[Haskell-beginners] Circular Linked Lists

[Dave Bayer]

On Feb 3, 2009, at 10:04 AM, Daniel Fischer wrote:

>> GHC seems to have a special awareness of cyclic lists. For example,
>> ghci computes
>>
>>> (zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)
>
> No, it's that the type of (!!) is [a] -> Int -> a, and 1000^1000 ::  
> Int is 0.
>
>>
>> immediately, as if it knows enough to compute 1000^1000 mod 12, by
>> repeated squaring.

Thanks.

The following takes forever, but it doesn't consume memory:

> Prelude> :m Data.List
> Prelude Data.List> genericIndex (zip (cycle [1..3]) (cycle [1..4]))  
> (1000^1000)

So zip is doing something smart here with cyclic lists.