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. | |||
|---|---|---|---|
|
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 -