bind vs flatMap

[Evan Czaplicki]

I have been giving this talk recently where I introduce Pure Monadic FRP with this function:

bind : Signal a -> (a -> Signal b) -> Signal b

Usually it is hard for people to figure out what that means, especially without a lot of Haskell knowledge. Introducing join helps. Later I introduce it the Reactive Extensions way:

flatMap : Signal a -> (a -> Signal b) -> Signal b

Goes way better! It builds on existing intuition about what map means and adds the fact that you "flatten" the thing. This is a waaay clearer name in my opinion. It builds on your existing knowledge to help you understand.

I wonder if this is a nicer name in domains besides FRP?

P.S. Is bind a word from Category Theory? Why does Haskell call it that?

[Max Goldstein]

This reminds me of this talk, with the monads starting around 24:30. After about 4 minutes he discusses naming conventions and also uses the term flatMap. So it seems that name is nicer in FP, a slighter larger domain than FRP.

It's your choice: have the non-haskellers understand you and make the haskellers mad, or have the haskellers understand you and make the non-haskellers bewildered.

[Eitan Chatav]

Bind is not a word from category theory. I don't know why Haskell calls is that but it sounds programmey to me (bind the payload of this variable to the input of this procedure). In category theory, you'd probably call it Kleisli evaluation if you called it anything. In category theory, monads are defined by their return and join operation which are called unit (eta) and multiplication (mu). flatMap, or better joinMap, is a good name for bind since (up to flipping some arguments) it really is obtained by first mapping over the functor and then using monadic join. Indeed, in the list monad in Haskell it actually does have a synonym named concatMap.

(=<<) == ((.).(.)) join fmap

P.S. I really enjoyed your talk :-D

[Jeff Smits]

I prefer flatten and flatMap over join(Map) and concat(Map). I get that bind means to bind what's in the monad to the parameter of the function you supply to bind, but it's still non-intuitive I think.

The only problem with the name flatten is that in dynamically typed languages it is sometimes used with the meaning of flattening arbitrarily deeply nested lists. 

Offtopic: The talk Max linked to is rather interesting to watch. I don't agree with everything he says, but still very nice.

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Max New]

bind is not a name from category theory. I believe it's supposed to be similar in name to `let`, as in

bind m <| \x -> ...

Would be read like "bind m to x in" which reads like a backwards "let" statement.

[Evan Czaplicki]

Ooh, I like (flatten : container (container a) -> container a) as a parallel to flatMap! It's a shame about what flatten means in Scheme (and other Lisps I guess?), but I don't think that's a show stopper considering how nicely those work together!

Max New, that makes sense. Though I wonder with a name like flatMap, should the arguments be moved around?

flatMap : (a -> container b) -> container a -> container b

contrivedExample : State Int Int

contrivedExample =

    pure 7

      |> flatMap (\seven -> put 4)

      |> flatMap (\nil -> get)

I think it's a bit weird. Maybe there is a better example?

Also, what if there was do-notation and named functions, but no operators to do the same stuff. I think part of the difficulty with learning this stuff in Haskell is that:

contrivedExample :: State Int Int

contrivedExample =

    do seven <- pure 7

       put 4

       get

-- desugars to this:

contrivedExample'Clarified' =

    pure 7 >>= put 4 >> get

So at the end of the explanation, you are just left to wonder what (>>=) and (>>) are and what they might mean. It looks weirdly easy now that I know this stuff, but even when you know what it means, this is rarely (never?) a good style for making things readable and making CL's minimally invasive. I think that is debatable, but in an industrial setting, I'd probably put "use do notation" in the style guide to maximize clarity.

--

[Brian Slesinsky]

What does it actually do in terms of signals? I see that the function can map each 'a' to a different 'Signal b', but how are all the (Signal b)'s combined into a single (Signal b)?

- Brian

[Dylan Sale]

> What does it actually do in terms of signals? I see that the function can map each 'a' to a different 'Signal b', but how are all the (Signal b)'s combined into a single (Signal b)?

It returns a signal that merges all the other signals (ie it emits all items emitted by any of them).

[Evan Czaplicki]

