functional programming in Prolog

[atheorist]

Once you understand the trick of closure conversion (getting rid of anonymous lambdas by introducing a new data object (the closure) and an apply function consuming the various kinds of closures), and the desugaring rule for Haskell's do-notation, it's fun to apply that trick to tiny elegant snippets of Haskell code, transforming them to slightly inscrutable, but still pretty elegant code in other languages.

Lol means "list of lists" by the way, and the definition of "apply" should probably be scattered around the code, rather than all in one paragraph.



% This is based on the first example in
% Fischer, Kisleyov, and Shan's
% "Purely Functional Lazy Non-deterministic Programming"

% perms(+List, -Lol)
perms(nil, Out) :-
!, return(nil, Out).
perms(cons(X, Xs), Out) :-
!, perms(Xs, R), bind(R, bindHelper1(X), Out).

% apply(+Closure, +List, -Lol)
apply(bindHelper1(X), Ys, Out) :-
!, insert(X, Ys, I), bind(I, bindHelper2, Out).
apply(bindHelper2, Zs, Out) :-
!, return(Zs, Out).
apply(insertWithinHelper(Y), Zs, Out) :-
!, return(cons(Y, Zs), Out).

% insert(+Element, +List, -Lol)
insert(X, Xs, Out) :-
!, return(cons(X, Xs), R), insertWithin(X, Xs, I), mplus(R, I, Out).

% insertWithin(+Element, +List, -Lol)
insertWithin(_X, nil, Out) :-
!, mzero(Out).
insertWithin(X, cons(Y, Ys), Out) :-
!, insert(X, Ys, I), bind(I, insertWithinHelper(Y), Out).

% mzero(-Lol)
mzero(Out) :-
!, Out = nil.

% return(+List, -Lol)
return(L, Out) :-
!, Out = cons(L, nil).

% mplus(+Lol, +Lol, -Lol)
mplus(nil, R, Out) :-
!, Out = R.
mplus(cons(X, Xs), R, Out) :-
!, mplus(Xs, R, MR), Out = cons(X, MR).

% bind(+Lol, +Closure, -Lol)
bind(nil, _F, Out) :-
!, Out = nil.
bind(cons(X, Xs), F, Out) :-
!, apply(F, X, AR), bind(Xs, F, BR), mplus(AR, BR, Out).