foldl in prolog

Published: 2011-06-10

David Edelstein

I don’t know how useful this will wind up being for me, but I felt the need to have a foldl type function in prolog. Here’s what I came up with (on swi-prolog)

foldl(Gen, Pred, Template, Bindings, Results) :-
    H=hold(Bindings),
    (   Gen,
        H=hold(BindingsH),
        Template=BindingsH,
        Pred,
        lshift(Template, TemplateNew),
        nb_setarg(1,H,TemplateNew),
        fail
    ;   H=hold([Results|_])
    ).

lshift([_|T], Out) :-
    append(T, [_], Out).

Here are a couple of example invocations. range is a function yielding all numbers between its arguments.

?- foldl(member(Loc, [1,5,9]), append(In,[Loc,space],Out),
        [In,Out], [[],_], R).
R = [1, space, 5, space, 9, space].

?- foldl(range(1,3,L), Out is In+L, [In, Out], [0, _], R).
R = 6.

one drawback I see already is that if Pred is nondet, the last successful value it gives back is what is stored. Some sort of cut is needed…

?- foldl(range(1,3,L), (range(1,5,N), Out is In+L+N), [In, Out], [0, []], R).
R=21.

I have no idea the performance of this, and I also have no idea if there is a better approach available for repeatedly invoking the same goal with different arguments as pulled from a generator type rule.