Erlang (programming language)/Tutorials/Iterator

Iterators

Simple Iterator

I interator 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 infinitly long list of items but we only want a few items from inside it. Erlang is naturally an eagar 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 everytime. 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 ! (N+1),
			counter (N+1)
	end.

rpc(To, Msg) ->
	To ! {self(), Msg},
	receive
		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.
%
% 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
  - 

---