[Haskell-cafe] List Monads and non-determinism

[Timon Gehr]

On 07/20/2013 12:23 AM, Matt Ford wrote:
> Hi All,
>
> I thought I'd have a go at destructing
>
> [1,2] >>= \n -> [3,4] >>= \m -> return (n,m)
>
> which results in [(1,3)(1,4),(2,3),(2,4)]
>
> I started by putting brackets in
>
> ([1,2] >>= \n -> [3,4]) >>= \m -> return (n,m)
> ...

This is not the same expression any more. See below for the correct 
bracketing.

> This immediately fails when evaluated: I expect it's something to do
> with the n value now not being seen by the final return.
>
> It seems to me that the return function is doing something more than
> it's definition (return x = [x]).
>
> If ignore the error introduced by the brackets I have and continue to
> simplify I get.
>
> [3,4,3,4] >>= \m -> return (n,m)
>
> Now this obviously won't work as there is no 'n' value.  So what's
> happening here? Return seems to be doing way more work than lifting the
> result to a list, how does Haskell know to do this?  Why's it not in the
> function definition?  Are lists somehow a special case?
>
> Any pointers appreciated.
> ...


[1,2] >>= (\n -> [3,4] >>= (\m -> return (n,m)))

~>*

((\n -> [3,4] >>= (\m -> return (n,m))) 1) ++ ((\n -> [3,4] >>= (\m -> 
return (n,m))) 2)

~>*

([3,4] >>= (\m -> return (1,m))) ++ ([3,4] >>= (\m -> return (2,m)))

~>*

((\m -> return (1,m)) 3 ++ (\m -> return (1,m)) 4) ++ ((\m -> return 
(2,m)) 3 ++ (\m -> return (2,m)) 4)

~>*

return (1,3) ++ return (1,4) ++ return (2,3) ++ return (2,4)

~>*

[(1,3)] ++ [(1,4)] ++ [(2,3)] ++ [(2,4)]

~>*

[(1,3),(1,4),(2,3),(2,4)]

Where the definition return x = [x] has been applied in the second-last 
step.