How are the singleton lists collected and concatenated in this block?-CodePudding

Following up on: Correct desugaring of this Do block

triples = do
   [1..] >>= \z ->
      [1..z] >>= \x ->
         [x..z] >>= \y ->
            guard (x^2   y^2 == z^2) >>= \_ ->
               return (x, y, z)

I am confused on how the singleton lists generated by return(x, y, z) get collected and concatenated in the end.

I now understand that bind is concatenating at each level such that there are no nested braces.

Please correct my interpretation of this block: We take an element of the infinite list and call it z. We take an element of the finite [1..z list and call it x We take an element of the finite [x...z] list and call it y We call guard with the predicate x^2 y^2 == z^2 which will return [] in the case of false or [()] in the case of true We take [()] and call return to wrap the verified triple [(x,y,z)]

What is the order of execution? In other words, is this executing like a nested loop in imperative languages? I am confused on how these singleton lists are collected and flattened.

If I just execute:

   [1..3] >>= \z ->
      [1..z] >>= \x ->
         [x..z] >>= \y ->

I just get a list. So, I am confused on how guard is taking elements from this large list and then generating and collecting singleton lists from this large list.

CodePudding user response：

What is the order of execution?

First, a minor digression. Since Haskell is pure, when we are only concerned by the result, the order of execution does not matter that much. Indeed, when evaluating an expression like f x g y we might compute f x before g y or vice versa and we would get the same result, unlike what happens in languages with side effects.

More in general, you could in principle use different evaluation strategies, and the result would not change. (To be pedantic, for this to hold the evaluation strategy should not get stuck into an infinite recursion or throw exceptions like error "urk".)

That being said, if we care not only about the result, but also about the performance (space & time), then the evaluation strategy becomes more important. foldl' ( ) 0 [1..n] could be evaluated in O(n) space if our strategy fully evaluates the list, but GHC will evaluate it on O(1) space since it will only demand numbers from the list as lazily as possible:

foldl' ( ) 0 [1..n]
= foldl' ( ) (0 1) [2..n]
= foldl' ( ) 1 [2..n]
= foldl' ( ) (1 2) [3..n]
= foldl' ( ) 3 [3..n]
= ...

In other words, is this executing like a nested loop in imperative languages?

Yes, I would say it is roughly the same. Let me make a simpler example. It's hard to fully visualize all the steps, but hopefully you will get the general idea.

[10,20,30] >>= \z -> [z,z 1]
= concat (map (\z -> [z,z 1]) [10,20,30])
= concat (map (\z -> [z,z 1]) (10 : [20,30]))
= concat ([10,11] : map (\z -> [z,z 1]) [20,30])
= 10 : concat ([11] : map (\z -> [z,z 1]) [20,30])
= 10 : 11 : concat ([] : map (\z -> [z,z 1]) [20,30])
= 10 : 11 : concat (map (\z -> [z,z 1]) [20,30])
= 10 : 11 : concat ([20,21] : map (\z -> [z,z 1]) [30])
= 10 : 11 : 20 : concat ([21] : map (\z -> [z,z 1]) [30])
= 10 : 11 : 20 : 21 : concat ([] : map (\z -> [z,z 1]) [30])
= 10 : 11 : 20 : 21 : concat (map (\z -> [z,z 1]) [30])
= 10 : 11 : 20 : 21 : concat (map (\z -> [z,z 1]) [30])
= 10 : 11 : 20 : 21 : concat ([30,31] : map (\z -> [z,z 1]) [])
= 10 : 11 : 20 : 21 : 30 : concat ([31] : map (\z -> [z,z 1]) [])
= 10 : 11 : 20 : 21 : 30 : 31 : concat ([] : map (\z -> [z,z 1]) [])
= 10 : 11 : 20 : 21 : 30 : 31 : concat (map (\z -> [z,z 1]) [])
= 10 : 11 : 20 : 21 : 30 : 31 : concat []
= 10 : 11 : 20 : 21 : 30 : 31 : []

Note how we never generated the full nested list [[10,11],[20,21],[30,31]], but we did effectively run over that by lazily generating each element, step by step as in a nested for loop:

for z in [10,20,30]:
   for x in [z,z 1]:
      yield x

Very roughly, in Haskell lists act more more like a "generator", an object having a .next() method that can be used to demand the next element in the list, as needed. Lists-of-lists similarly allow one to demand (".next()") the first list, which will be an object allowing one to demand the first element (another .next()). If we concatenate this list-of-lists, we never actually store the whole nested list in memory at the same time, but only a single "generator" for the lists-of-lists and a single "generator" for the list (at a time). At any time, only two objects are live, roughly.

I'll now be a bit more pedantic. Above, when I wrote the long computation, I actually cheated a bit allowing myself to write [10,11], [20,21], etc. in the intermediate steps. Actually, only a "generator" for those lists are stored: we do not really generate the whole list before we start concatenating it, but only one element at a time, so everything runs in O(1) space.

Let me conclude saying that understanding Haskell performance is, in my opinion, rather hard in the general case. Performance in strict languages (and imperative ones) is much simpler to understand.

Laziness is very nice and can sometimes make things run in almost surprisingly small space. Also, with purity it allows one to design their code neglecting how it is precisely evaluated and focusing on producing the right output value. On the other hand, evaluating performance often requires one to instead focus on the evaluation, exactly on those aspects that were so convenient to ignore during the initial coding. This requires a bit of experience. It is not easy at first to understand that foldl is almost always a bad idea, while foldl' might be a much better idea in some cases, while foldr might be the right choice for others. When used with an associative and commutative operation like ( ) the result is the same, but the (space) performance is not.