Brian, see the diagrams in this post. Start with map and then check out flatMap. They call these "marble diagrams" and they say what Dylan said in pictures. I think it can be helpful once you decipher the diagrams in the first place :P

[Jeff Smits]

That post really helps to understand those marble diagrams :) I never quite took the time to check those out. I guess they help when you have dynamic signal graphs.

Notice that flatMap/flatten is not available for Signals in Elm!

[Brian Slesinsky]

Right, but the reason I asked (and I think you made a similar point more diplomatically in your presentation) at is that concatenation doesn't actually make much sense for infinite streams.

If you have finite (or at least potentially finite) lists, flatMap makes sense. If you have infinite lists (a concat b) is just a.

I wonder if calling it mapConcat would make it clearer that treating signals as a monad is trying to do something that doesn't make sense?

- Brian

[John Mayer]

Bind is a vestigial name from using monads to do IO in Haskell, and it's a decent word when describing monads as computation contexts.

I'm not a big fan of the list-derived names like flatMap or mapConcat or any other those, frankly. It implies that we're working with containers, but there are a lot of monads which aren't containers. State is not a container. Maybe is kind of a container, but is flatMap then descriptive at all? Meh.

I like "join : m (m a) -> m a" the best.

[Dylan Sale]

> Right, but the reason I asked (and I think you made a similar point more diplomatically in your presentation) at is that concatenation doesn't actually make much sense for infinite streams.

It's not a concatenation, but a merging of the outputs. They can both be infinite and when any of them emit an output, the merged signal will also emit one. In your example, if a and b are infinite (in this sense infinite just means it never sends a completed message), then 'a merge b' would be a signal that is also infinite and which outputs b's outputs mixed in with a's. (Also, I think in Elm that all Signals are "infinite", they just retain the last state they were changed to whenever they are sampled.)

See https://github.com/Netflix/RxJava/wiki/Combining-Observables#merge for a marble diagram.

From other discussions it seems like the reason flatMap doesn't work in a pure language like Elm is that it allows for the creation of new signals at runtime, which means that (because you always need to keep every signal around forever due to the fact that they are all "infinite") your memory usage grows linearly with each new signal that gets created. (This is just my understanding, Evan has discussed this at length before: https://github.com/evancz/Elm/issues/413)

I think a better name would be mapMerge rather then flatMap (it maps the output of a signal to other signals, then merges the resulting signals).

[Evan Czaplicki]

I think my general question with this thread was: is there a better name for the general idea of "bind"? So not just for signals but for any monad. And perhaps taking inspiration from flatMap would be good because it seems to work for containers reasonably well. It seems like a clumsy name for things like HTTP and IO and State.

So maybe there are general categories of monadic things? Something like:

• containers - List, Set, Dict, etc. I don't think I'd ever use things like fmap or (=<<) for this kind of stuff though.
• effects - HTTP, IO, State, Reader, Writer, etc. Definitely use monadic functions heavily when using any of these.
• control flow - not really sure what kind of things fit here. Definitely Errors. Parsec? Is this really distinct from effects?
  

Perhaps figuring out groups of the useful monads could help get to better names in "the common case".

[Evan Czaplicki]

I kind of like this if we are just thinking about "effects":

andThen : effect a -> (a -> effect b) -> effect b

Sometimes it's a shame then is a keyword, so I went with andThen for now :) Going with the example from before:

contrivedExample : State Int Int

contrivedExample =

    pure 7

      `andThen` (\seven -> put 4)

      `andThen` (\nil   -> get)

I think I'm sort of starting to feel like do-notation is always preferable to this kind of code... Not really sure though.

[John Nilsson]

Another common name for that is simply ';'

BR

John

[Jeff Smits]

I think it would be an interesting exercise to see if monads can fall into distinct categories. Containers and effects seem to be good categories. I'm not sure about control flow though.

I think the following names are both nice in general for monads:
flatten : m (m a) -> m a
merge   : m (m a) -> m a

join    : m (m a) -> m a

But for merge and join I find the type (a -> b -> c) -> m a -> m b -> m c quite natural too.

That's all the disparate thoughts I can come up with for now.

--

[Alexander Noriega]

There is chain, which has:

