[Haskell-beginners] Circular Linked Lists
bayer at cpw.math.columbia.edu
Tue Feb 3 10:15:10 EST 2009
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.
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]))
So zip is doing something smart here with cyclic lists.
More information about the Beginners