3    Listen, Rekursion

Lösung der Aufgaben

3.1    Familienbeziehungen

vorfahr( VF, M) :- 
    elter( VF, M).
vorfahr( VF, M) :- 
    elter( Elter, M), 
    vorfahr( VF, Elter).

nachkomme( NK, M) :- 
    kind( NK, M).
nachkomme( NK, M) :- 
    kind( Kind, M), 
    nachkomme( NK, Kind).
/* auch: nachkomme( NK, M) :- 
    vorfahr( M, NK) */

verwandt( X, Y) :- 
    vorfahr( X, Y).
verwandt( X, Y) :- 
    nachkomme( X, Y).
verwandt( X, Y) :- 
    vorfahr( Z, X), 
    vorfahr( Z, Y), 
    X \= Y.

Back to example 3.1

3.2    Fakultät & Fibonacci

fakultaet( 0, 1).
fakultaet( X, Y) :- 
    X > 0, 
    X1 is X - 1, 
    fakultaet( 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    Listenmanipulation

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

/* accumulator */
rev( X, Y) :- 
    rev( X, [], Y). 
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.

length( [], 0).
length( [ X| Xs], L) :- 
    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( X, []).
not_member( X, [ Y| Ys]) :- 
    X \= Y, 
    not_member( X, Ys).

sort( [], []).
sort( [ X1| Xs], Y) :- 
    sort( 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    Ein komplexes Velo

teile( S, Teile) :- 
    struktur( S, Ks), 
    teile_k( Ks, Teile).

teile_k( [], []).
teile_k( [ K1| Ks], T) :- 
    teile_k1( K1, T1), 
    teile_k( Ks, T2), 
    append( T1, T2, T).

teile_k1( S, [ S] ) :- 
    element( S).
teile_k1( S, T ) :- 
    teile( S, T).

teil( S, K) :- 
    struktur( S, Ks), 
    member( K, Ks).
teil( S, K) :- 
     struktur( S, Ks), 
     member( S1, Ks), 
     teil( S1, K).

Back to example 3.4