append X Y Zwhich checks if Z is the result of appending the lists X and Y. Use
appendto write another predicate
reverse X Ywhich checks if Y is the result of reversing the order of list X. (Hint:
reverseis recursive. If the tail of X reversed to Z, how could you express Y?)
reverse using a Haskell function. You can use
the built-in list append operator "++". Which do you find more
readable? Which is more powerful? Is there a necessary tradeoff
magic_number 3. magic_number_plus_one X :- magic_number Y, X is Y+1. foo X :- (magic_number 2 => magic_number_plus_one X)What is the result of
magic_number_plus_one X? What is the result of
foo X? What does this say about modularity in Lambda-Prolog?
For example, suppose we want to define our own
type if o -> o -> o -> o. if P C A :- P, C. % true if both P and C are true if P C A :- not P, A. % true if P is false and A is trueThese two definitions can be reordered, as we would expect in a declarative language.
However, this solution is inefficient, because if P
succeeds, then C fails, there is no reason to try the
second rule and check
not P. We can use cuts to indicate
if P C A :- P, !, C. if P C A :- not P, !, A.Now if P succeeds, but C fails, the
ifwill immediately fail. This kind of use is called a
However, we know that Prolog tries rules in the order in which they are declared. Therefore if we ever get to the second rule we know that P is false. So we can omit the check:
if P C A :- P, !, C. if P C A :- A.The remaining cut is now called a
However, red cuts are frowned upon, not only because they violate
declarative style, but because they can inadvertently prevent
multi-way use of a relation. For example, what is wrong with this
min X Y Z, which presumably checks if
Z is the minimum of X and Y?
type min int -> int -> int -> o. min X Y X :- X <= Y, !. min X Y Y.After all,
min 2 5 Zand
min 5 2 Zboth correctly give
Z : 2. How can we fix it?
In Haskell, where there is no backtracking, we can think of cuts being
automatically placed at the equals sign. For example, we could write
if correctly as:
if p c a | p = c if p c a = aThe straightforward translation of our buggy
min x y z | (x < y) && (x == z) = True. min x y z | (y == z) = True.Now it may be more clear why it is broken. What is a simple way to fix it in Haskell?
type repeat o. repeat. repeat :- repeat.The first line means that repeat always succeeds. However, if a failure occurs later, backtracking will cause Prolog to consider the second line, which again succeeds, and so on. Thus
repeatis a kind of infinite choice point, which will evaluate what follows it, over and over again, until that code succeeds. To end the loop, we use a cut, which prevents any more backtracking.
Write a loop which reads all of the lines in a file, i.e. calls
read X until
eof X succeeds.