Why are there so many `map` function for different types in F#

Question

I'm learning F#. I started FP with Haskell, and I've got curious for this.

Since F# is .NET language, It seems to be more reasonable for me to declare interface like Mappable, just like haskell Functor type class.

But like the picture above, F# functions are seperated and implemented on it's own. What's the design purpose of such design? For me, introducing Mappable.map and implementing this for each data type would be more convenient.

Answer 1

Yes, a very straightforward question on the surface. But if you take the time to think it through to the end, you get into the depths of type theory immeasurable. And the type theory stares also into you.

First, of course, you have already correctly figured out that F# doesn't have type classes, and that's why. But you propose an interface Mappable. Ok, let's look into that.

Let's say we can declare such an interface. Can you imagine what the signature of it would look like?

type Mappable =
    abstract member map : ('a -> 'b) -> 'f<'a> -> 'f<'b>

Where f is the type implementing the interface. Oh wait! F# doesn't have that either! Here f is a higher-kinded type variable, and F# doesn't have higher-kindedness at all. There is no way to declare a function f : 'm<'a> -> 'm<'b> or something like that.

But ok, let's say we got over that hurdle as well. And now we have an interface Mappable that can be implemented by List, Array, Seq, and the kitchen sink. But wait! Now we have a method instead of a function, and methods don't compose well! Let's look at adding 42 to every element of a nested list:

// Good ol' functions:
add42 nestedList = nestedList |> List.map (List.map ((+) 42))

// Using an interface:
add42 nestedList = nestedList.map (fun l -> l.map ((+) 42))

Look: now we have to use a lambda expression! There is no way to pass this .map implementation to another function as a value. Effectively the end of "functions as values" (and yes, I know, using a lambda doesn't look very bad in this example, but trust me, it gets very ugly)

But wait, we're still not done. Now that it's a method call, type inference doesn't work! Because a .NET method's type signature depends on the type of the object, there is no way for the compiler to infer both. This is actually a very common problem newbies hit when interoperating with .NET libraries. And the only cure is to provide a type signature:

add42 (nestedList : #Mappable) = nestedList.map (fun l -> l.map ((+) 42))

Oh, but this is still not enough! Even though I have provided a signature for nestedList itself, I have not provided a signature for the lambda's parameter l. What should such signature be? Would you say it should be fun (l: #Mappable) -> ... ? Oh, and now we finally got to rank-N types, for you see, #Mappable is a shortcut for "any type 'a such that 'a :> Mappable" - i.e. a lambda expression which is itself generic.

Or, alternatively, we could go back to the higher-kindedness and declare the type of nestedList more precisely:

add42 (nestedList : 'f<'a<'b>> where 'f :> Mappable, 'a :> Mappable) = ...

But ok, let's put aside the type inference for now and get back to the lambda expression and how we now cannot pass map as a value to another function. Let's say we extend the syntax a bit to allow for something like what Elm does with record fields:

add42 nestedList = nestedList.map (.map ((+) 42))

What would the type of .map be? It would have to be a constrainted type, just like in Haskell!

.map : Mappable 'f => ('a -> 'b) -> 'f<'a> -> 'f<'b>

Wow, ok. Putting aside the fact that .NET doesn't even allow such types to exist, effectively we just got back type classes!

But there is a reason that F# doesn't have type classes in the first place. Many aspects of that reason are described above, but a more concise way to put it is: simplicity.

For you see, this is a ball of yarn. Once you have type classes, you have to have constraints, higher-kindedness, rank-N (or at least rank-2), and before you know it, you're asking for impredicative types, type functions, GADTs, and all the rest of it.

But Haskell does pay a price for all the goodies. Turns out there is no good way to infer all that stuff. Higher-kinded types sorta work, but constraints already kinda don't. Rank-N - don't even dream of it. And even when it works, you get type errors that you have to have a PhD to understand. And that's why in Haskell you're gently encouraged to put type signatures on everything. Well, not everything-everything, but really almost everything. And where you don't put type signatures (e.g. inside let and where) - surprise-surprise, those places are actually monomorphised, so you're essentially back in the simplistic F#-land.

In F#, on the other hand, type signatures are rare, mostly just for documentation or for .NET interop. Outside of those two cases, you can write a whole big complex program in F# and not use a type signature once. Type inference works fine, because there is nothing too complex or ambiguous for it to handle.

And this is the big advantage of F# over Haskell. Yes, Haskell lets you express super complex stuff in a very precise way, that's good. But F# lets you be very wishy-washy, almost like Python or Ruby, and still have the compiler catch you if you stumble.