[mercury-users] Destructive list operations

[Michael Day]

Hi Ralph,

> Yes, you will inevitably have this issue.  If you can abstract away
> from the list type, that would be good.  Destructively updating lists
> is likely to lead to some very hard to find bugs, IMHO.

Probably, yes; most likely bugs that will bite us several years later in 
unrelated code that we'll have trouble tracking down. Nasty.

With that in mind, I've tried writing a pure Mercury implementation of 
map_replace that is optimised for the situation in which no changes are 
made to the list, in which case it will be return as is with no copying 
or allocations. Here is the initial naive implementation:

:- pred map_replace_naive(pred(T, maybe(list(T))), list(T), list(T)).
:- mode map_replace_naive(in(pred(in, out) is det), in, out) is det.

map_replace_naive(_Pred, [], []).
map_replace_naive(Pred, [X|Xs0], Ys) :-
     Pred(X, Res),
     (
         Res = no,
         map_replace_naive(Pred, Xs0, Ys0),
         Ys = [X|Ys0]
     ;
         Res = yes(Xs),
         map_replace_naive(Pred, Xs0, Ys0),
         Ys = Xs ++ Ys0
     ).

Clear specification, but it rebuilds the list pointlessly if no changes 
are made. The smarter implementation builds up a list of changes, then 
applies them to the original list in a separate step:

:- pred map_replace_smart(pred(T, maybe(list(T))), list(T), list(T)).
:- mode map_replace_smart(in(pred(in, out) is det), in, out) is det.

map_replace_smart(Pred, Xs, Ys) :-
     find_replacements(Pred, 0, Xs, [], Rs),
     apply_replacements(0, Rs, Xs, Ys).

:- pred find_replacements(pred(T, maybe(list(T))), int, list(T),
     assoc_list(int, list(T)), assoc_list(int, list(T))).
:- mode find_replacements(in(pred(in, out) is det), in, in,
     in, out) is det.

find_replacements(_Pred, _Index, [], Rs0, Rs) :-
     Rs = reverse(Rs0).

find_replacements(Pred, Index, [X|Xs], Rs0, Rs) :-
     Pred(X, Res),
     (
         Res = no,
         Rs1 = Rs0
     ;
         Res = yes(Ys),
         Rs1 = [Index - Ys|Rs0]
     ),
     find_replacements(Pred, Index + 1, Xs, Rs1, Rs).

:- pred apply_replacements(int, assoc_list(int, list(T)), list(T), list(T)).
:- mode apply_replacements(in, in, in, out) is det.

apply_replacements(_Index, [], Xs, Xs).
apply_replacements(Index, [R|Rs], Xs, Ys) :-
     (
         % this should never happen
         Xs = [],
         Ys = []
     ;
         Xs = [X|Xs0],
         ( if R = Index-NewXs then
             apply_replacements(Index+1, Rs, Xs0, Ys0),
             Ys = NewXs ++ Ys0
         else
             apply_replacements(Index+1, [R|Rs], Xs0, Ys0),
             Ys = [X|Ys0]
         )
     ).

As you can see it's much longer and less clear, with index manipulation 
which I particularly don't like. However, in theory it should be faster, 
if the list is rarely changed, as no copying or allocations will be 
performed in this case.

The worst case is if every element in the list changes, in which case it 
will build up a list of replacements and then apply them one by one to 
rebuild the list again. Perhaps an even smarter solution would be to 
jump out of find_replacements if Pred ever returns yes, and go back to 
the beginning and call map_replace_naive? That would waste time though 
by calling Pred again on the earlier items, for which we know it will 
return no. So probably not.

Any better ideas for how to write this purely in Mercury? Note that I'm 
assuming the replacement list returned by the predicate is fairly short, 
so that the append in apply_replacements is unlikely to be a problem.

Cheers,

Michael

-- 
Print XML with Prince!
http://www.princexml.com
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------