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 .

Project ID: 19442324