Modular Implicits

Ecosystem
,
61

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.

21 Likes