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

## Meaning of instantiation mode indicators in arguments of Prolog predicates

Those prefix operators, in this context, represent instantiation modes, i.e. they tell you which arguments should be variables or instantiated when calling the predicate. They also tell you if an argument will be (possibly further) instantiated by the call. They can also be used to tell you that an argument is going to be meta-interpreted … Read more

## list of the values in the leaf nodes of binary tree T

Let’s use a DCG – a Definite Clause Grammar. We start with your original definition: lea(T, L) :- phrase(values(T), L). values(nil) –> []. values(t(X,L,R)) –> [X], values(L), values(R). Now, we need to restrict ourselves to those t/3 that are leaves. One possibility is to enumerate all cases: lea2(T, L) :- phrase(leaves(T), L). leaves(nil) –> []. … Read more

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

## Stack overflow in Prolog DCG grammar rule: how to handle large lists efficiently or lazily

As a general remark you will find more on SO about it under the name library(pio). Also the way to use it cleanly is rather: :- use_module(library(pio)). Your example is way too complex, so I will only consider a slightly simpler case, a newline separated list of numbers: nats([]) –> []. nats([N|Ns]) –> nat(N), newline, … Read more

## What is the logical ‘not’ in Prolog?

In place of not(X = Y) you need to write \+ X = Y or X \= Y. But consider to use dif(X,Y) instead. dif/2 is present in B, SWI, YAP, SICStus. To see the difference: ?- X = b, dif(a, X). X = b. ?- X = b, \+ a = X. X = … Read more