[Haskell-beginners] Circular Linked Lists

Dave Bayer bayer at cpw.math.columbia.edu
Tue Feb 3 09:54:46 EST 2009

So the "repeat bars" are there until the first pass through the list  
completes, otherwise cycle would be bottom on infinite lists.  
Thereafter, you're saying that a core dump would reveal a completely  
homogeneous memory representation, just like C code, that one could  
pass through the foreign function interface to C code?

GHC seems to have a special awareness of cyclic lists. For example,  
ghci computes

> (zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)

immediately, as if it knows enough to compute 1000^1000 mod 12, by  
repeated squaring.

On Feb 3, 2009, at 9:17 AM, Brent Yorgey wrote:

> It doesn't?
>  cycle xs = xs' where xs' = xs ++ xs'
> That sure looks like a cyclic data structure to me! xs' references a
> thunk which computes (xs ++ xs'); this thunk, in turn, references
> xs'. cycle is memory-efficient precisely because it *does* actually
> construct a cyclic data structure.

More information about the Beginners mailing list