3

The code for cycle is as follows

cycle                   :: [a] -> [a]
cycle []                = errorEmptyList "cycle"
cycle xs                = xs' where xs' = xs ++ xs'

I would appreciate an explanation on how the last line works. I feel that it would go off into an infinite recursion without returning or shall I say without printing anything on the screen. I guess my intuition is wrong.

johnson
  • 283
  • 2
  • 9

2 Answers2

4

A list, like basically everything else in Haskell, is lazily evaluated.

Roughly, to make an OOP analogy, you can think of a list as a sort of "iterator object". When queried, it reports on whether there is a next element, and if so, what is such element and what is the tail of the list (this being another "iterator object").

A list defined as

xs = 1 : xs

does not cause non termination. It corresponds to an "iterator object" o that, when queried, answers: "the next element is 1, and the rest of the list can be queried using o". Basically, it returns itself.

This is no different than a list having as a tail a "pointer" to the list itself: a circular list. This takes a constant amount of space.

Appending with ++ works the same:

xs = [1] ++ xs

is identical to the previous list.

In your code, the part

where xs' = xs ++ xs'

crafts a list that starts with xs and then continues with the list itself xs'. Operationally, it is an "iterator object" o that returns, one by one, the elements of xs, and when the last element of xs is returned, it is paired with "you can query the rest of the list at o". Again, a back-pointer, which builds a sort of circular list.

chi
  • 111,837
  • 3
  • 133
  • 218
3

Let's take out the last line separately:

cycle xs                = xs' where xs' = xs ++ xs'

Now, let's try to reduce it:

cycle xs                = xs ++ (xs ++ (xs ++ (xs ++ ...)))

You can see that it expands infinitely. But note that this is not how expressions get reduced in Haskell. Expressions will be reduced to WHNF when it's demanded. So, let's demand some values from cycle function:

ghci > take 1 $ cycle [1..]
[1]

This is how take function is implemented:

take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs

Now, because of pattern matching - the value n will be evaluated first. Since it is already in normal form, no further reduction needs to be done and it will be checked if it is less than or equal to zero. Since the condition fails, it will move on to the second condition. Here, it's second argument will be checked to see if it's equal to []. As usual, haskell will evaluate it to WHNF which will be 1:_. Here _ represents thunk. Now the whole expression will be reduced to 1:take 0 _. Since this value has to be printed in ghci, the whole 1:take 0 _ will be reduced again. Following the similar steps like above again, we will get 1:[] which reduces to [1]. Hence cycle [1,2,3] will get reduced to WHNF in the form (1:xs) and will be ultimately reduced to [1]. But if the cycle function, itself is strict in it's implementation, then it will just go into an infinite loop:

cycle :: NFData a => [a] -> [a]
cycle [] = []
cycle xs = let xs' = xs ++ xs'
           in deepseq xs xs'

You can test that in ghci: 

ghci > take 1 $ cycle [1..]
^CInterrupted.
Sibi
  • 47,472
  • 16
  • 95
  • 163