Write a predicate digits(L, B, N) that is true if L is a list of digits in base B whose value is N. For example, digits([3, 4, 5], 10, 345) is true. Use a left fold.
Write a predicate foldr(+P, ?L, ?A, ?R) that performs a right fold over the values in L. For example, foldl(P, [x, y, z], A, R) will apply
P(z, A, A1), P(y, A1, A2), P(x, A2, R).
Write a predicate dot(V, W, X) that is true if X is the dot product of vectors V and W, which must have the same dimension. Use a fold.
Write a predicate merge_sort(L, S) that sorts a list L of integers. Use a merge sort.
Write a predicate quicksort(L, S) that sorts a list L of integers. Use a quicksort. Use the first element of L as the pivot element.
Consider binary trees represented as nil (the empty tree) or as t(L, X, R), where L and R are left and right subtrees. Write a predicate height(?T, ?H) that is true if H is the height of the binary tree T. Recall that the height of a tree is defined as the maximal distance from the root to any leaf. Your predicate should be able to generate all possible trees of any height.
Write a predicate flatten(?T, ?L) that flattens a tree, producing a list of values in the tree. For any node t(L, X, R), the values in L should appear before X in the list, and the values in R should appear after X. What is the best-case and worst-case running time for your predicate for a tree with N nodes?
Write a predicate foldr_tree(+P, ?T, ?A, ?R) that performs a right fold of a predicate over all values in a tree.
Write a predicate insert(X, T, T1) that inserts a value X into a binary search tree T, producing a tree T1. If the value X is already in the tree T, then T1 should equal T.
Is it possible to delete values from a tree by running insert() backwards? Why or why not?