Erlang (programming language)/Tutorials/Folding: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Eric Evers
(New page: Fun with folding Fold is a powerful tool, when you get to know it. lists:foldr(F,S,L) takes three arguments: F is some folding function, S is some starting value, and L is some List that...)
 
imported>Eric Evers
No edit summary
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{subpages}}
Fun with folding
Fun with folding


==Fold==
Fold is also known as Reduce in some circles.
Fold is a powerful tool, when you get to know it. lists:foldr(F,S,L) takes three arguments:
Fold is a powerful tool, when you get to know it. lists:foldr(F,S,L) takes three arguments:
F is some folding function, S is some starting value, and L  is some List that needs folding. Let us do some simple folding. The following fold calculates the lenght of a list. Here the current list item, _C is ignored, and the accumulator, A, counts the number of elements in the list.
F is some folding function, S is some starting value, and L  is some List that needs folding. Let us do some simple folding. The following fold calculates the lenght of a list. Here the current list item, _C is ignored, and the accumulator, A, counts the number of elements in the list.


   lists:foldr( fun(_C,A)->A+1 end, 0, [1,2,3]).
   1> lists:foldr( fun(_C,A)->A+1 end, 0, [1,2,3]).
   3
   3
We could reverse a list with fold if we like.
  2> lists:foldr(fun(C,A)->A++[C] end, [], [a,b,c]).
  [c,b,a]
Or to get fancy we could try a finite difference.
  3> lists:foldr(
    fun(C,{P,A})->{C,[P-C]++A} end,
    {0,[]}, 
    [1,4,9,16]). 
  {1,[3,5,7,-16]}
In example 3, we used a tuple to remember the previous value, P, so we could use it for next difference. The current value, C, and the accumulator, A, is where we build the output.
In example 3, the output is the same length as the input, not much of a reduction.
Fold is a universal function, and can theoretically duplicate any program with a list as input.
Fold is
a function with a limited attention span. We might like to delete the last item, -16, because is has a non-intuitive relation to the source list.
Calculating a continuted calculation with fold seems natural
lists:foldr(fun(C,A)->(A+1)/C end, 1, lists:seq(1,1000)). 
1.718281828459045
The answer appears to be the value e-1,
which we can verify with:
math:exp(1) - 1.
1.718281828459045
==Unfold==
The opposite of fold is unfold.
Unfold takes a seed and builds a list or larger structure, perhaps an infinite stream.
  Argument list of unfold:
  Seed:        The starting state or current state
  Predicate:  fun that is the equivalent of a "While loop test function"
  Transform:  fun that creates current output from current state
  Incrementor: fun that moves to next state from current state
  Acc:        Accumulator is the place we build the output
  %============================================================
 
  -module(fun_utils).
  -compile(export_all).
 
  % erlang unfold code thanks to Debasish Ghosh
 
  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.
 
  % This front-end makes zip behave like the native lists:zip(L1,L2)
  % in the popular erlang lib.
 
  zip(L1,L2) ->
  lists:map(fun(L)->list_to_tuple(L) end, zip([L1,L2])).
 
  % a pure 100% list of lists based zip
 
  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).
 
  %===================================================================
  % Run it
  % 24> c(fun_utils).
  % ok
 
  % 25> fun_utils:zip([1,2,3],[4,5,6]). 
  % [{1,4},{2,5},{3,6}]

Latest revision as of 10:05, 31 August 2009


Fun with folding

Fold

Fold is also known as Reduce in some circles. Fold is a powerful tool, when you get to know it. lists:foldr(F,S,L) takes three arguments: F is some folding function, S is some starting value, and L is some List that needs folding. Let us do some simple folding. The following fold calculates the lenght of a list. Here the current list item, _C is ignored, and the accumulator, A, counts the number of elements in the list.

 1> lists:foldr( fun(_C,A)->A+1 end, 0, [1,2,3]).
 3

We could reverse a list with fold if we like.

 2> lists:foldr(fun(C,A)->A++[C] end, [], [a,b,c]). 
 [c,b,a]

Or to get fancy we could try a finite difference.

 3> lists:foldr(
   fun(C,{P,A})->{C,[P-C]++A} end, 
   {0,[]},   
   [1,4,9,16]).  
 {1,[3,5,7,-16]}

In example 3, we used a tuple to remember the previous value, P, so we could use it for next difference. The current value, C, and the accumulator, A, is where we build the output. In example 3, the output is the same length as the input, not much of a reduction. Fold is a universal function, and can theoretically duplicate any program with a list as input. Fold is a function with a limited attention span. We might like to delete the last item, -16, because is has a non-intuitive relation to the source list.

Calculating a continuted calculation with fold seems natural

lists:foldr(fun(C,A)->(A+1)/C end, 1, lists:seq(1,1000)).  
1.718281828459045

The answer appears to be the value e-1, which we can verify with:

math:exp(1) - 1. 
1.718281828459045

Unfold

The opposite of fold is unfold. Unfold takes a seed and builds a list or larger structure, perhaps an infinite stream.

 Argument list of unfold:
 Seed:        The starting state or current state
 Predicate:   fun that is the equivalent of a "While loop test function"
 Transform:   fun that creates current output from current state
 Incrementor: fun that moves to next state from current state
 Acc:         Accumulator is the place we build the output
 %============================================================
 
 -module(fun_utils).
 -compile(export_all).
 
 % erlang unfold code thanks to Debasish Ghosh
 
 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.
 
 % This front-end makes zip behave like the native lists:zip(L1,L2)
 % in the popular erlang lib. 
 
 zip(L1,L2) ->
 	lists:map(fun(L)->list_to_tuple(L) end, zip([L1,L2])).
 
 % a pure 100% list of lists based zip 
 
 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).
 
 %===================================================================
 % Run it
 % 24> c(fun_utils).
 % ok
 
 % 25> fun_utils:zip([1,2,3],[4,5,6]).  
 % [{1,4},{2,5},{3,6}]