Copyright © 2023 Jiri Kriz,

3    Lists, Recursion


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. 
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. 
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).

Solution 3.4