[erlang-questions] Noob questions: Searching a tree

[Richard O'Keefe]

On 10 Dec 2008, at 12:25 am, Edward Stow wrote:

> Hi
>
> Is this a friendly place to ask very simple questions about Erlang and
> functional programming.  I'm learning both at the same time.  For
> example I want to search for a value in the nodes of a tree structure.
> The tree is simply nested lists.  For example
>
> 6> tut1:search(a, [b, [a]]).
> true
> 7> tut1:search(a, [b, [c]]).
> false
> 8> tut1:search(a, [ [a], b]).
> true

The starting point is a question:
"What do you *mean* 'the tree is simply nested lists'?"
Can a "value" ever be a list itself?
If so, does the "value" [a,b] occur in the list [c,a,b]?

Haskell programmers talk about "rose trees"
where a rose tree is a node that has a value and 0 or more subtrees.

is_rose_tree({Value,Children}) ->
     is_rose_tree_list(Children);
is_rose_tree(_) ->
     false.

is_rose_tree_list([Tree|Trees]) ->
     case is_rose_tree(Tree)
       of true  -> is_rose_tree_list(Trees)
        ; false -> false
     end;
is_rose_tree_list([]) ->
     true;
is_rose_tree_list(_) ->
     false.

The nice thing about starting by writing down a recogniser
for a recursive data structure is that computations on it are
often straightforward edits of the recogniser.

So

member_rose_tree(X, {X,_}) -> true;
member_rose_tree(X, {_,L}) -> member_rose_tree_list(X, L).

member_rose_tree_list(X, [T|Ts]) ->
     case member_rose_tree_list(X, T)
       of true  -> true
        ; false -> member_rose_tree_list(X, Ts)
     end;
member_rose_tree_list(_, []) ->
     false.

Note that with this representation a rose tree CAN be a value
in a rose tree, and there is never any doubt about which bits
are values held in the tree and which are substructure.

Of course this is prettier in Haskell:

	data Rose_Tree t = Rose_Tree t [Rose_Tree t]

	x `elem` (Rose_Tree y ts) = x == y || any [x `elem` t | t <- ts]

but the Erlang version is also straightforward.
>
>
> My implementation is: Is this implementation OK or how else would it
> be performed.
>
> -module(tut1).
> -export([search/2]).
>
> %% Search for an element in tree (nested lists)
>
> search(_, []) ->
>    false;
>
> search(A, [A|_]) ->
>    true;
>
> search(A, [H|T]) when list(H), length(H) > 0 ->
>    [H1|T1] = H,
>    search(A, [H1 | [T1 | T]]);
>
> search (A, [_|T]) ->
>    search(A, T).

length/1 is an order N operation.  In this context,
you simply don't need it.  Your third rule could
just be
	search(A, [[H1|T1]|T]) ->
	    search(A, [H1|[T1|T]]);

 From your definition, you ARE willing to accept a list as a value
in a nested list, and you are even willing to accept [a,b] as
one of the values in [c,a,b] --- I would NOT be --- so you could
simplify the whole thing to

	search(A, A) ->
	    true;
	search(A, [H|T]) ->
	    case search(A, H)
	      of true  -> true
	       ; false -> search(A, T)
	    end;
	search(A, _) ->
	    false.

It's not quite the same, but close enough for government work.

I do think that a clearer separation between "payload" and
"structure" would be a good idea, as in the "rose tree" datatype
described above.
>
>
> Question:  I'm not really sure of the semantics of the comma operator
> in the function when clause:
> search(A, [H|T]) when list(H), length(H) > 0 ->

It means "AND".
>
> Can somebody point me towards some relevant documentation.

Either the old Erlang book or Joe's new Erlang book.
The on-line reference manual, which is at
http://www.erlang.org/doc/reference_manual/part_frame.html
describes guards in "6.24 Guard Sequences",
which you can reach from the navigation bar on the left.