3    Lists, Recursion

Solution of Exercise 3

3.1    Family Relations

ancestor( A, X) :- 
    parent( A, X).
ancestor( A, X) :- 
    parent( P, X), 
    ancestor( A, P).

descendant( D, X) :- 
    child( C, X).
descendant( D, X) :- 
    child( C, X), 
    descendant( D, C).
/* also: descendant( D, X) :- ancestor( X, D) */

related( X, Y) :- 
    ancestor( X, Y).
related( X, Y) :- 
    descendant( X, Y).
related( X, Y) :- 
    ancestor( Z, X), ancestor( Z, Y), X \= Y.

Back to example 3.1

3.2    Factorial and Fibonacci

factorial( 0, 1).
factorial( X, Y) :- 
    X > 0, X1 is X - 1, 
    factorial( X1, Y1), Y is X*Y1.

fibo( 0, 1).
fibo( 1, 1).
fibo( X ,Y) :- 
    X > 1, X1 is X-1, X2 is X-2, 
    fibo( X1, Y1), fibo( X2, Y2), Y is Y1 + Y2.

Back to example 3.2

3.3    List Manipulations

member( X, [ X| _]).
member( X, [ _| Y]) :- member( X, Y).

append( [], Y, Y).
append( [ X1| X], Y, [ X1| Z]) :- append( X, Y, Z).

reverse( [], []).
reverse( [ H| T], L) :- reverse( T, R), append( R, [ H], L).

rev( X, Y) :- rev( X, [], Y).        /* accumulator */
rev( [ X1| X], Y0, Y) :- rev( X, [ X1| Y0], Y).
rev( [], Y, Y).

min_list( [ X], X).
min_list( [ X1| Xs], MinX) :- 
    min_list( Xs, MinXs),
    min( X1, MinXs, MinX).

min( X, Y, X) :- X =< Y.
min( X, Y, Y) :- X > Y.

sum( [ X], X).
sum( [ X1| Xs], S1) :- 
    sum( Xs, S), S1 is S + X1.

list_length( [], 0).
list_length( [ _| Xs], L) :- 
    list_length( Xs, Ls), L is Ls + 1.

positive( [], []).
positive( [ X1| X], [ X1| Y]) :- 
    X1 > 0, positive( X, Y).
positive( [ X1| X], Y) :- 
    X1 =< 0, positive( X, Y).

flatten( [], []).
flatten( [ X1| Xs], Y) :- 
    flatten( X1, Y1), flatten( Xs, Ys), 
    append( Y1, Ys, Y).
flatten( X, [ X]) :- not_list( X).
not_list( X) :- X \= [], X \= [ _| _].

set( [], []).
set( [ X1| Xs], Ys) :- 
    member( X1, Xs), set( Xs, Ys).
set( [ X1| Xs], [ X1| Ys]) :- 
    not_member( X1, Xs), set( Xs, Ys).

not_member( _, []).
not_member( X, [ Y| Ys]) :- 
    X \= Y, not_member( X, Ys).

sort_list( [], []).
sort_list( [ X1| Xs], Y) :- 
    sort_list( Xs, Ys), 
    insert( X1, Ys, Y).

insert( X, [], [ X]).
insert( X, [ Y1| Ys], [ X, Y1| Ys]) :- 
    X =< Y1.
insert( X, [ Y1| Ys], [ Y1| Zs]) :- 
    X > Y1, insert( X, Ys, Zs).

Back to example 3.3

3.4    A Complex Bicycle

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

parts( S, Parts) :- 
    structure( S, Cs), 
    parts_c( Cs, Parts).

parts_c( [], []).
parts_c( [ C1| Cs], P) :- 
    parts_c1( C1, P1), 
    parts_c( Cs, P2), 
    append( P1, P2, P).

parts_c1( S, [ S] ) :- element( S).
parts_c1( S, P) :- parts( S, P).

part( S, C) :- 
    structure( S, Cs), 
    member( C, Cs).
part( S, K) :- 
    structure( S, Cs), 
    member( S1, Cs), 
    part( S1, C).

Back to example 3.4