why can't ghci print the head of the first permutation of the integers, calculated 'selection-style'?

Question

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.

Answer 1

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.

Answer 2

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