Lambda the Ultimate

I mentioned this in another thread. I think that there is a book on API design desperately waiting to be written, which includes a chapter on modelling with coalgebras followed by a number of sections showing how to represent this in your favourite language.

Number.prototype.upTo = function(end) {
  var start = this.valueOf();
  return function(item) {
    if ( typeof(item) == "undefined" ) return start;
    if ( ++item <= end ) return item;
  }.lazy();
};

So now you can write (1).upTo(10) and get the list of 1,2...10

Note this is not just a simple case, it's a simplified case. Since a_i and b_i are the same in this case, I dropped b_i. In reality BeyondJS lazy generators do return both a_i and b_i as a pair. The upcoming version uses an object of the form:

{ value: ... , context: ... }

where a_i is the value and b_i is the context. Thus the implementation of the foreach (map) list-comprehension becomes very simple:

Lazy.prototype.foreach = function(f) {
  var item;
  while ( item = this.generator(item) )
    f(item.value);
};

(again, the reality is slightly more complex because BeyondJS allows f to interrupt the iteration by returning the false value).

Erik postulates that imperative consumption of a list may be easier for programmers than the functional approach. In a new module, beyondRhino we enable the construction of lazy lists on top of Java iterators. Which would you rather write:

var sum = 0;
while ( iter.hasNext() ) sum += iter.next();

or

var sum = 0;
list.foreach(function(n) { sum += n; });

or

var sum = list.fold("+");

with BeyondJS you can do all three (list is obtained from Beyond.iterator(iter))

I'm a VB.Net programmer (if you can be a C# "programmer", then you can be a VB.Net "programmer"), and I'm already "test-driven" - NUnit works just fine for me, and before that I used VBUnit for VB6.

I actually think that even VB "users" would indeed appreciate a few more simple, expressive and powerful constructs of the kind Erik discusses (Python-style yield for instance). But they mightn't take too kindly to the introduction of a Banana keyword...

unfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p f g b = if p b then [] else (f b):(unfold p f g (g b))

p and g show how to iterate over type b. They are comparable to a standard interfaces for enumerations like Java and C# have.

Can each Haskell type "implement" an enumeration "interface", so unfold can work genericly without the p and g arguments? Or doesn't it work that way?

Can you think of any situation where it might be useful to have separated out the "generator" and the "guard" functions in this way (the implementation with Maybe implicitly combines them)? Perhaps you might wish to generate a curried unfold with the generator already supplied, so that you could supply different terminating conditions according to need - a "do X until..." operator for any X?

unfold' :: b -> (b -> b) -> (b -> a) -> (b -> Bool) -> [a]
unfold' b g f p = if p b then [] else (f b):(unfold' (g b) g f p )


fibGen :: (Int, Int) -> (Int, Int)
fibGen (a, b) = (b, (a + b))


fibRes :: (a, a) -> a
fibRes (a, b) = b


tooBig :: (Int, Int) -> Bool
tooBig (a, b) = (b > 1000)


fibUntil = unfold' (0, 1) fibGen fibRes
fibUntilTooBig = fibUntil tooBig

Btw, I think booleans are grossly overrated.

Well, this way I can define tooBig and muchTooBig, and finish off fibUntil with one or other of them depending on how big I want my fibonacci sequence list to be. With unfoldr, the "generator" and "terminator" are one and the same (and we don't get a separate function to extract a "result" from each seed value, either, which means that we'd end up with a list like [(0,1), (1, 1), (1, 2), (2, 3), (3, 5)...]).

As for booleans, we could always define:

data HasNext = Continue | Stop

Having written this, I see Erik's point a little more clearly too. VB6 programmers were always filling in the blanks in little bits of boilerplate code like:

Do While Not Recordset.EOF
   ' ...do something with the record
   Recordset.MoveNext
Loop

The unfold' form above can be seen as an abstraction of that boilerplate - each of p, f and g corresponds to one of the "slots" you'd fill in. So - setting aside any doubts we might have about the ability of certain poor simian brains to accommodate such advanced wisdom - there is something about unfold that is quite intuitively accessible to programmers (or whatever) used to working in this idiom.

val unfold: isempty:(a -> Bool) -> 
            head:(a -> b) -> 
            tail:(a -> a) -> 
               (a -> List[b])

With the names restored, you can very clearly see the co-algebra that the unfold is co-iterating over. This is one reason I liked named arguments -- it can make the connections between the recursion operators and the algebras of constructors and observors really blindingly explicit.

However, while I think this style of interface works well for an iteration protocol, it doesn't really scale up very well to problems where the datatype has lots of cases, such as abstract syntax trees. I still haven't found any solutions to this that I'm completely happy with yet.

I don't think is that big a deal, though. I disagree with Pseudonym in that I don't think people are crying out for general codata. The reason that unfolds and folds are so convenient is precisely because they are special cases, with powerful invariants coming along for free. Better still, a fold and an unfold composed together can describe any primitive recursive function, and that's a huge class of computations, which describes almost all of the programs I've written.

class Enum a where
    hasNext :: a -> Bool
    current :: a -> b
    next :: a -> a


unfold :: (Enum a) => a -> [b]
unfold a 
    | hasNext a = current a : unfold (next a)
    | otherwise = []

