[erlang-questions] "Symmetrical" function

[Boris Okner]

This must be a trivial question, and it's probably more related to
functional programming in general, rather then to Erlang.
I have a function f(A,B) for which f(A,B) is ALWAYS equivalent to
f(B,A). So I call it "symmetrical".
Arguments A and B are patterns, and f is legal for some of
combinations of A and B.
So I have a (long) list of clauses like so:
f(P1, P1) -> expr11;
f(P1, P2) -> expr12;
f(P1, P3) -> expr13;
f(P2, P3) -> expr23;
.......
f(Pm, Pn) -> expr_m_n;

%Other pairs are illegal
f(_, _) ->throw(illegalPairException).

My problem that I don't want to manually write clauses like f(P2,
P1), f(P3, P1) etc., because symmetrical cases would have been already
described (i.e. f(P1, P2) is equivalent to f(P2,P1)).
And I can't use
f(A, B) -> f(B,A)
because "illegal" clause already covers this case.

Thank you for suggestions!

_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions

[Michal Ptaszek]

Maybe try this one:

f(P1, P2) when P1 > P2 ->
f1(P1, P2);
f(P1, P2) ->
f1(P2, P1).

f1(P1, P1) -> expr11;
f1(P1, P2) -> expr12;
f1(P1, P3) -> expr13;
f1(P2, P3) -> expr23;
.......
f1(Pm, Pn) -> expr_m_n;

Best regards,
--
Michal Ptaszek
www.erlang-consulting.com

[Michael Radford]

