Cons <- function(head, tail)
    structure(list(head = head, tail = function() tail),
              class = "LazyList")

Head <- function(x) x$head
Tail <- function(x) x$tail()
print.LazyList <- function(x, ...) {
    cat(paste("<", Head(x), ", ... >\n"))
}
intList <- function(i) Cons(i, intList(i+1))

Iterates <- function(x, f) {
    iter <- function(x, f) {
        y <- f(x)
        Cons(y, iter(y, f))
    }
    Cons(x, iter(x, f))
}
    
#**** as.List
FromList <- function(x) {
    v <- NULL;
    for (i in rev(as.list(x)))
        v <- do.call("Cons", list(i, v))
    v
}

#**** fix Take for finite list

Append <- function(x, y) {
#**** coerce t list??
    if (is.null(x))
        y
    else
#**** force eval of y to avoid buildup of nested promises?
        Cons(Head(x), Append(Tail(x), y))
}

Repeat <- function(x)
    Append(x, Repeat(x))
Elt <- function(x, n) {
    if (n <= 0)
        NULL
    else {
        while (n > 1 && ! is.null(x)) {
            n <- n - 1
            x <- Tail(x)
        }
        if (is.null(x))
            NULL
        else
            Head(x)
    }
}

Take <- function(n, x) {
    if (n <= 0)
        NULL
    else
        sapply(1:n, function(i) { v <- Head(x); x <<- Tail(x); v })
}

Drop <- function(n, x) {
    if (n > 0)
        for (i in 1:n)
            x <- Tail(x)
    x
}

TakeWhile <- function(test, x) {
    y <- x
    n <- 0
    while (! is.null(x) && test(Head(x))) {
        n <- n + 1
        x <- Tail(x)
    }
    Take(n, y)
}

DropWhile <- function(test, x) {
    while (! is.null(x) && test(Head(x)))
        x <- Tail(x)
    x
}
Filter <- function(x, test) {
    if (test(Head(x)))
        Cons(Head(x), Filter(Tail(x), test))
    else
        Filter(Tail(x), test)
}

Filter <- function(x, test) {
    while (! test(Head(x)))
        x <- Tail(x)
    Cons(Head(x), Filter(Tail(x), test))
}
Filter <- function(x, test) {
    while (! is.null(x) && ! test(Head(x)))
        x <- Tail(x)
    if (is.null(x))
        NULL
    else
        Cons(Head(x), Filter(Tail(x), test))
}

Map <- function(x, fun) {
    if (is.null(x))
        NULL
    else
        Cons(fun(Head(x)), Map(Tail(x), fun))
}
Interleave <- function(x, y) {
    if (is.null(x))
        y
    else if (is.null(y))
        x
    else
        Cons(Head(x), Interleave(y, Tail(x)))
}

Zip <- function(x, y) {
    if (is.null(x) || is.null(y))
        NULL
    else
        Cons(Head(x), Cons(Head(y), Zip(Tail(x), Tail(y))))
}