FunListClass

Functional List Structures (Semi-Lazy Lists)

I call these semi-lazy because tail is lazy evaluated, but head is not.

Fpiglet defines abstract class !FunList and provides one implementation called LazyList (package: fpilget.lists.structures).

Interface exposed by these structures should not be used directly by the program. These classes serve the following purposes:

• provide (very narrow) interface for implementing List Functions
• server as type for defining type mappings (client programs can use FunList type for type checking).
• these classes are loaded with a Mixin providing old OO style interface (usage of which is discouraged).

FunList exposes this interface used by functional closure library:

abstract class FunList<T> {
    static FunList getEMPTYLIST() {...}
 
    abstract boolean isEmpty()
    abstract T getHead()
    abstract FunList<T> getTail()

    //tailEval returns FunList<T> and <S super T>
    abstract <S> FunList<S> build(S val, Closure tailEval)
}

This allows the tail to be not evaluated during creation a provides mechanism for defining lists recursively.

Calling list.tail evaluates that closure, but until that happens tail is not evaluated. This allows for lazy recursive implementation of methods like map or take.

Lazy recursion defers the computational effort to when the list starts fetching tail and is Stack Overflow safe. Only methods that need to recursively and eagerly evaluate tail (like foldL) need to consider Stack Overflow problems.

NOTE: Shown version uses Java Generics which are not really capable to describe the concept fully. We would need a way to define variance with Generics. I may decide to untype all of that. I hope the class definition is not very confusing. In particular, EMPTYLIST is polymporphic and is effectively a singleton where all lists of all types end... (we would need something like SCALA Nothing class which extends everything to properly define Generics annotations!).

Back to FunList