Erlang (programming language)/Tutorials/Folding

The metadata subpage is missing. You can start it via filling in this form or by following the instructions that come up after clicking on the [show] link to the right.

Do you see this on PREVIEW? then SAVE! before following a link. To find out more about the use of metadata for the management of Citizendium pages, see CZ:Metadata. You may see this box for one of two reasons. Either: A - New page has been created, or subpages template was added to an existing page B - Cluster move is in progress Click either the A or B link for further instructions. [Feel free to recommend improvements to the text or links in this template] A - For a New Cluster use the following directions Subpages format requires a metadata page. Using the following instructions will complete the process of creating this article's subpages. Click the blue "metadata template" link below to create the page. On the edit page that appears paste in the article's title across from "pagename =". You might also fill out the checklist part of the form. Ignore the rest. For background, see Using the Subpages template Don't worry--you'll get the hang of it right away. Remember to hit Save! the "metadata template". However, you can create articles without subpages. Just delete the {{subpages}} template from the top of this page and this prompt will disappear. :) Don't feel obligated to use subpages, it's more important that you write sentences, which you can always do without writing fancy code. [Feel free to recommend improvements to the text or links in this template] B - For a Cluster Move use the following directions The metadata template should be moved to the new name as the first step. Please revert this move and start by using the Move Cluster link at the top left of the talk page. The name prior to this move can be found at the following link. [Feel free to recommend improvements to the text or links in this template]

---

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 it the unfold. Unfold takes a seed and builds a list or larger structure, perhaps an infinite stream.

 Argument list of unfold.
 Seed:        The starting value or current state
 Predicate:   fun that is the equivalent of a "While loop test function"
 Transform:   fun that creates output from current state
 Incrementor: fun that moves to next state
 Acc:         Accumulator is the place to build 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}]