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),
                       Predicate,
                       Transformer,
                       Incrementor,
                       [Transformer(Seed)|Acc]);
        false -> lists:reverse(Acc)
    end.



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 ->
    unfold(Min,
           fun(X) -> X =< Max end,
           fun(X) -> X end,
           fun(X) -> X + Incr end);

seq(Min, Max, Incr) when Incr < 0, Max =< Min ->
    unfold(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) ->
    unfold(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) ->
    unfold(Ls,
           lambda("length(hd(_)) > 0"),
           lambda("[hd(List) || List <- _]"),
           lambda("[List -- [hd(List)] || List <- _]")).

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

seq(Min, Max, Incr) when Incr > 0, Max >= Min ->
    unfold(Min,
           lambda("_ >= Max"),
           lambda("_"),
           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.

1 comment:

Anonymous said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,按摩棒,震動按摩棒,微調按摩棒,情趣按摩棒,逼真按摩棒,G點,跳蛋,跳蛋,跳蛋,性感內衣,飛機杯,充氣娃娃,情趣娃娃,角色扮演,性感睡衣,SM,潤滑液,威而柔,香水,精油,芳香精油,自慰套,自慰,性感吊帶襪,吊帶襪,情趣用品加盟AIO交友愛情館,情人歡愉用品,美女視訊,情色交友,視訊交友,辣妹視訊,美女交友,嘟嘟成人網,成人網站,A片,A片下載,免費A片,免費A片下載愛情公寓,情色,舊情人,情色貼圖,情色文學,情色交友,色情聊天室,色情小說,一葉情貼圖片區,情色小說,色情,色情遊戲,情色視訊,情色電影,aio交友愛情館,色情a片,一夜情,辣妹視訊,視訊聊天室,免費視訊聊天,免費視訊,視訊,視訊美女,美女視訊,視訊交友,視訊聊天,免費視訊聊天室,情人視訊網,影音視訊聊天室,視訊交友90739,成人影片,成人交友,美女交友,微風成人,嘟嘟成人網,成人貼圖,成人電影,A片,豆豆聊天室,聊天室,UT聊天室,尋夢園聊天室,男同志聊天室,UT男同志聊天室,聊天室尋夢園,080聊天室,080苗栗人聊天室,6K聊天室,女同志聊天室,小高聊天室,上班族聊天室,080中部人聊天室,同志聊天室,聊天室交友,中部人聊天室,成人聊天室,一夜情聊天室,情色聊天室,寄情築園小遊戲情境坊歡愉用品,情境坊歡愉用品,情趣用品,成人網站,情人節禮物,情人節,AIO交友愛情館,情色,情色貼圖,情色文學,情色交友,色情聊天室,色情小說,七夕情人節,色情,情色電影,色情網站,辣妹視訊,視訊聊天室,情色視訊,免費視訊聊天,美女視訊,視訊美女,美女交友,美女,情色交友,成人交友,自拍,本土自拍,情人視訊網,視訊交友90739,生日禮物,情色論壇,正妹牆,免費A片下載,AV女優,成人影片,色情A片,成人論壇,情趣,免費成人影片,成人電影,成人影城,愛情公寓,成人影片,保險套,舊情人,微風成人,成人,成人遊戲,成人光碟,色情遊戲,跳蛋,按摩棒,一夜情,男同志聊天室,肛交,口交,性交,援交,免費視訊交友,視訊交友,一葉情貼圖片區,性愛,視訊,視訊聊天,A片,A片下載,免費A片,嘟嘟成人網,寄情築園小遊戲,女同志聊天室,免費視訊聊天室,一夜情聊天室,聊天室