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?

Marybelle

I'm not sure why it is causing this, but you generate a space leak by calling :p pathCounts that last time. Examine your RAM usage in your system monitor when you call it, mine jumped up to full usage pretty quickly. My guess would be that for whatever reason the partial evaluation of pathCounts' then makes :p pathCounts try to evaluate the repeat 1 term of pathCounts. What happens if you try head . head . tail $ pathCounts'? I would assume you get a space leak again. – Unterwalden

yeah, pathCounts' is a bit of a distraction - I was just trying to demonstrate that :p worked for a partially evaluated infinite list of finite lists. The leak happens if I inspect any part of pathCounts, directly or indirectly. – Marybelle

Simpler example ghci> let pcs = repeat $ repeat 1 :: [Int], ghci> pcs !! 0 !! 0, ghci> :p pcs – Marybelle

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.

Falconiform

btw in common lisp and scheme (I think, at least some dialects), and even prolog, they do have ways to show the circularity in structures... – Radiopaque

@WillNess We have ways to do that in Haskell, too -- it's just that :p doesn't use them. See e.g. vacuum-cairo. – Falconiform

thanks for the link (I knew I saw something like that once!) -- a side note: so this problem here is only with pathCounts's head, by the same reasoning for zipWith as for map... – Radiopaque

@WillNess Aha, thanks for the comment. Now I understand Reid Barton's complaint better. You (and he) are right, of course, and my earlier rebuttal just looks silly now. =D – Falconiform