10 ms·

> each result of "bind" sits in its own version of the original data structure, which then have to be combined back into a single data structure That doesn't m

> each result of "bind" sits in its own version of the original data structure, which then have to be combined back into a single data structure That doesn't make sense to me. Let's say I have the list [5,3,4], to me that means each application returns a three element list [f(5),x,x], [x,f(3),x], and [x,x,f(4)] then the bind function takes these lists and turns them into [f(5),f(3),f(4)]. What makes this function a monad?

scottmsul 10y ago
It makes a List of Lists, then combines those into a List. [5,3,4] becomes [f(5), f(3), f(4)], but f(x) must return a List. Those inner Lists are then concatenated. When I say "original data structure", I mean the type of data structure is the same (in this case, List).
- jnordwick 10y ago
  What is the data structures don't support a join operation, like a tree?
  - scottmsul 10y ago
    We would need a way to transform a Tree of Trees into a single Tree. The inner Trees would be at leaf nodes of the outer Tree, so they could be attached in place. Although I recall monads need to satisfy certain laws, and I don't recall if Trees satisfy them or not. Just because something is a data structure does not necessarily imply it is a monad.
    - dllthomas 10y ago
      A rose tree is a monad.
gizmo686 10y ago
In this case "data structure" refers to List, not a specific size or type of list. For example, suppose you have a list of ints, and want to bind a function, show. We have types: [5,3,4] :: List Int show :: Int -> List Char That is to say, [5,3,4] is a list of ints, and show is a function that takes an int and returns a list of characters. In this case, we would have [5,3,4] >>= show f(5) ++ f(3) ++ f(4) ['5'] ++ ['3'] ++ ['4'] ['5','3','4'] where "++" is list concatenation. The idea here is that when we apply show, we get back 3 different Lists, and want to combine them into a single list.
- deleted 10y ago
  [deleted]
- jnordwick 10y ago
  So bind is flat map in other languages? If join is a function that take a list and appends its elements together join ( [[1], [2], [3]] ) -> [1,2,3] then bind is join(map(f, x))? bind just seems like a terrible name. For some reason Haskell users try to make things sounds as academic as possible.
  - gizmo686 10y ago
    >For some reason Haskell users try to make things sounds as academic as possible. Probably because Haskell ended up being the language for academics. If you want to do programming language research in an ML-type language use Haskell. If you want to make a product, use OCaml. Not entirely true, but pretty close. >So bind is flat map in other languages. In the case of a List, yes, but there are other datastructures that implement Monad. This type of thing happens a fair amount in Haskell. It is not that uncommon to see code like: instance Monad List where (>>=) = flatMap That is to say, the implementation of the interface is just another function that has a more domain specific name. There are other monads with a bind that cannot be understood as flatMap. For example, the Maybe datatype is Haskell's version of Optional. For example, if a variable is of type `Maybe t`, it either contains a single value of type t, or no value. It is common to use Maybe without using it as a monad. However, Maybe does implement the Monad interface. In this case, bind is defined as follows: x.bind(f) = if (x.hasValue()) then { return Just(f(x.value)) } else { return Nothing() } where Just and Nothing are two constructors of Maybe. If we view 'no value' as analogous to null, then this bind function is null propogation.
    - Forlien 10y ago
      I feel a bit dumb asking this, but your explanation doesn't make it clear to me why you can't think of a bind on Maybe as a flatMap on a List with 0 (Nothing) or 1 (Just) elements. Could you elaborate further on how thinking of a bind on Maybe as null propagation eliminates it also being interpreted as a flatMap on a restricted-size list?
Tarean 10y ago
I think an easier to understand definition uses fmap and join. Example: f x = [x, x*2] f =<< [5, 3, 4] join (fmap f [5, 3, 4]) join ([[5, 10], [3, 6], [4, 8]]) [5, 10, 3, 6, 4, 8] So the pattern is fmap a function `a -> f b`; this leaves us with `f (f b)` so we flatten. You might notice that we could bind as often as we want since we always get a list of integers!
- StavrosK 10y ago
  I think if you already know fmap, join and Haskell syntax, you also already know monads, so I'm not sure whom this is easier for :P

