[Haskell-beginners] Circular Linked Lists

Brent Yorgey byorgey at seas.upenn.edu
Tue Feb 3 10:07:50 EST 2009

On Tue, Feb 03, 2009 at 09:54:46AM -0500, Dave Bayer wrote:
> 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?

I'm not really sure what you mean by "repeat bars".  There really is a
cyclic data structure in memory at all times--it's just that until the
first pass through the list, part of it is a thunk.  After a complete
pass to the list, however, a core dump would indeed reveal something
like what you suggest.

> 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.

I came to the same conclusion as Daniel but it took me a few minutes
of puzzlement.  Besides, it should actually be equal to (2,1), not
(1,1). =)


More information about the Beginners mailing list