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