Good examples of the value of functors, in terms of expressivity

Learning
,
1

So, I recently had the time to spend a few hours discussing languages with someone who hasn’t used Haskell or OCaml or the like, but likes functional programming and strict type-systems.

In particular, I’d have liked to make a better showing in explaining why we value our higher-kinded tooling, functors - having used them in anger and at work, I’m a fan; and I feel like I’ve seen good arguments for the power of the ‘module-language functors’ approach over things like typeclasses … but I’m actually at more of a loss here than I’d expected.

I started out with a classic “fully generic map” example …

module type Mappable = sig
  type 'a t
  val our_map : ('a -> 'b) -> 'a t -> 'b t
end

module ListMappable : Mappable with type 'a t = 'a list = struct
  type 'a t = 'a list
  let our_map = List.map
end

module OptionMappable : Mappable with type 'a t = 'a option = struct
  type 'a t = 'a option
  let our_map f = function
    | None -> None
    | Some x -> Some (f x)
end

module MakeMap (M : Mappable) = struct
  let our_map f x = M.our_map f x
end

let list_result = MakeMap(ListMappable).our_map (fun x -> x + 1) [1; 2; 3] in
let option_result = MakeMap(OptionMappable).our_map (fun x -> x + 1) (Some 1) in ...

… but I was surprised at how much cleaner Kotlin’s (chatGPT-generated, forgive me, I don’t know Kotlin yet) example was than what I’d build w/ OCaml:

fun <T, R, C : Collection<T>> C.map(transform: (T) -> R): List<R> {
    val result = mutableListOf<R>()
    for (item in this) {
        result.add(transform(item))
    }
    return result
}

Now, of course, this result isn’t fully generic in the collection-return-type; and attempting to extract that blew the complexity up hugely … okay, fine, point to OCaml there. But nonetheless, generally speaking, I didn’t feel that example did a good job of demonstrating what functors are good for in practice, that more mainstream-style ‘generics’ and ‘interfaces’ and the like don’t provide.

I feel like the times they’ve really benefitted me in practice (already relatively rare, because half the time, I’m just using functors to work around a different shortcoming of OCaml, instead of using them for something they’re really ideal for, ugh) were in larger projects; so I could definitely lean on the code-reuse / separation-of-concern benefits of functorial design, but I’d really like to show that they do also help express certain algorithmic/modularity concepts … I just, off my head, can’t think of a good specific example from all my time using OCaml.

tl;dr What’re y’all’s favourite educational examples that show the expressivity benefits of typing-features like functors (and relatedly, typeclasses)?

2 Likes
2

My favorite example of modules and functors are implementations of algebraic structures (like rings). Here’s a small library I once implemented as part of some schoolwork: ocaml-algebra/lib at master · sim642/ocaml-algebra · GitHub.
The OCaml implementations follow mathematical definitions very closely. For example, any field can be lifted into a polynomial ring (with field elements as coefficients). Or quotient fields can be constructed from Euclidean rings (and a chosen modulus), in particular modular arithmetic (rings) for a chosen modulus.

The latter also exemplifies the usefulness of modules as opposed to type classes: you can define multiple modular rings (on the int type) with different moduli and the module system can statically prevent certain misuse. Conventionally, type classes only allow one (simultaneous) instance for a type, so similar things can be less convenient (requiring wrapper types).

In Goblint we use functors extensively for abstract domains (algebraically lattices, or at least lattice-like), among many other things.

3 Likes
3

I don’t know Kotlin myself so I’m not able to judge what you posted; but, if you don’t know it either, ChatGPT may well have generated an answer experts would qualify as bad or incomplete (the forum rules advise against posting generated content and that is one reason).

Here, map should be a “functor”, that is it should in particular preserve the generic container type, so returning a list systematically looks completely incorrect. I don’t know if this is the only possible solution in Kotlin or if ChatGPT gave a wrong answer.

Finally, my goto-example to illustrate the power of functors is OCamlgraph.

2 Likes
4

Norman Ramsey wrote an embeddable Lua interpreter in ML and a paper explaining how the design exemplifies the advantages of modules

https://www.cs.tufts.edu/~nr/pubs/maniaws-abstract.html
I personally haven’t read it but I’d like to when I get a chance.