3 Lists, Recursion
Solutions
3.1 Family Relations
Extend the family relations of the Example 1.1 by the following predicates:
ancestor( A, X)
/* A is an ancestor of X */
descendant(D, X)
/* D is a descendant of X */
related( X, Y)
/* X and Y are related */
Solution 3.1
3.2 Factorial and Fibonacci
Implement the following functions as recursive relations:
factorial( N, F)
/* F is the factorial von N */
fibo(N, F)
/* F is the N-th Fibonacci number:
F(n) = F(n-1) + F(n-2), F(0) = F(1) = 1 */
Solution 3.2
3.3 List Manipulations
Implement the following predicates:
member(X, Y)
/* X is an element of the list Y */
append( X, Y, Z)
/* the list Z is the list Y "plus" the list X */
reverse( X, Y) /* Y is the list X in reversed order. Implementation using append */
rev( X, Y)
/* Y is the list X in reversed order. Implementation using accumulated parameters */
min_list( X, Y)
/* Y is the smallest elemente of the list X */
sum( X, S)
/* S = sum of the elements of the list X */
list_length( X, L) /* L is the length of the list X */
positive( X, Y)
/* Y is the list containing the positive elements (numbers) of the list X */
Try also to implement some more difficult predicates:
flatten( X, Y)
/* Y is the list of the atomic elements that occur in the list X or in the sublists of X.
Example:
flatten( [a, [b, [c, d]], a], [a, b, c, d, a]).*/
set( X, Y)
/* Y is the list of unique elements of the list X.
Example:
set( [1, 1, 2], [1,2]) */
sort_list( X, Y)
/* Y is the ordered list of the elements the list X.
Implementation using "Insert sort":
step k: X1, X2, ... Xk are already sorted as Y1, Y2, ... Yk
step k+1: Xk+1 is inserted into Y1, Y2, ... Yk at the correct position. */
Solution 3.3
3.4 A Complex Bicycle
A hierarchical structure can be described by the following facts:
structure( c, [c1, c2, ..., cn])
/* Component c consists of the subcomponents c1, .., cn */
element( c)
/* Component c ist elementary, i.e. it cannot be decomposed further */
Write the following predicates:
parts( C, E)
/* The component C consists of the elementary objects E, E is a list. */
part( C, SubC)
/* SubC is an elementary or composed component, that is contained directly or indirectly in C. */
Check your solution on the example of the bicycle structure:
structure( bicycle, [frame, saddle_area, front_set, wheel, wheel, drive, brakes]).
structure( frame, [top_tube, down_tube, seat_tube, seat_stay, chain_stay]).
structure( saddle_area, [saddle, seat_post]).
structure( front_set, [handlebar_grip, head_tube, schock_absorber, fork]).
structure( wheel, [spokes, hub, rim, tire, valve]).
structure( drive, [pedal, crank_arm, front_derailleur, rear_derailleur, chain]).
structure( brakes, [front_brakes, rear_brakes]).
element( saddle_area).
element( down_tube).
element( seat_tube).
element( seat_stay).
element( chain_stay).
element( saddle).
element( seat_post).
element( handlebar_grip).
element( head_tube).
element( schock_absorber).
element( fork).
element( spokes).
element( hub).
element( rim).
element( tire).
element( valve).
element( pedal).
element( crank_arm).
element( front_derailleur).
element( rear_derailleur).
element( chain).
element( front_brakes).
element( rear_brakes).