Deal of the Day

Home » Main » Manning Forums » 2008 » Erlang and OTP in Action

Thread: Chapter 2, pg 84, tail recursive function

Reply to this Thread Reply to this Thread Search Forum Search Forum Back to Thread List Back to Thread List

Permlink Replies: 8 - Pages: 1 - Last Post: Apr 2, 2010 11:53 AM by: kenpratt
sqlrunner

Posts: 4
Registered: 3/29/10
Chapter 2, pg 84, tail recursive function
Posted: Mar 29, 2010 10:40 PM
  Click to reply to this thread Reply

I am having a difficult time understanding this function as built:

tailrev([X | TheRest], Acc) -> tailrev(TheRest, [X | Acc]);

If I read this right, I am adding X to the left side of TheRest and then adding X to the left side of Acc. How does TheRest ever get reduced? Should I not be removing from TheRest into X and then adding X to the left side of ACC?

ddossot


Posts: 206
From: Vancouver, BC
Registered: 8/21/08
Re: Chapter 2, pg 84, tail recursive function
Posted: Mar 29, 2010 11:47 PM   in response to: sqlrunner in response to: sqlrunner
  Click to reply to this thread Reply

This is exactly what the expression does.

First, the function declaration:

tailrev([X | TheRest], Acc)

it puts the list's head in X and the rest of the list in TheRest by pattern matching.

Then the function body:

tailrev(TheRest, [X | Acc]);

which recurse by passing the rest of the list and a new Acc built by prepending X.

HTH
D.

sqlrunner

Posts: 4
Registered: 3/29/10
Re: Chapter 2, pg 84, tail recursive function
Posted: Mar 31, 2010 12:33 PM   in response to: ddossot in response to: ddossot
  Click to reply to this thread Reply

Being brand new to Erlang, but not programming, how can the same expression do two different things?

I understand that [X | Acc] prepends X to Acc using the construct '|'. Why does that act differently in this instance:
[X | TheRest]

Where is the matching? I understand pattern matching in the situation as such:

[X |TheRest] = "This is a test"

ddossot


Posts: 206
From: Vancouver, BC
Registered: 8/21/08
Re: Chapter 2, pg 84, tail recursive function
Posted: Mar 31, 2010 1:46 PM   in response to: sqlrunner in response to: sqlrunner
  Click to reply to this thread Reply

In this situation, the expression performs matching because it is used in a function clause.

D.

sqlrunner

Posts: 4
Registered: 3/29/10
Re: Chapter 2, pg 84, tail recursive function
Posted: Mar 31, 2010 2:08 PM   in response to: ddossot in response to: ddossot
  Click to reply to this thread Reply

Thank you for the explanation. Is there anywhere in the book that explains this special situation? That this becomes pattern matching when used in a function clause? I have looked back through the first few pages and have not seen anything to explain that. Thanks again.

kenpratt

Posts: 4
From: Vancouver, BC
Registered: 3/31/10
Re: Chapter 2, pg 84, tail recursive function
Posted: Mar 31, 2010 4:30 PM   in response to: sqlrunner in response to: sqlrunner
  Click to reply to this thread Reply

Hello,

You might want to give section 2.5.2 (Multiple clauses and pattern matching for choice) another read-through.

Basically, all function arguments in Erlang get pattern matched. So:

tailrev([X | TheRest], Acc) ->
    tailrev(TheRest, [X | Acc]);

Is sort of equivalent to:

tailrev(List, Acc) ->
    [X | TheRest] = List,
    NewAcc = [X | Acc],
    tailrev(TheRest, NewAcc).

The main difference is that when the pattern match is present as an argument, if the match fails, the function clause is skipped and it moves on to check the next clause (if one exists). In my expanded implementation, there is no matching happening on the arguments, so it will gladly accept an empty list and then throw an error on the [X | TheRest] = List match.

Also note that different arguments are tied together. So:

is_same(X, X) when is_integer(X) ->
    true;
is_same(X, Y) when is_integer(X), is_integer(Y) ->
    false.

This function will return true for is_same(2, 2), but false for is_same(2, 3), since the first clause will only pass if both arguments are the same. (The first X binds to the first argument, and the second X matches against the second argument).

Hope that helps,

-Ken

sqlrunner

Posts: 4
Registered: 3/29/10
Re: Chapter 2, pg 84, tail recursive function
Posted: Mar 31, 2010 6:55 PM   in response to: kenpratt in response to: kenpratt
  Click to reply to this thread Reply

It does. Thank you for the expanded explanation, Ken.

anthropoid

Posts: 5
Registered: 3/25/10
Re: Chapter 2, pg 84, tail recursive function
Posted: Apr 1, 2010 7:06 AM   in response to: kenpratt in response to: kenpratt
  Click to reply to this thread Reply

Just a little nitpick:

> is_same(X, X) when is_integer(X) ->
>     true;
> is_same(X, Y) when is_integer(X), is_integer(Y) ->
>     false.
>
> This function will return true for is_same(2, 2), but
> false for is_same(2, 3), since the first clause will
> only pass if both arguments are the same. (The first
> X binds to the first argument, and the second X
> matches against the second argument).

While your explanation is correct, your example has a gotcha in it:

is_same(X, Y) when is_integer(X), is_integer(Y)

I've met too many people who assume that since is_same(X, X) only matches if you use the same value for both arguments, is_same(X, Y) will only match if you use different values. This, of course, isn't true: is_same(X, Y) also matches is_same(2, 2).

I would rewrite your example (for clarity and correctness) as:

is_same(X, X) when is_integer(X) ->
true;
is_same(_, _) ->
false.

kenpratt

Posts: 4
From: Vancouver, BC
Registered: 3/31/10
Re: Chapter 2, pg 84, tail recursive function
Posted: Apr 2, 2010 11:53 AM   in response to: anthropoid in response to: anthropoid
  Click to reply to this thread Reply

Totally true, anthropoid. is_same(X, Y) would also match (2, 2), and only escapes that fate by virtue of coming after the other clause. I should have been more clear that order mattered there.

The reason I assign X and Y to variables is solely so that I can ensure that they are integers. is_same(_, _) is totally valid, but will match any terms. The function I provided will fail if any input other that two integers is provided.

So you could have:

is_same(X, X) when is_integer(X) ->
    true;
is_same(X, Y) when is_integer(X), is_integer(Y) ->
    false;
is_same(_, _) ->
    undefined.

...if you wanted is_same/2 to return true/false for integer inputs and undefined otherwise.

Legend
Gold: 300 + pts
Silver: 100 - 299 pts
Bronze: 25 - 99 pts
Manning Author
Manning Staff
Manning Developmental Editor