LazyList.groovy

class LazyList {

    private Closure list

    private LazyList(list) {
        this.list = list
    }

    static LazyList nil() {
        new LazyList( {-> []} )
    }

    LazyList cons(head) {
        new LazyList( {-> [head, list]} )
    }


    def car() {
        def lst = list.call()
        lst ? lst[0] : null
    }

    def cdr() {
        def lst = list.call()
        lst ? new LazyList(lst[1]) : nil()
    }


    def methodMissing(String name, args) {
        def matcher = name =~ /^c([ad]+)r$/
        if (matcher) {
            matcher[0][1].reverse().toList().inject(this) {
                del, cr -> del."c${cr}r"()
            }
        } else {
            throw new MissingMethodException(name, this.class, args)
        }
    }


    boolean isEmpty() {
        list.call() == []
    }

    def fold(n, acc, f) {
        n == 0 || isEmpty() ? acc : cdr().fold(n-1, f.call(acc, car()), f)
    }

    def foldAll(acc, f) {
        isEmpty() ? acc : cdr().foldAll(f.call(acc, car()), f)
    }


    def take(n) {
        fold(n, []) {acc, item -> acc << item}
    }

    def takeAll() {
        foldAll([]) {acc, item -> acc << item}
    }
    
    def toList() {
        takeAll()
    }


    def map(f) {
        isEmpty() ? nil() : new LazyList( {-> [f.call(car()), cdr().map(f).list]} )

        // doesn't work for infinite lists
        //isEmpty() ? nil() : cdr().map(f).cons(f.call(car()))
    }


    def filter(p) {
        isEmpty() ? nil() : p.call(car()) ? new LazyList( {-> [car(), cdr().filter(p).list]} ) : cdr().filter(p)
    }


    private static sequence(int n) {
        {-> [n, sequence(n+1)]}
    }

    static LazyList integers(int n) {
        new LazyList(sequence(n))
    }

    static LazyList naturals() {
        integers(1)
    }


    static def zipWith(alist, blist, f) {
        alist.isEmpty() || blist.isEmpty() ? nil() : new LazyList( {-> [f.call(alist.car(), blist.car()), zipWith(alist.cdr(), blist.cdr(), f).list]} )
    }
}

test.groovy

def lazylist = LazyList.nil().cons(4).cons(3).cons(2).cons(1)


assert lazylist.car() == 1
assert lazylist.cdr().car() == 2


assert lazylist.caddr() == 3

def lmn = LazyList.nil().cons('N').cons('M').cons('L')
def almnz = LazyList.nil().cons('Z').cons(lmn).cons('A')
assert almnz.cadadr() == 'M'


ArrayList.metaClass.lazy = {
    -> delegate.reverse().inject(LazyList.nil()) {list, item -> list.cons(item)}
}
def lazyfied = ['A', ['L','M','N'].lazy(), 'Z'].lazy()
assert lazyfied.cadadr() == 'M'


assert [1,2,3,4,5].lazy().foldAll(0){ acc, i -> acc + i } == 15
assert [1,2,3,4,5].lazy().fold(3, 1){ acc, i -> acc * i } == 6


assert [1,2,3,4,5].lazy().takeAll() == [1,2,3,4,5]
assert [1,2,3,4,5].lazy().take(3) == [1,2,3]


assert [1,2,3,4,5].lazy().map{ 2 * it }.take(3) == [2,4,6]


assert [1,2,3,4,5].lazy().filter{ 2 < it }.take(2) == [3,4]


assert [1,2,3,0,6].lazy().map{ 6 / it }.take(3) == [6,3,2]

try {
    [1,2,3,0,6].lazy().map{ 6 / it }.takeAll()
}
catch (Exception e) {
    assert e instanceof ArithmeticException
}


def naturals = LazyList.naturals()
assert naturals.take(3) == [1,2,3]

def evens = naturals.map { 2 * it }
assert evens.take(3) == [2,4,6]

def odds = naturals.filter { it % 2 == 1 }
assert odds.take(3) == [1,3,5]

assert naturals.cadddddddddr() == 10

def nonnegatives = naturals.cons(0)
assert nonnegatives.cadr() == 1

assert LazyList.zipWith(evens, odds){ x, y -> x * y }.take(4) == [2,12,30,56]