Haskell folks really think that type classes should be generalized. Simon Peyton Jones gave a serie of lectures about type system and Haskell. He introduced type classes in his first lecture, at the very beginning, then in the fourth one he pointed limitation of basic type classes and how to generalize them.
Around the 15th minutes, he shows this example:
class Key k where
data Map k :: * -> * -- here the generalization
empty :: Map k v
lookup :: k -> Map k v -> Maybe v
-- insert, union, etc.
instance Key Bool where
data Map Bool v = MB (Maybe v) (Maybe v)
empty = MB Nothing Nothing
lookup True (MB _ mt) = mt
lookup False (MB mf _) = m
and here, how we can basicaly do this with modules:
module type S = sig
type key
type 'a t
val empty : 'a t
val lookup : key -> 'a t -> 'a option
val insert : key -> 'a -> 'a t -> 'a t
end
module Map_bool : S with type key = bool = struct
type key = bool
type 'a t = 'a option * 'a option
let empty = None, None
let lookup k m = (if k then snd else fst) m
let insert k x m = if k then fst m, Some x else Some x, snd m
end
and using functors, we can also use standard lib Map:
module Of_MapS (M : Map.S) : S with type key = M.key = struct
type key = M.key
type 'a t = 'a M.t
let empty = M.empty
let lookup = M.find_opt
let insert = M.add
end
Map_bool.(empty |> insert true "OCaml" |> insert false "Haskell" |> lookup true);;
- : string option = Some "OCaml"
let module K = struct type t = bool let compare = Pervasives.compare end in
let module M = Of_MapS (Map.Make (K)) in
M.(empty |> insert true "OCaml" |> insert false "Haskell" |> lookup true);;
- : string option = Some "OCaml
But, more surprisingly, he claimed something false about ML languages in his second lecture when he introduced higher-kinded polymorphism with this example:
data Tree f a = Leaf a
| Node (f (Tree f a))
type RoseTree a = Tree [] a
type BinTree a = Tree Pair a
type AnnTree a = Tree AnnPair a
data Pair a = P a a
data AnnPair = AP String a a
(see around 38 minutes)
he said this is not possible to do in an ML language, so here we go in OCaml
module Tree (F : sig type 'a t end) = struct
type 'a t = Leaf of 'a | Node of ('a t) F.t
end
module RoseTree = Tree (struct type 'a t = 'a list end)
module BinTree = Tree (struct type 'a t = 'a * 'a end)
module AnnTree = Tree (struct type 'a t = string * 'a * 'a end)
module RoseTree : sig type 'a t = Leaf of 'a | Node of 'a t list end
module BinTree : sig type 'a t = Leaf of 'a | Node of ('a t * 'a t) end
module AnnTree : sig type 'a t = Leaf of 'a | Node of (string * 'a t * 'a t) end
I agree that type classes are useful, and so will be modular implicits, but you should not underestimate the power of ML module system.
