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

corecursion, ghci, haskell

Solution

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.

Problem

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?

Original source