[erlang-questions] Noob questions: Searching a tree

Bernard Duggan <>
Tue Dec 9 12:59:45 CET 2008


Edward Stow wrote:
> Is this a friendly place to ask very simple questions about Erlang and
> functional programming.  
I hope so - I've only been here a couple of days myself - since I
couldn't find any specific guidelines, I'm just going to assume it is :)
> [snip]
>
> search(A, [H|T]) when list(H), length(H) > 0 ->
>     [H1|T1] = H,
>     search(A, [H1 | [T1 | T]]);
>
> [snip]
>   
Looks like a pretty neat implementation to me.  Of course, trees are
usually used for ordered data, meaning the search can be done faster
than O(n).  What you have here will do a straight linear search, which
would make me wonder what the point of having a tree at all is :)  For
unordered data like you will presumably have, you could do the whole
thing with something like:

search(A, T) ->
    lists:any(fun(E) -> A =:= E end, lists:flatten(T)).

(Unless what you're looking for is itself a list...)

> 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 ->
> Can somebody point me towards some relevant documentation.

The comma operator in guards acts as an 'and' operation so what you have
is equivalent to "list(H) and length(H) > 0".
As a side note, I believe the newer is_list() is preferred these days :)
The full reference manual is at
http://erlang.org/doc/reference_manual/part_frame.html - look at the
section on Guard Sequences.

Also, you could simplify that middle block a bit by changing the
signature to:

search(A, [[H1|T1]|T]) ->

Which does away with the need for both the guard and the assignment on
the first line.

Hope that helps - what I say should be taken with a grain of salt - I've
been tinkering with erlang for over a year now, but I'm kind of new at
giving advice or having anyone who knows what they're talking about look
at my work :)

Cheers,

Bernard






More information about the erlang-questions mailing list