Erlang (programming language)/Tutorials/Iterator

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]

---

Iterators

Simple Iterator

I iterator is a function that gives us the next item in a series of items. Iterators are lazy, in that they only give the next item needed and ignore everything after the next. This is very handy when we have potentially an infinitely long list of items but we only want a few items from inside it. Erlang is naturally an eager language so when ever we wish to have lazy evaluation, we need to build an iterator. The first example is a simple iterator hard coded to generate the counting numbers. Here we have used a process and messages to create a non-pure functional program. It is not pure because calling the same function does not return the same value every time. None-the-less, it does get the job done.

 -module (iter).
 -compile (export_all).
 
 start ()  ->
     spawn(iter, counter, [0]).
 
 next(P) ->
	rpc(P,next).
      
 counter(N) ->
       receive
           {From, next}  ->  
                  From ! {self(), N+1},
                  counter (N+1)
       end.
 
 rpc(To, Msg) ->
       To ! {self(), Msg},
       receive
            {To, Answer} -> Answer
       end.

To run it we compile, call start, and call the function next(P).

3> f(), c(iter).
{ok,iter}

4> P = iter:start().
<0.96.0>

5> iter:next(P).    
1

6> iter:next(P).
2

7> iter:next(P).
3

8> iter:next(P).
4

9> iter:next(P).
5

Generic iterator

Let us add some power to the iterator. Giter is a generic iterator. It takes a starting value and a hop function. The hop function generates the next value from the previous value. Now our series can be made of any data type.

-module (giter) .
-compile (export_all) .

% Giter is a generic iterator that takes a starting value and hop function
% The hop function generates the next value from the previous value

start() ->
	Start = 0,
	Hop = fun(N) -> N+2 end,
	create(Start, Hop).

next(P) ->
	rpc(P,next).
	
create(Start, Hop) ->
	spawn(fun() -> hopper(Start, Hop) end).
	
hopper(N, Hop) ->
	receive
		{From, next}  ->  
			NN = Hop(N),
			From ! (NN),
			hopper(NN, Hop)
	end.	

rpc(To, Msg) ->
	To ! {self(), Msg},
	receive
		Answer -> Answer
	end.

Sample output

47> f(), c(giter).    
{ok,giter}

48> P = giter:start().
<0.162.0>

49> giter:next(P).    
2

50> giter:next(P).
4

51> giter:next(P).
6

52> giter:next(P).
8

Iterator for a tree

Example program:

---

-module(test_gb).
-compile(export_all).

start() ->
	W = gb_sets:from_list([1,2,3,4,5]), 
	 
	I0 = gb_sets:iterator(W), 
	{N1,I1} = gb_sets:next(I0), 
	{N2,I2} = gb_sets:next(I1),
	{N3,I3} = gb_sets:next(I2),
	{N4,I4} = gb_sets:next(I3),	
	[ {I0}, {N1,I1}, {N2,I2}, {N3,I3}, {N4,I4} ].

% gb_sets are General Balanced Sets.
%
% gb_sets are stored in general balanced trees.
% A tree is one type of structure we can use an iterator to explore.
% The gb_sets iterator does a left-most-first node traversal, 
% The default iterator for gb_sets visits each node once. It starts
% at maximum depth on the left and removes the left most branches first. 
% After a branch has been fully explored it is trimmed from the 
% iterator. The parent of the branch is also removed.
% Iterators can be used to parse, search, read and sometimes can help one
% to serialize a data structure.
%
% Note:It is important to realize that the gb_sets:next(Iterator_N) is a  
% pure function that returns the next item and the next iterator.
% As such it is a pure function an always returns the same value given
% an input. iter:next(P) and giter:next(P) are impure by comparison.
% Any pure function is theoretically a safer building block than an impure function.
%
% Output of program
% [
% {1, [{2,{1,nil,nil},nil},{3,{2,{1,nil,nil},nil},{5,{4,nil,nil},nil}}]},
% {2, [{3,{2,{1,nil,nil},nil},{5,{4,nil,nil},nil}}]},
% {3, [{4,nil,nil},{5,{4,nil,nil},nil}]},
% {4, [{5,{4,nil,nil},nil}]},
% {5, []}    ]
%
% Each iterator starts with the parent of the next node,
% if it has not been trimmed already.
% Note: the underlined node is the next node.
%           
%     3
%    / \              
%   2   5
%  /   /  
% 1   4          1 is next
% -   
%     3
%    / \
%   2   5
%  /-  /
% 1   4          2 is next
%    
%     3
%    /-\
%   2   5
%  /   /
% 1   4          3 is next and trim the left most tree
%    
%     5
%    /  
%   4            4 is next 
%   -    
%     
%     5          5 is next
%    /-
%   4 
 
%
% Q:Why is everyday Christmas for a computer scientist. 
% A:Because everyday they are likely to be trimming the tree.    

Here is a command line example of the use of gb_sets. 

% --------------------------------------------
W = gb_sets:from_list([1,2,3]).
{3,{2,{1,nil,nil},{3,nil,nil}}}  

127> gb_sets:iterator(W).
[{1,nil,nil},{2,{1,nil,nil},{3,nil,nil}}] 

128> W1 = gb_sets:iterator(W).
[{1,nil,nil},{2,{1,nil,nil},{3,nil,nil}}]

129> gb_sets:next(W1).        
{1,[{2,{1,nil,nil},{3,nil,nil}}]}

130> {Item,W2} = gb_sets:next(W1).
{1,[{2,{1,nil,nil},{3,nil,nil}}]} 

131> {Item2,W3} = gb_sets:next(W2). 
{2,[{3,nil,nil}]}

132> {Item3,W4} = gb_sets:next(W3).
{3,[]}

133> {Item4,W5} = gb_sets:next(W4). 
** exception error: no match of right hand side value none
% ------------------------------------------
Depth first parse of a tree 

  2
 / \
1   3
-  

  2
  -\
    3  

  3
  - 

---