2

This no doubt moronic question is inspired from What does this list permutations implementation in Haskell exactly do?

Suppose

perms [] = [[]]
perms xxs = [ (y:ys) | ( y, xs ) <- pix xxs , ys <- perms xs ]

--where
pix [] = []
pix ( x:xs ) = ( x , xs ) : [ ( y, x : ys ) | ( y, ys ) <- pix xs ]

Twan van Laarhoven writes "the first thing this function does is pick the first element from the entire list, which is not lazy at all." OK - sure ! But I am confused -

I do not understand why ghci does the following:

*Main> let p = perms [1..]
*Main> let hs = map head p
*Main> take 1 hs
*** Exception: stack overflow

Why can't ghci print [1]?

Sigh...

peter

Comment on Answers:

As I said in my replies to Carsten's answer, I had 'reasoned' that my

*Main> let hs = map head p
*Main> take 1 hs

along with Haskell's laziness, would allow ghci not to calculate the ys in (y:ys) in perms, since the above only 'wanted' the value of the first 'y'; in short I was arguing that I was not really calculating the first term of perms [1..] at all. But, as both Carsten and Reid Barton in effect point out below, laziness is besides the point, and my argument was wrong.

To add to (and, I hope, not mangle) their answers, if 

   ans = take 1 hs

then, because of the list comprehension in the definition of perms,

   ans is in the image of some function from the Cartesian product 
                            (pix [1..]) X perms [2..].

But how do I know that the Cartesian product, the domain of my function, is not the empty set? For, otherwise, ans does not exist... ( i.e., how do I know that the first term of perms[1..] exists? Or, as Reid Barton more succinctly put it, how do I know that perms [1..] is not empty?)

The product is not empty if and only each factor is not empty. I know that the first is not empty (inspection!) - but how do I know that the perms [2..] factor is not empty? Oh - alas, by recursion, I am dead.

Community
  • 1
  • 1
peter a g
  • 165
  • 6
  • As I wrote above, I am indebted to both Carsten and Reid, but I am going to credit Reid's Socratic question... – peter a g Jun 08 '15 at 02:56

2 Answers2

4

well let's see what it has to do (let's use the GHCi debugger)

λ> :break perms
Breakpoint 0 activated...
λ> perms [1..]
Stopped at perms
λ> :step
Stopped at RHS perms xxs
xxs :: [Integer] = 1 : _
λ> :step
Stopped at RHS perms xxs (comprehension)
xxs :: [Integer] = 1 : _
λ> :step
Stopped at pix
λ> :step
Stopped at RHS pix (x:xs)
x :: Integer = 1
xs :: [Integer] = _
λ> :step
Stopped at RHS perms xxs (comprehension)
xs :: [t] = _
λ> :step
Stopped at perms
λ> :step
Stopped at rhs perms xxs
_result :: [[Integer]] = _
xxs :: [Integer] = 2 : _
...

I have tried to translate the position a bit and I removed all but the last _result (there you see that it still not in any WHNF for a list)

The important line is the last one: Can you see that you stepped into the same line as at the beginning but now with the tail of your your infinite list?

That's because you draw ys <- perms xs and if you go on you will see xxs = 3 : _ ...

In the end you will have to traverse all of the list before you get any result - which is of course impossible here.

remarks

take 1 $ perm [1..] will not change anything here as it has to evaluate the result of the above expression to a point where it gets _:_ or [] but as you can see it never does - of course you can check yourself if you add something like

first () = take 1 $ perms [1..]

and then do

:break first
first ()
: step

in ghci - I think it is a fun way to explore a bit - although it can be a bit tedious

answer to your comment

lazy is no easy concept yes and in principle your reasoning is not bad - but both take and map need to deconstruct the given list into something like _:_, now this means that you need see at least the (:) constructor of the list (or [] for that matter) - but here (as I tried to show you with the debug-session) the chunk of the list never reaches this state (its the_result` part) - that is no problem with laziness in Haskell but with your algorithm / the implementation details of your algorithm.

To see that it can work you only need to have a look at permutations in the Data.List - if you try to run your code with this it will work just fine:

λ> import Data.List (permutations)

λ> map head . take 1 $ permutations [1..]
[1]
λ>

so does this:

λ> import Data.List (permutations)

λ> take 1 $ permutations [1..]

but of course this will continue printing till the end of time (memory, whatever)

In case you are interested you can have a look at the implementation of permutations too.

Random Dev
  • 51,810
  • 9
  • 92
  • 119
  • This seems clearly false to both you and Reid Barton below, but I expected, since I Iet hs = map head p, ghci would not need to calculate ys ( i.e. in conjunction with the take 1 hs). I am obviously endowing more omniscience to the word 'lazy' than is warranted. This is what I hadn't understood in the original post cited above. – peter a g Jun 02 '15 at 20:52
  • Namely - I guess this is obvious, but allow me to express my previous comment more explicitly - I thought that laziness would allow ghci NOT to calculate as much of the first term of perms [1..], when calculating take 1 $ map head p, where p = perms [1..] - in short, I guess I think laziness means 'left to right': take 1 => only need to calculate the first term to the right of the $, map head => only need to calculate the (first) y... So laziness means ghci should have printed [1]. But not so! – peter a g Jun 02 '15 at 21:41
2

How do you know that perms [1..] is nonempty?

Reid Barton
  • 14,951
  • 3
  • 39
  • 49
  • 1
    that's not it - this will be easy because if you pattern match on `[1..]` you will get `1 : _` at once – Random Dev Jun 02 '15 at 05:08
  • Maybe I assumed too much of the reader. If you try to show that `perms [1..]` is nonempty, you will soon find yourself needing to know whether `perms [2..]` is nonempty. That is the loop which makes `perms [1..] = _|_`. – Reid Barton Jun 02 '15 at 13:47
  • ok sorry - I thought you was hinting at the pattern-match for `[]` (the empty list - yeah sorry: *nonempty* is something different) - maybe you should (have?) explain(ed) it a bit more – Random Dev Jun 02 '15 at 14:11