Shuffle in prolog

shuffle([], B, B). shuffle([H|A], B, [H|S]) :- shuffle(B, A, S). In this kind of problems, usually the difficult part is not Prolog but identifying the simplest recursive relation that solves it.

Explanation of a Prolog algorithm to append two lists together

First, let’s translate the clauses into something more understandable: append([], List, List) :- !. can be written append([], List2, Result) :- Result = List2, !. and append([H|L1], List2, [H|L3]) :- append(L1, List2, L3). can be written append(List1, List2, Result) :- List1 = [Head1 | Tail1], Result = [HeadR | TailR], Head1 = HeadR, append(Tail1, List2, … Read more

Complexity of ISO Prolog predicates

tl;dr: No and no. Let’s start with sort/2 which ideally would need n ld(n) comparisons. Fine, but how long does one comparison take? Let’s try this out: tails(Es0, [Es0|Ess]) :- Es0 = [_|Es], tails(Es, Ess). tails([],[[]]). call_time(G,T) :- statistics(runtime,[T0|_]), G, statistics(runtime,[T1|_]), T is T1 – T0. | ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L), tails(L,LT), call_time(sort(LT,LTs), … Read more

Safer type tests in Prolog

The testing for types needs to distinguish itself from the traditional “type testing” built-ins that implicitly also test for a sufficient instantiation. So we effectively test only for sufficiently instantiated terms (si). And if they are not sufficiently instantiated, an appropriate error is issued. For a type nn, there is thus a type testing predicate … Read more

Einsteins Riddle Prolog

This site is devoted to solve such puzzles with CLP(FD). But the full power of CLP(FD) is overkill here: your assignment can be solved effectively searching the entire solution space when you have adequately described the constraints. The solution will be composed of 5 houses, where each attribute satisfy all constraints imposed by description. Be … Read more

Using a constrained variable with `length/2`

What’s probably more useful than a slightly less nondeterministic length/2 is a proper list-length constraint. You can find an ECLiPSe implementation of it here, called len/2. With this you get the following behaviour: ?- N :: 1..3, len(Xs, N). N = N{1 .. 3} Xs = [_431|_482] % note it must contain at least one … Read more