Hacker News Reader

Comment by celdon25 | Hacker News Reader

> The big reason to not use F# vs OCaml tends to come down to the lack of functors...

What do you mean by that? F# has support for functors, or are you referring to something else? https://fsprojects.github.io/FSharpPlus/applicative-functors...

View on HN

Those are an implementation of functors as they exist in Haskell. The functors I'm talking about are actually a language level construct that is a primary abstraction mechanism in OCaml/SML. They are essentially higher-level modules: modules that are parameterized by other modules.

https://stackoverflow.com/a/16353711

Can someone explain to me like I'm 5 what the big deal about functors is?

Probably not, as it is a very abstract generalization for what is essentially a simple concept that for most purposes doesn't need a math-y abstraction. And it would depend on whether you're talking about Haskell, or OCaml, or Category theory.

The best I could describe the general concept is that a functor allows you to take something of some type and maps it to another type via some unspecified function.

If you mean ML (i.e. OCaml) functors, then to put it simply: they are the primary code abstraction mechanism in ML. ML doesn't have inheritance and runtime dispatch, instead it uses functors which do static dispatch.

Simple example: in an OOP language you might have a Map<K, V> class for any type K, V where K must be an instance of an Ordered interface so that the map implementation can do efficient lookup.

In OCaml, you have a Map.Make(Ord : Ordered) functor which explicitly takes a module Ord as its parameter. The Ord module implements the key data type, which must support the Ordered interface. When you (statically) apply the functor, you get back a new module which specializes a map data type to work for the specific key type. E.g.,

    module StringMap = Map.Make(String)

The String module implements the Ordered interface, so it can be used as the argument here. Now you can create and manipulate maps of strings to any values.

You might be wondering, what's the payoff? It's very similar to the payoff for interfaces--code abstraction. It's just that it's all statically resolved and highly efficient.

Sounds like this is covered by F# already, simply by the use of genercs (similar to what you described for OOP, which in that particular case doesn't really have any OOP downsides, i.e.: no inheritance, no state).

>simply by the use of genercs

It depends on what you mean by "generics". Functors are generics, but very powerful ones, akin to packages in Ada.

They are way more generic than what parametric polymorphism allows you to do in F#, they support Higher Kinded Types, module can have many type variables within it etc etc.

In F# you have List<'a> but you cant have a single map operation abstracting over Lists, Arrays, Options..... so they have to be implemented separately Option.map, Array.map.....

Not just with generics, but also with dynamic dispatch on the runtime class of the K type which implements Ordered interface. ML traditionally doesn't have dynamic dispatch, so it uses the static mechanism of building a map type specialized to a given key type. The value type is completely generic, though.

I said 'traditionally' above because OCaml actually has dynamic dispatch now; it has a powerful and feature-complete OOP implementation, and a way to pass around modules at runtime as first-class objects. And in fact people take advantage of these capabilities to build more 'modern' APIs. But I would argue that the functor approach is one of, if not the best, overall.

He's talking about functor from OCaml and SML which are basically a function in the module level. So a module which take other modules as arguments and produce a new module.

OCaml functors are not the same as Haskell/F# functors/applicatives (which are essentially one and the same in OCaml if you use named arguments).

Instead, they're roughly "functions from modules to modules": https://dev.realworldocaml.org/functors.html. Functors allow you to replicate much of what classes/objects in an OO language offer, but with static instead of dynamic dispatch.

I am an F# person rather than OCaml and am not familiar with the compiler, but this seems to be overstating the difference: I thought the OCaml functors are “real” mathematical functors that implemented a structured type polymorphism over the “input type” - they look pretty similar to C++ templates superficially but they work similarly to Haskell type classes. They are “functions from modules to modules” but those functions take types as values.

Real experts should let me know if I am mistaken: I don’t think OCaml and Haskell have strictly the same type system, but they are both similarly more expressive than F# because of this specific type -> type polymorphism that in particular lets you do type-checked monads, etc.

Neither Haskell's nor OCaml's functors are the same as the mathematical one I believe, but both are similar in some way that the word makes sense to be used for their respective feature.

In OCaml, functors map between an abstract module and some concrete one. And in Haskell functors are structures that can have a function that maps over their elements. In math a functor is a map between categories. So you can see how all three kinda make sense as functors, but also are different in exactly what they are.

Both Haskell's and OCaml's functors are special cases of the general mathematical one.

How? What are the categories that OCaml's Hashtbl.Make maps between? What are the morphisms in those categories and how are they mapped?

It maps between a category with HashedType implementations as objects and a category with Make implementations as objects. Unfortunately it's not a very interesting functor because to satisfy the functor laws I think the categories have to be discrete. It's basically a function! (And functions are indeed a special case of functors.)

https://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.M...

Right, in other words it is just a function. I don't think the categories have to be discrete just to satisfy the functor laws; even ignoring that, what would the morphisms be in principle? I don't think there is an obvious choice, at least.

I think in OCaml, "functor" basically just means "like a function but for modules". They might technically be categorical functors, but it seems quite different to the meaning in Haskell where they are plainly categorical functors (modulo Hask technically not being a category).

Agreed, I'm not sure it's a terribly interesting functor.

Here is one way one might implement a categorical Functor (https://www.reddit.com/r/haskell/comments/eoo16m/base_catego...).

A function S -> T maps a S(ource) type to a T(arget) type, like FunctorOf (-S>) (-T>) does between the source category (-S>) and target category (-T>)

    type  Functor :: forall (s :: Type) (t :: Type). (s -> t) -> Constraint
    class (Category (Src f), Category (Tgt f)) => Functor (f :: s -> t) where
      type Src (f :: s -> t) :: Cat s
      type Tgt (f :: s -> t) :: Cat t
      fmap :: Src f a1 a2 -> Tgt f (f a1) (f a2)

    type FunctorOf :: forall (s :: Type) (t :: Type). Cat s -> Cat t -> (s -> t) -> Constraint
    type FunctorOf src tgt f = (Functor f, Src f ~ src, Tgt f ~ tgt)

The usual endofunctor

    type EndofunctorOf :: forall (ob :: Type). Cat ob -> (ob -> ob) -> Constraint
    type EndofunctorOf @ob cat f = FuntorOf @ob @ob cat cat f

we have in Haskell can be defined as FunctorOf @Type @Type (->) (->), or

    type OldFunctor :: (Type -> Type) -> Constraint
    type OldFunctor f = EndofunctorOf @Type (->) f

For simplicity written with a type synonym, but it cannot be partially applied. So I would use constraint synonym encoding (https://gist.github.com/Icelandjack/5afdaa32f41adf3204ef9025...)

    type FunctorOf :: forall (s :: Type) (t :: Type). Cat s -> Cat t -> Constraint

    class    (Functor f, Src f ~ src, Tgt f ~ tgt) => FunctorOf src tgt f
    instance (Functor f, Src f ~ src, Tgt f ~ tgt) => FunctorOf src tgt f

The other definitions can be eta reduced

    type EndofunctorOf cat = FunctorOf cat cat
    type OldFunctor        = EndofunctorOf (->)

In OCaml, "functors" are parametrized modules—mostly unrelated to functors and applicatives in the Haskell sense. Think about it as a module that can take another module as an input.

Reply on news.ycombinator.com