Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 322
hawkeye Avatar asked Dec 26 '13 09:12

hawkeye


1 Answers

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.

like image 78
J. Abrahamson Avatar answered Nov 15 '22 09:11

J. Abrahamson