EN → DE A-AA+ Sitemap Search
Copyright © 2023 Jiri Kriz, www.nosco.ch

# 3    Lists, Recursion

## 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