[m-dev.] Re: for review: Accumulator introduction

[Peter Schachte]

On Thu, Sep 03, 1998 at 03:55:31PM +1000, Peter Ross wrote:

> As stated in a comment below, you never need an identity element for
> commutative predicates.  My code recognises this already.

My point is that you don't need an identity even when it's not
commutative, because you can initialize the accumulator to the first
value.  It's easier with an identity, but you don't need one.  It just
needs to be associative.

> > 	min([X|Xs], M) :-
> > 		(   Xs = [] ->
> > 			M = X
> > 		;	min(Xs, M0),
> > 			min2(M0, X, M)
> > 		).
> > 
> > ==>	min([X|Xs], M) :-
> >		min'(Xs, X, M).
> > 
> >	min'(Xs, M0, M) :-
> > 		(   Xs = [] ->
> > 			M = M0
> > 		;	Xs = [X|Xs1],
> > 			min2(M0, X, M1)
> > 			min'(Xs1, M1, M)
> > 		).
> > 
> > but I think that one is probably a bit harder.
> > 
> You are right it is a bit harder.  At the moment I only handle the case
> where choice between the base case and the recursive case is a switch
> (the more common case).

I don't see why if-then-elses should pose a problem.  You *know* it's
a deterministic choice, no need for switch detection!

> funny_rev([], [3]).
> funny_rev([H|T], R) :-
>     funny_rev(T, R0),
>     append(R0, [H], R).
> 
> The 3 should end up at the start of the list.
>
> funny_rev(L, R) :-
>     funny_rev'(L, [3], R).
> 
> funny_rev'([], A, A).
> funny_rev'([H|T], A, R) :-
>     append([H], A, A1),
>     funny_rev'(T, A1, R).
> 
> Now 3 ends up at the end of the list.  This is because append is not
> commutative.

Using infix functional notation, and taking @ to mean append a
singleton (which clearly has no identity), this computes:

	(((3 @ Xn) @ ... X2) @ X1)

which by associativity is the same as

	(3 @ (Xn @ ... (X2 @ X1)))

so:

funny_rev([], [3]).
funny_rev([H|T], R) :-
	funny_rev'(T, [H], R0),
	append([3], R0, R).

funny_rev'([], R, R).
funny_rev'([H|T], R0, R) :-
    append([H], R0, R1).
    funny_rev'(T, R1, R).


No problem.


-- 
Peter Schachte                | When I give food to the poor, they call me a
mailto:pets at cs.mu.OZ.AU       | saint. When I ask why the poor have no food,
http://www.cs.mu.oz.au/~pets/ | they call me a communist.
PGP: finger pets at 128.250.37.3 |     -- Dom Helder Camara