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

[Peter Ross]

On 03-Sep-1998, Peter Schachte <pets at cs.mu.OZ.AU> wrote:
> 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!
> 

No the point is that it was a bit harder to code up, (not much) but I
haven't done it yet.

> > 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.
> 
Nice.  Now all I have to do is implement it.