Why does :p freeze in GHCi when I give it this corecursive value?

Question

I've defined the infinite list of infinite lists pathCounts and the infinite list of finite lists pathCounts':

import Data.Function (fix)

nextRow xs = fix $ \ys -> zipWith (+) xs (0:ys)

pathCounts = repeat 1 : map nextRow pathCounts
pathCounts' = map (take 100) pathCounts

Dropping into ghci, if I haven't evaluated either at all, I can use :p on either successfully:

ghci> :p pathCounts
pathCounts = (_t1::[[Integer]])
ghci> :p pathCounts'
pathCounts' = (_t2::[[Integer]])

But if I evaluate pathCounts' partially, then :p freezes on pathCounts while still succeeding on pathCounts':

ghci> head . head $ pathCounts'
1
ghci> :p pathCounts'
pathCounts' = (1 : (_t4::[Integer])) : (_t5::[[Integer]])
ghci> :p pathCounts
^CInterrupted.

I'd expect :p pathCounts to print the same as :p pathCounts', as I've only partially evaluated it. Why isn't it working?

Answer 1

I'd expect :p pathCounts to print the same as :p pathCounts', as I've only partially evaluated it.

Ah, but that's the interesting bit! You have, in fact, fully evaluated the (infinitely long) head of pathCounts. Let's take a slightly smaller example to simplify the discussion:

> let v = repeat 1 :: [Int]
> head v
1
> :p v
^C

I claim that after fully evaluating head v, in fact v is also fully evaluated. This is because, in memory, v is a cyclic singly-linked list. So if you've evaluated enough to know the first element, there is nothing left to evaluate!

The result is that when you ask to :print it, GHC duly attempts to construct a string representing all of the evaluated portion of the structure -- and obviously can't, since it will never stop traversing. (:p simply doesn't have a way to indicate sharing in a structure.)

Compare:

> let x = 1 :: Int; v = (x, x)
> fst v
1
> :p v
(1,1)

Although you have only requested evaluation of the first part of v, in fact all of v has been evaluated here, so :p prints it all -- and doesn't indicate the sharing that exists between the first and second parts.

Now, how come pathCounts' doesn't have the same problem? Well, the thing there is that, although map f (repeat x) = repeat (f x) is a denotationally correct equation, in the GHC implementation of Haskell, that equation isn't operationally sound -- and :p is all about the operational semantics and thumbs its nose at the denotational semantics. In particular, map doesn't (can't) observe the sharing present in repeat x; hence it produces a non-cyclic infinite list. Since map f (repeat x) has less sharing, forcing part of map f (repeat x) doesn't result in an in-memory representation that is as fully evaluated.