[mercury-users] Destructive map_replace

[Michael Day]

Hi,

I've written a predicate called map_replace, which is attempting to be 
an efficient replacement for using map to transform a list into a list 
of lists and then condensing it back to a single list, when you expect 
that in most cases the list will not be changed.

For example, imagine we wanted to scan a list of ints and replace any 
number 17 with two numbers 99 and 13. We could do it like this:

     Xs = [1, 2, 17, 3, 4],
     Ys = map((func(X) = ( if X = 17 then [99, 13] else [X] )), Xs)
     Zs = condense(Ys)
     % Zs is [1, 2, 99, 13, 4]

However, in the common case there are no 17s in the list, and we're 
allocating three cons cell for each item to eventually get back the 
original list. Given that the compiler can't optimise all this work away 
yet, and we're doing this millions of times, this sucks.

A specialised predicate for doing this is less elegant, but potentially 
could be made to run faster. Here is one solution:

:- pred replace17(int, maybe(list(int))).
:- mode replace17(ui, uo) is det.

replace17(X, Res) :-
     ( if X = 17 then
         Res = yes([99, 13])
     else
         Res = no
     ).

:- pred map_replace(pred(int, maybe(list(int))), list(int), list(int)).
:- mode map_replace(in(pred(ui, uo) is det), di, uo) is det.

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

It looks like the common case when the predicate returns no could be 
optimised into a tail-recursive loop, and the unique modes combined with 
CTGC would allow the reuse of the list skeleton, such that in the case 
where the predicate always returns no the original list should be 
returned exactly as is with no allocations or copies performed at all.

Since the compiler isn't quite up to this level yet I'm going to skip 
straight to the C implementation, and see how that goes.

:- pragma foreign_proc(c,
         map_replace(Pred::in(pred(ui, uo) is det), Xs::di, Ys::uo),
         [may_call_mercury, thread_safe, promise_pure], "

How on earth do I call Pred from within this C code, and what do I have 
to do to avoid destroying the universe if Pred does something strange, 
such as throw an exception?

Best regards,

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
--------------------------------------------------------------------------