1. Less potential for pedagogically harmful connotations and inaccurate analogies, than flatMap.

2. Expresses the motivation of wanting to enforce a coherent shape/sequence for one's computations.

P.S: +1 on avoiding the "Functors/Monads are containers" teaching trick from influencing API naming choices. That trick did a great disservice to me when I was first learning, by allowing me to understand concrete examples, but severely limiting me to further understand the concepts and their relation with other concepts. I now agree with this person.

--Alexander

[Alexander Noriega]

Forgot to mention that the chain name I know it from fantasy-land.

[Max New]

Dict isn't a monad, is it? Perhaps some kind of indexed monad?

List and Set are fine monads to use with fmap and (>>=), but you probably won't think of them as containers when you do. You can think of List (or anything in Haskell's MonadPlus class) as being a simple backtracking monad that you can use for Logic Programming. For instance taking two lists and taking pairs of distinct elements is easy when you think of it this way:

guard : Bool -> [()]
guard b = if b then [()] else []

distinctPairs : [a] -> [a] -> [(a,a)]
distinctPairs xs ys =
  xs >>= \x ->
  ys >>= \y ->
  guard (x /= y) >>
  pure (x, y)

So often when you are using so-called "container" Monads, you often think of them as an "effect"

In general, the best intution for "container" Monads is that they are all Tree types (like List). Basically, `join : Tree (Tree a) -> Tree a` would take a tree whose leaves are trees and then graft those trees in their place.

This is how you get a Free Monad as well.
If you think of a simple tree type:
data Tree a = Leaf a | Node [Tree a]
then your join would be
join : Tree (Tree a) -> Tree a
join tt = case tt of
  Leaf t    -> t
  Node ts -> Node <| map join ts

Then if you noticed all we needed was map so if instead of [] you took an arbitrary Functor F (by Functor I mean we have fmap : (a -> b) -> F a -> F b) you would get

data FTree a = Leaf a | Node (F a)
join : FTree (FTree a) -> FTree a
join tt = case tt of
  Leaf t    -> t
  Node ts -> Node <| fmap join ts

Not sure where I was going with that, but there you have it.

[Brian Slesinsky]

On Tuesday, March 25, 2014 10:00:40 PM UTC-7, Dylan Sale wrote:

It's not a concatenation, but a merging of the outputs.

Of course! Thank you for straightening me out.

 

I think a better name would be mapMerge rather then flatMap (it maps the output of a signal to other signals, then merges the resulting signals).

+1. "Merge" works well for me because it's a general term that suggests a variety of possible ways to do the merge.

In the case of merging two unsorted lists, it could be concatenation or cartesian product. Merging two sorted lists would mean maintaining the sort order. We could consider signals to be infinite streams of events sorted by timestamp, and a merge preserves timestamp order.

I think it would generalize to effects as well. Two commands can be merged by running the first one followed by the second one.

(I am inspired to go off and write a monad tutorial, but I will resist the impulse. :-)

- Brian

[Eitan Chatav]

It's maybe instructive to compare some type signatures:

                         (a -> b) -> a -> b                 Names: apply, <|, $

Functor f      => (a -> b) -> f a -> f b            Names: map, fmap, <$>, <~

Applicative f => f (a -> b) -> f a -> f b          Names: ap, <*>, ~

Monad f       => (a -> f b) -> f a -> f b          Names: bind (flipped), flatMap, concatMap, =<<

Also their flips

                         a -> (a -> b) -> b                 Names: |>, #

Functor f      => f a -> (a -> b) -> f b            (never used???)

Applicative f => f a -> f (a -> b) -> f b          Names: <**> (rarely used???)

Monad f       => f a -> (a -> f b) -> f b          Names: bind, flatMap?, >>= (more common then its flip)

It would be very nice to have a consistent naming system for them. My suggestion is names for the first four, and directional combinators for all 8. For example (but I care more about consistency than actual names):

apply <| |>

map <~ ~>

ap <* *>

flatMap =<< >>=

BTW, the reason I'd want the rarely used left-to-right combinators is that it reads better when used in combination with the often used left-to-right combinators. I find it extremely ugly when I see something like g <~ (x |> f).