# Modular Implicits

**URL:** <https://discuss.ocaml.org/t/modular-implicits/144>\
**Category:** Ecosystem\
**Tags:** faq, compiler\
**Created:** [May 15, 2017, 3:06pm UTC](https://discuss.ocaml.org/t/modular-implicits/144 "2017-05-15T15:06:40Z")\
**Posts on this page:** 4\
**Page:** 4

<div class="post-metadata">

**Author:** ![kantian](https://avatars.discourse-cdn.com/v4/letter/k/4bbf92/32.png) [@kantian](https://discuss.ocaml.org/u/kantian)\
**Post date:** [April 12, 2018, 6:09pm UTC](https://discuss.ocaml.org/t/modular-implicits/144/61 "2018-04-12T18:09:28Z")

</div>

> [@bluddy](#):
>
> And what advantage do functors give us that type classes cannot perform?

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.

[![](https://img.youtube.com/vi/XtogTwzcGcM/maxresdefault.jpg "Adventure with Types in Haskell - Simon Peyton Jones (Lecture 4)") ](https://www.youtube.com/watch?v=XtogTwzcGcM)

Around the 15th minutes, he shows this example:

```haskell
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:

```ocaml
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`:

```ocaml
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:

```haskell
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

```

[![](https://img.youtube.com/vi/brE_dyedGm0/maxresdefault.jpg "Adventure with Types in Haskell - Simon Peyton Jones (Lecture 2)") ](https://www.youtube.com/watch?v=brE_dyedGm0)

(see around 38 minutes)

he said this is not possible to do in an ML language, so here we go in OCaml

```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.

---

<div class="post-metadata">

**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\
**Post date:** [March 31, 2021, 6:44pm UTC](https://discuss.ocaml.org/t/modular-implicits/144/62 "2021-03-31T18:44:41Z")

</div>

> [@lpw25](#):
>
> This requires us to answer questions like: “Is there any module `X` such that the result of `Print_list(X)` would be of the required module type?”. Which is actually just  
> a unification problem at the module level, essentially can we unify `= Print_list(?X)` with `sig type t = int list val print : ...` , where `?X` is a unification variable and `= ...` is a singleton type/module alias.
> 
> So implementing modular implicits requires us to implement a unification algorithm at the module level. Now the prototype uses a very naive algorithm which is very weak and quite unpredictable. My more ambitious plan is to implement a higher-order pattern unification, of the sort found in languages like Agda, and to do so for the full module language. My plan also includes strengthening the module language with additional equalities – in particular module aliases on functor applications and eta-equality on structures – in order for unification to have some more desirable properties.

I can’t figure out an example where high-order unification is important and naive unification is not enough. Can you point on the one so I could study it?

P.S. Sorry for necroposting 🙂

---

<div class="post-metadata">

**Author:** ![anmolsahoo25](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@anmolsahoo25](https://discuss.ocaml.org/u/anmolsahoo25)\
**Post date:** [April 15, 2021, 5:55pm UTC](https://discuss.ocaml.org/t/modular-implicits/144/63 "2021-04-15T17:55:29Z")

</div>

This might help -

> [@Modular Implicits](https://discuss.ocaml.org/t/modular-implicits/144/18):
>
> Is it possible that a more limited implementation that was not so ambitious but was compatible with a future more general version would be feasible? Much of the work for a limited version would need to be redone from scratch for the more complete version. Given our very limited man power, doubling the amount of work we have to do is probably not a good idea. The more limited version would still be a huge amount of work, so it is not like it would appear any time soon anyway. My plan is certa…

---

<div class="post-metadata">

**Author:** ![nrolland](https://avatars.discourse-cdn.com/v4/letter/n/d26b3c/32.png) [@nrolland](https://discuss.ocaml.org/u/nrolland)\
**Post date:** [October 24, 2022, 12:24pm UTC](https://discuss.ocaml.org/t/modular-implicits/144/64 "2022-10-24T12:24:46Z")

</div>

Is there a recent thread for tracking progress on modular implicits ?

[Previous page](https://discuss.ocaml.org/t/modular-implicits/144.md?page=3)