Write a Prolog program to implement the predicate
frequencies(L,M), which takes as input a list L and
returns a list of pairs [x,n], where x is an element of
L and n is the number of times x appears in
L. Here are some sample runs in SWI Prolog:
?- frequencies([a,b,a,c,a,c,d,a],L).
L = [[a, 4], [b, 1], [c, 2], [d, 1]]
Yes
?- frequencies([],L).
L = []
Yes
Assume that a binary tree is represented in Prolog using the
function term
tree(X,LeftSubTree,RightSubTree)
where
X is the element at any node and LeftSubTree and
RightSubTree are the left sub-tree and the right sub-tree for
the node respectively.
The term nil is used when there is no left sub-tree
or right-tree. For example, the following function term:
tree(20,tree(10,nil,nil),tree(40,tree(30,nil,nil),nil))
would represent the following binary (search) tree:
20
/ \
10 40
/
30
Recall that a binary search tree is a binary tree in which all the elements
in the left sub-tree of a node are less than the element at the node and
all the elements in the right sub-tree of a node are greater than the
element at the node. Assume that the binary search tree is being used to
represent a set of numbers with no duplicates.
Write Prolog programs for the following predicates:
- smallest(X,T) is true if X is the smallest element
in the binary search tree T.
- member(X,T) is true if X is an element in the
binary search tree T.
- height(T,H) is true if H is the height of the
binary search tree T where height is defined as the length of
the longest path from root to leaf node.
- insert(X,T1,T2) is true if T2 is the tree obtained
by inserting X in the binary search tree T1.
- delete(X,T1,T2) is true if T2 is the tree obtained
by deleting X from the binary search tree T1.