CODEWITHSUNDEEP
haskell
Evg
Evg

Reputation: 3080

haskell list comprehension via list monad understanding

I am from python world, but try to use functional as much as possible, and change my imperative thinking.

Now i study haskell and found that 

list = [(x,y) | x<-[1,2,3], y<-[4,5,6]]

are translated to 

list' = 
    [1,2,3] >>= \x ->
    [4,5,6] >>= \y ->
    return (x,y)

I try to understand step by step processing of list monad binds chain:

bind defind as: 

xs >>= f = concat (map f xs)

and bind is left associative

So as I understend, at start first bind ([1,2,3] >>= \x -> [4,5,6]) executed with result [4,5,6,4,5,6,4,5,6]

And then next bind [4,5,6,4,5,6,4,5,6] >>= \y -> return (x,y) executed

But how it can see x inside lambda if it's allready calculated ?? x is just argument that has no concrete value at all (lambda can be call with varios arguments at any time, how can we se it outside and fixed??). If it somehow can see it how can it know about that x call history was changed with 1,2,3 ? in my understanding onces first bind calculation done, only result [4,5,6,4,5,6,4,5,6] avaible and it goes next, to first argument of next bind.

So I can't understand how can i read this construction, and how it step by step logicaly produce correct result?

Upvotes: 2

Views: 324

Answers (1)

Jon Purdy
Jon Purdy

Reputation: 54981

This is a common source of confusion. The scope of the lambdas extends as far as possible, so this:

[1,2,3] >>= \x ->
[4,5,6] >>= \y ->
return (x,y)

Is equivalent to this:

[1,2,3] >>= (\x ->
  [4,5,6] >>= (\y ->
    return (x,y)))

So the inner lambda \y -> … is inside the scope of the outer lambda, \x -> …, meaning x and y are both in scope. You can then inline the definitions of >>= and return for the [] monad instance and step through the evaluation:

concatMap (\x ->
  concatMap (\y ->
    [(x,y)]) [4,5,6]) [1,2,3]

concat
  [ concatMap (\y -> [(1,y)]) [4,5,6]
  , concatMap (\y -> [(2,y)]) [4,5,6]
  , concatMap (\y -> [(3,y)]) [4,5,6]
  ]

concat
  [ concat [[(1,4)], [(1,5)], [(1,6)]]
  , concat [[(2,4)], [(2,5)], [(2,6)]]
  , concat [[(3,4)], [(3,5)], [(3,6)]]
  ]

concat
  [ [(1,4), (1,5), (1,6)]
  , [(2,4), (2,5), (2,6)]
  , [(3,4), (3,5), (3,6)]
  ]

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

A common and more succinct way of expressing this is with the Applicative instance instead of the Monad instance, using the <$> (fmap) and <*> (ap) operators or liftA2:

(,) <$> [1,2,3] <*> [4,5,6]

liftA2 (,) [1,2,3] [4,5,6]

Upvotes: 7

Related Questions