If the patterns are of some form where you can always determine from the
patterns alone when one of the two arguments is less than the other (and
if you don't care about integer vs. float), you can use the term order:

f (A, B) when A < B -> f_ordered (A, B);
f (A, B) when A >= B -> f_ordered (B, A).

f_ordered (P1, P1) -> expr11;
f_ordered (P1, P2) -> expr12;
...

But that won't work for patterns like:
f ([_], [_,_]) -> 2;

In that case, you could first map each argument to an atom individually
using the same patterns, and then write the list of clauses in terms
of the atoms:

f (A, B) -> fp (p(A), p(B)).

fp (A, B) when A < B -> fp_ordered (A, B);
fp (A, B) when A >= B -> fp_ordered (B, A).

p ([_]) -> p1;
p ([_,_]) -> p2;

fp_ordered (p1, p1) -> expr11;
fp_ordered (p1, p2) -> expr12;
...

Mike

[Hynek Vychodil]

You can try something like this

f(A,B) -> try f1(A,B) catch error:function_clause -> f1(B,A) end.

f1(P1, P1) -> expr11;
f1(P1, P2) -> expr12;
f1(P1, P3) -> expr13;

f1(P2, P3) -> expr23;
.......
f(Pm, Pn) -> expr_m_n.

--
--Hynek (Pichi) Vychodil

Analyze your data in minutes. Share your insights instantly. Thrill your boss.  Be a data hero!
Try Good Data now for free: www.gooddata.com

[Adam Lindberg]

A macro perhaps?

-define(f(Pm, Pn, Expr_m_n), f(Pm, Pn) -> Expr_m_n; f(Pn, Pm) -> f(Pm, Pn)).

So for the clause where the same patter exists twice you would write normally:

f(P1, P1) -> expr11;

And for the other clauses where you need symmetry you would write:

?f(P1, P2, expr12);

Cheers,
Adam

----- "Boris Okner" <boris...@gmail.com> wrote:

[Andras Georgy Bekes]

> Maybe try this one:
>
> f(P1, P2) when P1 > P2 ->
> f1(P1, P2);
> f(P1, P2) ->
> f1(P2, P1).

Bad idea. Comparing might take very long time! With this you can convert
a function with runtime proportional to pattern size to a function with
runtime proportional to parameter size.

Try this:
N=10000000, lists:seq(1,N) > lists:seq(1,N+1).

It will also block the whole VM (one scheduler) for an arbitary time.
See
http://www.erlang.org/pipermail/erlang-questions/2008-March/033838.html
Note that term comparisons like > are BIFs, just like '--'.

I think the right solution for the problem is using macros:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-define(fSYM(P1,P2,Result),
f(P1,P2)->Result;
f(P2,P1)->Result
).

% XOR function
?fSYM(0,1,1);
f(X,X)->0.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Of course you can parametrise the macro with the function name as well.

Georgy

[Richard O'Keefe]

There are two approaches to the problem of
writing a symmetric function, depending on
what you think the problem is.

If the problem is WRITING every clause twice,
then don't. Use the parse tools to take an
annotation such as
-symmentric([{{f,2},{1,2}}]).
% function f/2 is symmetric in arguments 1 and 2
and rewrite
f(P11, P12) -> E1;
...
f(Pn1, Pn2) -> En.
to
f(P12, P11) -> E1;
f(P11, P12) -> E1;
...
f(Pn2, Pn1) -> En;
f(Pn1, Pn2) -> En.

If the problem is HAVING two versions of each
clause, then

f(X, Y) ->
try f'(X, Y)
catch your special exception ->
try f'(Y, X) ->
catch your special exception ->
fake a "no matching clause" exception
end
end.

f'(P11, P12) -> E1;
...
f'(Pn1, Pn2) -> En;
f(_, _) -> throw your special exception.

Note that there is a behavioural difference:
the first version interleaves the swapped clauses with the
originals, while the second puts all the swapped clauses
after the originals. The first approach can be modified
to get the effect of the second, but the second cannot
_easily_ be modified to get the effect of the first.

[Richard O'Keefe]

On 17 Feb 2009, at 4:13 am, David Mercer wrote:
> Why not just catch the function_clause error?

To make life really simple for the reader,
by making it really really obvious that the exception
is *deliberate*.
Also, being somewhat lazy, to avoid the trouble of
checking that it is the *right* function_clause exit.

>> Note that there is a behavioural difference:
>> the first version interleaves the swapped clauses with the
>> originals, while the second puts all the swapped clauses
>> after the originals. The first approach can be modified
>> to get the effect of the second, but the second cannot
>> _easily_ be modified to get the effect of the first.
>

> Can you explain some more. I don't understand the difference.

Suppose we start with

f(a, _) -> 1;
f(b, _) -> 2.

The "preprocessor" approach generates

f(_, a) -> 1;
f(a, _) -> 1;
f(_, b) -> 2;
f(b, _) -> 2.

The "exception" approach generates

f(X, Y) ->
try f1(X, Y)
catch throw:flip ->
try f1(Y, X)
catch throw:flip ->
erlang:error(function_clause, [X,Y])
end
end.

f1(a, _) -> 1;
f1(b, _) -> 2;
f1(_, _) -> throw(flip).

Now what happens if we ask for f(b, a)?
The version that interleaves the rules will return 1;
the version that first tries all the rules as written
and then tries all the rules swapped will return 2.

Since functional languages like ML, Erlang, and even Haskell
adopt a "first match" rule for functions, you cannot expect
re-ordering function rules to work. But if you want to
automatically force a function to be symmetric, you *have*
to mix up two sets of rules somehow. In addition to the
(B,A,B,A,...) and (A,A,...B,B,...) patterns, there are
obviously others like (A,B,A,B,...) and (B,B,...,A,A,...)
and many others. In the absence of guards, detecting when
the order of interleavings might matter would be fairly
straightforward: if {X1,Y1} and {Y2,X2} unify, there is
a problem. (Here, {a,_} and {_,b} unify.) Guards make it
a lot harder to tell.

[Michael Radford]

Richard O'Keefe writes:
> >>Note that there is a behavioural difference:
> >>the first version interleaves the swapped clauses with the
> >>originals, while the second puts all the swapped clauses
> >>after the originals. The first approach can be modified
> >>to get the effect of the second, but the second cannot
> >>_easily_ be modified to get the effect of the first.
> >
> >Can you explain some more. I don't understand the difference.
>
> Suppose we start with
>
> f(a, _) -> 1;
> f(b, _) -> 2.

But you are supposing that the function is not symmetrical.
f(a,b) =/= f(b,a).

For functions that are actually symmetrical, as the original poster was
asking about, either approach should give the same results when either
the upper or lower half of the matrix of clauses is correctly specified.

Mike

[Richard O'Keefe]

On 17 Feb 2009, at 10:41 am, Michael Radford wrote:
> But you are supposing that the function is not symmetrical.
> f(a,b) =/= f(b,a).
>
> For functions that are actually symmetrical, as the original poster
> was
> asking about, either approach should give the same results when either
> the upper or lower half of the matrix of clauses is correctly
> specified.

There is the function that one *wants* to implement,
and there is the code that has been *written* to implement half
of it. Michael Radford is assuming that the actually written
code is correct ("is CORRECTLY specified").
I'm not. Just writing half of the clauses of
a function and then pasting together two suitably adjusted copies
may not give you what you expect.

He is also assuming that one of the halves of the matrix has been
consistently chosen ("either the upper or lower half"). I didn't
say anything in the original message to indicate that this was so.

I don't think we really disagree; it's a theory-vs-practice issue.

[Michael Radford]

Richard O'Keefe writes:
> >But you are supposing that the function is not symmetrical.
> >f(a,b) =/= f(b,a).
> >
> >For functions that are actually symmetrical, as the original poster was
> >asking about, either approach should give the same results when either
> >the upper or lower half of the matrix of clauses is correctly
> >specified.
>
> There is the function that one *wants* to implement,
> and there is the code that has been *written* to implement half
> of it. Michael Radford is assuming that the actually written
> code is correct ("is CORRECTLY specified").
> I'm not. Just writing half of the clauses of
> a function and then pasting together two suitably adjusted copies
> may not give you what you expect.

So you're saying that if your code has bugs, it may not do what you
expect. No argument there. :)

(The original poster was rather emphatic: "I have a function f(A,B) for
which f(A,B) is ALWAYS equivalent to f(B,A)".)

> He is also assuming that one of the halves of the matrix has been
> consistently chosen ("either the upper or lower half"). I didn't
> say anything in the original message to indicate that this was so.

Actually, that assumption was unnecessary. I guess I should have said,
"when at least one of the two possible clauses for each pair of legal
patterns has been correctly specified."

Mike

[Richard O'Keefe]

On 17 Feb 2009, at 11:56 am, Michael Radford wrote:
> (The original poster was rather emphatic: "I have a function f(A,B)
> for
> which f(A,B) is ALWAYS equivalent to f(B,A)".)

That is, the *abstract* function he wanted to implement is symmetric,
but he wanted to know how to halve the work of writing it.

> Actually, that assumption was unnecessary.

Whether that is so depends on how the function is to be implemented.
As several people pointed out, sometimes the answer is

f(X, Y) when X =< Y -> f1(X, Y);
f(X, Y) -> f1(Y, X).

If the f1 clauses are a mix of choices from both sides of the
main diagonal of the matrix, that won't work.

Some obvious questions are "for the intended symmetric f : A x A -> B,
what is #A? And how many clauses would you have for the implemented
f without using any trickery? Why do you think it is feasible to
write half of the function?"

Let's take the intersection of two sorted lists as an example
of a symmetric function:

oi([X|Xs], [Y|Ys]) ->
if X < Y -> oi(Xs, [Y|Ys])
; X > Y -> oi([X|Xs], Ys)
; true -> oi(Xs, Ys)
end;
oi(_, _) ->
[].

Here #A is infinite, the number of clauses is 2, and I don't see
any good way to write half of f.

[Michael Radford]

Richard O'Keefe writes:
> >Actually, that assumption was unnecessary.
>
> Whether that is so depends on how the function is to be implemented.
> As several people pointed out, sometimes the answer is
>
> f(X, Y) when X =< Y -> f1(X, Y);
> f(X, Y) -> f1(Y, X).
>
> If the f1 clauses are a mix of choices from both sides of the
> main diagonal of the matrix, that won't work.

I thought we were talking about the behavior of the "interleaved parse
transform method" vs. the "exception method."

(Of course if f1 is consistent with symmetry, and and it uses either of
those methods to generate the other half of its clauses, its behavior
will be the same, regardless of the method. And f would be redundant.)

I think what you mean is that if you use the above "comparison method"
to generate half the clauses of f, you have to implement the f1 clauses
for which X <= Y. Which is true.

[snip]

> oi([X|Xs], [Y|Ys]) ->
> if X < Y -> oi(Xs, [Y|Ys])
> ; X > Y -> oi([X|Xs], Ys)
> ; true -> oi(Xs, Ys)
> end;
> oi(_, _) ->
> [].
>
> Here #A is infinite, the number of clauses is 2, and I don't see
> any good way to write half of f.

I think you can write just the diagonal...

oi(_, _) -> [].

Mike

[Michael Radford]

Richard O'Keefe writes:
> > oi([X|Xs], [Y|Ys]) ->
> > if X < Y -> oi(Xs, [Y|Ys])
> > ; X > Y -> oi([X|Xs], Ys)
> > ; true -> oi(Xs, Ys)
> > end;
> > oi(_, _) ->
> > [].
> >
> > Here #A is infinite, the number of clauses is 2, and I don't see
> > any good way to write half of f.

Joking aside, your example got me thinking -- and there is another way
to look at the function I think you meant:

oi([], []) -> [];
oi([], [_|_]) -> [];
oi([_|_], []) -> []; % *
oi([X|Xs], [Y|Ys]) when X < Y -> oi(Xs, [Y|Ys]);
oi([X|Xs], [Y|Ys]) when X == Y -> [X | oi(Xs, Ys)];
oi([X|Xs], [Y|Ys]) when X > Y -> oi([X|Xs], Ys). % *

(I think this is the simplest way to write the function without relying
on the evaluation order of clauses.)

Seen this way, you have already managed to write fewer than half of the
mutually exclusive clauses.

Also, note that either the "parse transform" or "exception" methods
would allow half of the off-diagonal clauses to be omitted (*), if only
Erlang had a syntax for guards that could live inside the parameter list:

oi([X (when X < Y) | Xs], [Y|Ys])-> oi(Xs, [Y|Ys]);

Mike

P.S. Wouldn't it be nice if regular matches had the same syntax, e.g.,
X (when X < 3) = f(X)
I think "(when" is never currently legal, so it's even unambiguous.