What is the difference between mapcat in Clojure and concatmap in Haskell?

Question

In Clojure you have a function called mapcat in Clojure, which bears some similarity to flatmap in Scala. It is used to map a function to a list and return a list.

In Haskell we have a function ConcatMap which in name seems quite similar.

My question is - what is the difference between mapcat in Clojure and concatmap in Haskell?

Somerville

Why do you think they are different? – Once

Because mapcat in Clojure and flatmap in Scala are different: #20363705 – Somerville

flatMap in Scala is the general name for monadic bind, which is >>= in Haskell. On the other hand concatMap is >>= specialised to the [] monad. – Leoraleos

So you're saying that the Clojure function and the Haskell function are similar, apart from the underlying differences in the data structures? – Somerville

Answer 1

concatMap in Haskell has the type concatMap :: (a -> [b]) -> [a] -> [b] while Clojure's mapcat, if it were to have any type at all, would have to be much more complex. At first approximation, we could write

mapcat :: (Collection c, Collection c') => (a -> c' b) -> c a -> [b]

Although, technically mapCat inherits map's dynamic argument list and thus cannot be typed in Haskell at all, but if it could it might look like

mapcat :: (forall c . Collection c => a -> ... -> c b) 
       -> [forall c . Collection c => c a]
       -> [b]

which emphasizes how dynamic mapCat could be, though still less dynamic than it actually is. That said, if we promise to just pass one lazy seq into mapcat then it's identical to concatMap and has almost exactly identical code

concatMap f s = concat (map f s)

(defn mapcat [f coll] (concat (map f coll)))

That said, in Haskell nobody uses concatMap, they use (>>=) (or list comprehensions which can be translated to (>>=) if desired).

-- flipped for consistency
flip (>>=) :: Monad m => (a -> m b) -> m a -> m b

It turns out that (>>=) is still less polymorphic on input than mapcat, but (>>=) is also output polymorphic. This allows it to have a great deal more semantic variety. You're not always draining values from collections, zipping the answers into a result list, and then gluing those results together. You might instead be passing a continuation function into a non-deterministic parallel orchestration process. Or sequencing parsers where the second depends on output from the first. Or propagating a stateful environment.

Mannish

I was very interested to see that. I'm not quite sure still how to read multi-arity type annotations—does it allow for individually varying inputs to the map function? – Mannish

The t ... b is a template for a sequence of types. It handles any legal arity of mapcat such that the function argument matches the number of arguments to mapcat. The paper describing this research is called "Practical Variable-Arity Polymorphism". – Madge

Thanks! I'll take a read. I'm currently implementing a system like this at work. – Mannish

Answer 2

mapcat only operates on sequences, and always returns a lazy-seq.

Trunk

"and always returns a lazy-seq" That's not a difference, since concatMap also returns a lazy list. – Surplice

I don't know Haskell. I'm just describing mapcat in Clojure. – Trunk