A list is either empty or it is composed of a first element (head) and a tail,
which is a list itself. In λProlog, we represent the empty list by the atom
[] and a non-empty list by a term [H|T] where H denotes the head and T
denotes the tail.
Example:
> list.last [1,2,3,4] X.
X = some 4
Example:
> list.second-last [1,2,3,4] X.
Success:
X = some 4
The first element in the list is number 0. Example:
> list.nth [1,2,3,4,5] 2 X.
Success:
X = some 3
The predicate should work with the arguments in any mode.
> list.len [1,2,3,4] X.
Success:
X = 4
> list.len L 4.
Success:
L = [X0, X1, X2, X3]
> list.len L X.
Success:
L = []
X = 0
More? (Y/n)
y
Success:
L = [X0]
X = 1
More? (Y/n)
y
Success:
L = [X0, X1]
X = 2
The predicate should work both ways.
> list.reverse [1,2,3,4] X.
Success:
X = [4,3,2,1]
> list.reverse X [4,3,2,1].
Success:
X = [1,2,3,4]
A palindrome can be read forward or backward; e.g. [“x”,”a”,”m”,”a”,”x”].
Unlike its dynamically typed cousin, λProlog doesn’t support simple heterogeneous
lists. Define a datatype nlist A that allows constructing possibly nested
lists of elements of type A.
An example, using ls for the constructor of nested lists and el to construct
single elements:
NestedList = ls [el 1, ls [el 2, ls [el 3, el 4], el 5]]
Transform a list, possibly holding lists as elements, into a ‘flat’ list by replacing each list with its elements (recursively).
Example:
> my_flatten (ls [el 1, ls [el 2, ls [el 3, el 4], el 5]]) X.
Success:
X = [1, 2, 3, 4, 5]
Hint: Use the predefined predicate pred append i:list A, i:list A, o:list A
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
Example:
> compress [1,1,1,1,2,3,3,1,1,4,5,5,5,5] X.
Success:
X = [1,2,3,1,4,5]
If a list contains repeated elements they should be placed in separate sublists.
Example:
> pack [1,1,1,1,2,3,3,1,1,4,5,5,5,5] X.
Success:
X = [[1,1,1,1],[2],[3,3],[1,1],[4],[5,5,5,5]]
Use the result of problem 1.09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as terms [N,E] where N is the number of duplicates of the element E.
Example:
> encode ["a","a","a","a","b","c","c","a","a","d","e","e","e","e"] X.
Success:
X = [pr 4 "a", pr 1 "b", pr 2 "c", pr 2 "a", pr 1 "d", pr 4 "e"]
Modify the result of problem 1.10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as [N,E] terms.
Note: This will require defining a new datatype.
Example:
TODO fix formatting
> encode-compact ["a","a","a","a","b","c","c","a","a","d","e","e","e","e"] X.
Success:
X = [many 4 "a", one "b", many 2 "c", many 2 "a", one "d", many 4 "e"]
Given a run-length code list generated as specified in problem 1.11. Construct its uncompressed version.
Implement the so-called run-length encoding data compression method directly. I.e. don’t explicitly create the sublists containing the duplicates, as in problem 1.09, but only count them. As in problem 1.11, simplify the result list by replacing the singleton terms [1,X] by X.
Example:
> encode-direct ["a","a","a","a","b","c","c","a","a","d","e","e","e","e"] X.
Success:
X = [many 4 "a", one "b", many 2 "c", many 2 "a", one "d", many 4 "e"]
Example:
> duplicate [1,2,3,4,5] X.
Success:
X = [1,1,2,2,3,3,4,4,5,5]
Example:
> duplicate-n 3 [1,2,3] X.
Success:
X = [1,1,1,2,2,2,3,3,3]
What are the results of the goal:
> duplicate-n 3 X Y.
Example:
> drop [1,2,3,4,5,6,7,8] 3 X.
Success:
X = [1,2,4,5,7,8]
Do not use any predefined predicates.
Example:
> split 3 [1,2,3,4,5,6,7,8,9,10] L1 L2.
Success:
L1 = [1,2,3]
L2 = [4,5,6,7,8,9,10]
Given two indices, I and K, the slice is the list containing the elements between the I’th and K’th element of the original list (both limits included). Start counting the elements with 0.
Example:
> slice 4 8 [1,2,3,4,5,6,7,8,9,10] L.
Success:
L = [5,6,7,8,9]
Examples:
> rotate [1,2,3,4,5,6,7,8] 3 X.
Success:
X = [4,5,6,7,8,1,2,3]
?- rotate [1,2,3,4,5,6,7,8] -2 X.
Success:
X = [7,8,1,2,3,4,5,6]
Hint: Use the predefined predicates pred std.length i:list A, o:int and
pred append i:list A, i:list A, o:list A, as well as the result of problem
1.17.
Example:
> select-nth N [1,2,3,4] X R.
Success:
N = 1
X = 2
R = [1,3,4]
Example:
> insert-at 10 2 [1,2,3,4] L.
Success:
L = [1,2,10,3,4]
Example:
> range 4 9 L.
Success:
L = [4,5,6,7,8,9]
The selected items shall be put into a result list.
It should not include duplicates, unless there are duplicates items in the given list.
Example:
> select-rnd [1,2,3,4,5,6,7,8] 3 L.
Success:
L = [5,4,1]
Of course, your results will be random.
Hint: Use the built-in random number generator random.int/2 and the result of problem 1.20.
The selected numbers shall be put into a result list. Example:
> lotto 6 49 L.
Success:
L = [23,1,17,33,21,37]
Hint: Combine the solutions of problems 1.22 and 1.23.
Example:
> rnd-permu [1,2,3,4,5,6] L.
Success:
L = [4,3,6,1,2,5]
Hint: Use the solution of problem 1.23.
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities (via backtracking).
Example:
> combination(3,[a,b,c,d,e,f],L). L = [a,b,c] ; L = [a,b,d] ; L = [a,b,e] ; …