public class Anamorphism {
    public Anamorphism() {
        super();
    }
    public static void main(String[] args) {
        for (Cursor c = fromTo(1, 10); !c.isDone(); c = c.move()) {
            System.out.println(c.item());
        }
    }
    /*
     * fromTo n m = unfoldr next n
     *     where next i = if i>m then Nothing else Just(i,i+1)
     */
    public static Cursor fromTo(int n, final int m) {
        Lambda next = new Lambda() {
            public Object apply(Object obj) {
                Integer i = (Integer) obj;
                if (i.intValue() > m) {
                    return null;
                } else {
                    return new Pair(i, new Integer(i.intValue() + 1));
                }
            }
        };
        return CursorUtils.unfoldRight(next, new Integer(n));
    }
}
interface Cursor {
    public boolean isDone();
    public Object item();
    public Cursor move();
}
interface Lambda {
    public Object apply(Object obj);
}
class Pair {
    public final Object left;
    public final Object right;
    public Pair(Object left, Object right) {
        this.left = left;
        this.right = right;
    }
}
class Break implements Cursor {
    public boolean isDone() {
        return true;
    }
    public Object item() {
        throw new UnsupportedOperationException();
    }
    public Cursor move() {
        throw new UnsupportedOperationException();
    }
}
class CursorUtils {
    public static Cursor cons(final Object value, final Cursor rest) {
        return new Cursor() {
            public boolean isDone() {
                return false;
            }
            public Object item() {
                return value;
            }
            public Cursor move() {
                return rest;
            }
        };
    }
    /*
     * unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
     * unfoldr f b = case (f b) of   
     *                   Nothing -> []
     *                   Just (a,b) -> a : unfoldr f b
     */
    public static Cursor unfoldRight(final Lambda next, final Object value) {
        Object obj = next.apply(value);
        if (obj == null) {
            return new Break();
        } else {
            final Pair pair = (Pair) obj;
            return new Cursor() {
                public boolean isDone() {
                    return false;
                }
                public Object item() {
                    return pair.left;
                }
                public Cursor move() {
                    return unfoldRight(next, pair.right);
                }
            };
        }
    }
}

You don't need fancy existials to hide your representation, you can just use objects (that is, data represented as bundles of function):

type Enum[a] = { 
    hasNext(): Bool
    current(): a
    next(): Enum[a]
}

This is a recursive parametric type (or interface) that describes objects which implement unfolds, or iterators, and it is pretty much what you find in Java and C#. Yield certainly makes creating them eaiser.

But it is interesting that objects can so easily implement lazy computations. That is something that should make lazy functional programmers take note. This is a pretty interesting viewpoint coming from Erik, who has spent a lot of time working on Haskell.

So in ML, you can have datatype declarations like datatype nat = Zero | Succ of nat. This is a recursive type, since nat appears in its definition, and we read this to mean that Zero, Succ(Zero), Succ(Succ(Zero)) are members of the set of values of nat. This seems obvious, except that there's a subtlety: is the expression Succ(Succ(Succ(...))), where the ellipsis indicates infinite repetition, a member of the nat type?

The ML answer is "No, it's not". We treat nat as an inductive definition, and the infinite use of Succ will never bottom out, so it's ruled out. This is called the least fixpoint, or inductive, interpretation. However, you could also say "Yes, it is a member of nat", and permit infinite terms to be part of the set of values the type describes. This is what Haskell does, and is the greatest fixed point or co-inductive interpretation of recursive types.[*] The reason that Haskell says yes and ML says no is that our computers have finite memory, and we can't directly represent infinite data structures. In a lazy language, you can do just a little bit of computation at a time, just as you need it, and this lets you pretend that you have an infinite data structure even if your really don't.

Now, inductive definitions naturally lead to algebraic/recursive programs, and coinductive definitions naturally lead to co-algebraic/co-recursive programs. Since OO languages make coalgebraic definitions easier, it's not a huge surprise that infinite data structures like streams find a natural expression in both OO languages and functional languages with coinductive types.

[*] I'm lying just a little bit here. Haskell also permits non-terminating computations to be a member of a type, which means that it's not quite a coinductive definition. But we can safely ignore that. I also gratuitously speculate that some future functional language could distinguish inductive and co-inductive recursive types, and automatically do the "right thing" order-of-evaluation-wise based on the types of its arguments. That would be really sweet.

the difference is mostly syntax and not semantics:

Agreed. Moreover, Erik Meijer writes on his blog:

In principle there is nothing that prevents special list transformers and comprehensions from being introduced into imperative languages as well. We know how to do it. In fact, as is the case for many other features, Python has already taken the lead in this.

Python has limited syntax for iteration and unlimited classes that behave as iterators.

The less obvious, more expressive example is Smalltalk, which eschews special iteration syntax. This so called "pure" object-oriented language does not have any syntax for iteration. Everything is a message send, even conditionals and iterations.

A simple notation for a "block of code" object and a simple notation for keyword-based parameters/messages give you what you need without hidden machinery or a fixed syntax. Any of Smalltalk's flow of control mechanisms can be defined in Smalltalk itself. And more, to your heart's content.

BTW, Ruby is closer to Smalltalk than Python is to either in this regard.

(If you want links to the details of this then you have to read the blog version 'cause I'm not copying all the links over.)