Lazy Haskell
-- xs ++ xs ++ xs ++ ...
-- take 7 (cycle [1, 2, 3]) -> [1, 2, 3, 1, 2, 3, 1]
cycle :: [a] -> [a]
cycle xs = xs' where xs' = xs ++ xs'
Normally, appending a list to itself is an
infinitely-recursive calculation — impossible
within a finite amount of time and memory.
Haskell's solution is to describe a calculation
while calculating as little as possible.
cycle
describes a list infinitely
appended to itself, but only returns as much of
that list as is needed by other functions.
take 7 (cycle [1, 2, 3])
will
calculate only seven parts of an otherwise
infinite, cyclic list.
Non-strict evaluation, or lazy evaluation, is a powerful tool. The semantics, however, of describing or declaring a calculation versus understanding when a calculation will actually evaluate is a tricky business. This complexity is most apparent when implementing non-strict semantics in a strict language.
;; (cycle list) -> <promise>
;; Returns a promise to build a circular list from a finite one.
;; (take 7 (cycle '(1 2 3))) -> '(1 2 3 1 2 3 1)
(define cycle
(lambda (xs)
(let next ([ys xs])
(delay (if (null? ys)
(cons (car xs) (next (cdr xs)))
(cons (car ys) (next (cdr ys))))))))