tree.erl

%% From "Why Functional Programming Matters" by John Hughes
-module(tree).
-include_lib("eunit/include/eunit.hrl").

-export([fold/4,
         map/2]).

-type label() :: any().
-type tree()  :: {label(), [tree()]}.

fold(_NodeFun, _LabelFun, Acc, []) ->
    Acc;
fold(NodeFun, LabelFun, Acc, [H|T]) ->
    LabelFun(fold(NodeFun, LabelFun, Acc, H), fold(NodeFun, LabelFun, Acc, T));
fold(NodeFun, LabelFun, Acc, {Label, SubTrees}) ->
    NodeFun(Label, fold(NodeFun, LabelFun, Acc, SubTrees)).

map(NodeFun, Tree) ->
    fold(NodeFun, fun cons/2, [], Tree).

cons(Label, Acc) ->
    [Label|Acc].

fold_sum_test() ->
    T1 = {1, [{2, []}, {3, [{4, []}]}]},
    T2 = {1, [{2, [{11, []}]}, {3, [{4, []}]}]},
    Adder = fun(N, Acc) -> N + Acc end,
    Sumtree = fun(Tree) -> fold(Adder, Adder, 0, Tree) end,
    10 = Sumtree(T1),
    21 = Sumtree(T2).

fold_labels_test() ->
    T1 = {1, [{2, []}, {3, [{4, []}]}]},
    Cons = fun(Label, Acc) -> [Label|Acc] end,
    Append = fun(Label, Acc) -> lists:flatten([Label, Acc]) end,
    Labels = fun(Tree) -> fold(Cons, Append, [], Tree) end,
    [1,2,3,4] = Labels(T1).

map_test() ->
    T1 = {1, [{2, []}, {3, [{4, []}]}]},
    AddTwo = fun(Label, Acc) -> {Label + 2, Acc} end,
    {3, [{4, []}, {5, [{6, []}]}]} = map(AddTwo, T1).