Prolog Haskell Predicates

Very simple haskell prolog predicates

Part I: Binary Trees

--------------------

tree(+Tree)

tree/1 succeeds when its argument is an instantiated binary tree. A binary

tree may be tip (representing an empty tree) or bin(Left,Here,Right), where

Left and Right are binary trees and Here may be anything (including an

uninstantiated variable).

tree/1 should be deterministic when its argument is a complete tree

structure (i.e., with only the Here values possibly being variables).

?- tree(bin(tip,X,tip)).

true.

?- tree(bin(tip,1,2)).

false.

?- tree(bin(bin(tip,1,tip),0,bin(tip,not_an_integer,tip))).

true.

symmetric(+Tree)

symmetric/1 succeeds when its argument is an instantiated binary tree that

is symmetric: that is, switching the left and right children of every node

results in an identical tree.

?- symmetric(17).

false.

?- symmetric(tip).

true.

?- symmetric(bin(bin(tip,1,tip), 0, bin(tip,1,tip))).

true.

?- symmetric(bin(bin(tip,X,tip), Y, bin(tip,atom,tip))).

X = atom.

?- symmetric(bin(bin(tip,X,tip), Y, bin(tip,Z,tip))).

X = Z.

height(+Tree, ?Height)

height/2 holds if Tree is a binary tree with height Height, meaning that the

longest path from a root to a leaf has length Height. We will assume that

an empty tree (tip) has height 0.

height/2 should fail if Tree is not a binary tree, or Height is negative.

?- height(bin(tip,X,tip), 1).

true.

?- height(bin(bin(tip, X, tip), Y, tip), N).

N = 2.

perfect(?Tree, ?Height)

perfect/2 holds if Tree is a perfect binary tree with height Height. In a

perfect binary tree, every node has either 2 or 0 children, and every path

from the root to a leaf has the same length.

This predicate must be usable in four modes:

1. perfect(+Tree, +Height) is semi-deterministic

succeeds if Tree is perfect and has height Height

?- perfect(bin(tip,X,tip), 1).

true.

?- perfect(tip, 1).

false.

2. perfect(+Tree, -Height) is semi-deterministic

succeeds if Tree is perfect, and instantiates Height with its height

?- perfect(bin(tip,X,tip), N).

N = 1.

?- perfect(bin(bin(tip,X,tip),Y,tip), N).

false.

3. perfect(-Tree, +Height) is deterministic

instantiates Tree with a perfect binary tree of height Height.

Note: behavior is undetermined if Height is negative

?- perfect(T, 0).

T = tip.

?- perfect(bin(tip,X,tip), N).

N = 1.

4. perfect(?Tree, ?Height) is non-deterministic

succeeds when Tree and Height can be instantiated such that Tree is a

perfect binary tree of height Height.

?- perfect(T, N).

T = tip,

N = 0 ;

T = bin(tip,X,tip),

N = 1 .

?- perfect(bin(L,X,R), N).

L = R, R = tip,

N = 1 ;

L = bin(tip, _1, tip),

R = bin(tip, _2, tip),

N = 2 .

Prolog

Project ID: #19442324

About the project