Thursday, November 29, 2007

Fun with unfold in Erlang

Fold is one of the most commonly used catamorphisms in functional languages. Erlang has foldl and foldr, which are used very frequently to encapsulate some of the very common patterns of computation as higher order operators instead of using recursion directly. Fold's dual is unfold (anamorphism), which unfortunately does not enjoy an equal popularity amongst functional programmers. While fold is a recursion operator that consumes a collection, it's dual unfold encapsulates a common pattern that produces streams / collections from a single object.

Here is an attempt to implement an unfold in Erlang .. adopting from this thread ..

unfold(Seed, Predicate, Transformer) when is_integer(Seed) ->
    unfold(Seed, Predicate, Transformer, 1).

unfold(Seed, Predicate, Transformer, Incrementor) ->
    unfold(Seed, Predicate, Transformer, Incrementor, []).

unfold(Seed, Predicate, Transformer, Incrementor, Acc) ->
    case Predicate(Seed) of
        true -> unfold(Incrementor(Seed),
        false -> lists:reverse(Acc)

It is a simple implementation that takes a seed, a transformer that transforms a state to an output value, a predicate that tells when to stop and an incrementor that takes us to the next state. And it generates finite collections, though a generic implementation should potentially be able to generate infinite streams as well. But it provides a base for implementing some of the common functions from the Erlang library in a pointfree notation ..

seq(Min, Max, Incr) when Incr > 0, Max >= Min ->
           fun(X) -> X =< Max end,
           fun(X) -> X end,
           fun(X) -> X + Incr end);

seq(Min, Max, Incr) when Incr < 0, Max =< Min ->
           fun(X) -> X >= Max end,
           fun(X) -> X end,
           fun(X) -> X + Incr end).

This one is more powerful. It packs an iteration over multiple lists into one operation and completely abstracts away the iteration from the user.

zip(Ls) ->
           fun(X) -> length(hd(X)) > 0 end,
           fun(Lists) -> [hd(List) || List <- Lists] end,
           fun(Lists) -> [List -- [hd(List)] || List <- Lists] end).

And you can treat them up with String lambdas as well .. of course for this you will need the string lambda library ..

zip(Ls) ->
           lambda("length(hd(_)) > 0"),
           lambda("[hd(List) || List <- _]"),
           lambda("[List -- [hd(List)] || List <- _]")).

seq(Min, Max, Incr) when Incr > 0, Max >= Min ->
           lambda("_ =< Max"),
           lambda("_ + Incr"));

seq(Min, Max, Incr) when Incr > 0, Max >= Min ->
           lambda("_ >= Max"),
           lambda("_ + Incr")).

Why unfold when you can recurse directly ? It provides one more pattern to programming in functional languages. Virtues of catamorphism and anamorphism have been well elucidated in various literature of functional programming. Look here for a detailed discussion on the virtues of unfold and unfold characterization of many well known algorithms.

No comments: