# [mercury-users] Destructive map_replace

Michael Day mikeday at yeslogic.com
Mon Jan 5 18:00:20 AEDT 2009

```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),

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