scottmsul 10y ago

It makes a List of Lists, then combines those into a List. [5,3,4] becomes [f(5), f(3), f(4)], but f(x) must return a List. Those inner Lists are then concatenated. When I say "original data structure", I mean the type of data structure is the same (in this case, List).

jnordwick 10y ago
What is the data structures don't support a join operation, like a tree?
- scottmsul 10y ago
  We would need a way to transform a Tree of Trees into a single Tree. The inner Trees would be at leaf nodes of the outer Tree, so they could be attached in place. Although I recall monads need to satisfy certain laws, and I don't recall if Trees satisfy them or not. Just because something is a data structure does not necessarily imply it is a monad.
  - dllthomas 10y ago
    A rose tree is a monad.

gizmo686 10y ago

In this case "data structure" refers to List, not a specific size or type of list. For example, suppose you have a list of ints, and want to bind a function, show. We have types: [5,3,4] :: List Int show :: Int -> List Char That is to say, [5,3,4] is a list of ints, and show is a function that takes an int and returns a list of characters. In this case, we would have [5,3,4] >>= show f(5) ++ f(3) ++ f(4) ['5'] ++ ['3'] ++ ['4'] ['5','3','4'] where "++" is list concatenation. The idea here is that when we apply show, we get back 3 different Lists, and want to combine them into a single list.

deleted 10y ago
[deleted]
jnordwick 10y ago
So bind is flat map in other languages? If join is a function that take a list and appends its elements together join ( [[1], [2], [3]] ) -> [1,2,3] then bind is join(map(f, x))? bind just seems like a terrible name. For some reason Haskell users try to make things sounds as academic as possible.
- gizmo686 10y ago
  >For some reason Haskell users try to make things sounds as academic as possible. Probably because Haskell ended up being the language for academics. If you want to do programming language research in an ML-type language use Haskell. If you want to make a product, use OCaml. Not entirely true, but pretty close. >So bind is flat map in other languages. In the case of a List, yes, but there are other datastructures that implement Monad. This type of thing happens a fair amount in Haskell. It is not that uncommon to see code like: instance Monad List where (>>=) = flatMap That is to say, the implementation of the interface is just another function that has a more domain specific name. There are other monads with a bind that cannot be understood as flatMap. For example, the Maybe datatype is Haskell's version of Optional. For example, if a variable is of type `Maybe t`, it either contains a single value of type t, or no value. It is common to use Maybe without using it as a monad. However, Maybe does implement the Monad interface. In this case, bind is defined as follows: x.bind(f) = if (x.hasValue()) then { return Just(f(x.value)) } else { return Nothing() } where Just and Nothing are two constructors of Maybe. If we view 'no value' as analogous to null, then this bind function is null propogation.
  - Forlien 10y ago
    I feel a bit dumb asking this, but your explanation doesn't make it clear to me why you can't think of a bind on Maybe as a flatMap on a List with 0 (Nothing) or 1 (Just) elements. Could you elaborate further on how thinking of a bind on Maybe as null propagation eliminates it also being interpreted as a flatMap on a restricted-size list?

Tarean 10y ago

I think an easier to understand definition uses fmap and join. Example: f x = [x, x*2] f =<< [5, 3, 4] join (fmap f [5, 3, 4]) join ([[5, 10], [3, 6], [4, 8]]) [5, 10, 3, 6, 4, 8] So the pattern is fmap a function `a -> f b`; this leaves us with `f (f b)` so we flatten. You might notice that we could bind as often as we want since we always get a list of integers!

StavrosK 10y ago
I think if you already know fmap, join and Haskell syntax, you also already know monads, so I'm not sure whom this is easier for :P