Chapter 3

Slide, Figure 3.1
The . functor must be quoted in gprolog.
Let's not use the dot!

Demo (not in Bratko)
?- [a, b, c] = X.
?- [X, Y, Z] = [a, b, c].
?- [X, b, Z] = [a, Y, c].
?- [[a, b], c] = [X, Y].
?- [a( b), c( X)] = [Z, c( a)].

car and cdr
?- X = [a|[b, c ,d]].
?- X = [a | []].

To extract the car of a list:
?- [Car|_] = [a, b, c, d].

To extract the cdr of a list:
?- [_|Cdr] = [a, b, c, d].

To extract the car and the cdr of a list:
?- [Car|Cdr] = [a, b, c, d].

?- [X|Y] = [a, b, c, d].
?- [X|Y] = [a].

?- X = [a|[b, c, d]].
?- [X|Y] = [a, [b, c, d]].
?- [X|[Y]] = [a, [b, c, d]].

?- X = [a, b, c|[d, e, f]].

?- [X, Y|Z] = [a, b, c].
?- [X, Y|Z] = [a, b, c, d].
?- [X, Y, Z|A] = [a, b, c].
?- [X, Y, Z|A] = [a, b]. % fails

?- [X, Y, a] = [Z, b, Z].

Surprizing
?- [X, Y|Z] = [a|W].

Load ch3.pl

Scroll to third_element
?- third_element([a, b, c, d, e, f], What).
?- third_element([a, b, Y, d, e, f], c).
?- third_element( X, a).

Scroll to my_member
?- my_member( c, [a, b, c, d]).
?- my_member( c, [a, b, c, d, c, e]).
?- my_member( c, X).

Demo
append is built-in.
conc/3 does the same thing
?- append( [a,b], [c,d], X).
?- append( [a,b], Y, [a,b,c,d]).

Slide, Figure 3.2

Scroll to conc
?- conc( [a,b,c], [1,2,3], L).
?- conc( L1, L2, [a,b,c]).

?- conc( Before, [may | After], [jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec]).

?- conc( _, [Month1, may, Month2 | _],
        [jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec]).

Delete three z's and everything that follows them.
?- L1 = [a,b,z,z,c,z,z,z,d,e], conc(L2, [z,z,z | _], L1).

Slide, Figure 3.4
Introduce member concept.
X is a member of [Head|Tail] if it is Head.
X is a member of [Head|Tail] if it is a member of Tail.

Scroll to member1
Note: member/2 is builtin.
?- member1( a, [b,c,d]).
?- member1( a, [b,a,d]).

Scroll to add
?- add( a, [1,2,3], What).

Scroll to del
?- del( a, [a,b,a,a], L1).
?- del( a, L, [1,2,3]).

Scroll to insert
?- insert( a, [1,2,3], L).

Scroll to member2
?- member2( a, [b,c,d]).
?- member2( a, [b,a,d]).
?- del( a, [b,a,d], L).
?- del( a, [b,a,d], _).

Slide, Figure 3.4
Introduce sublist concept.
S is a sublist of L, if you conc anything with L2 to get L,
and if you conc S with anything, you get L2.

Scroll to my_sublist
Note: sublist/2 is builtin.
?- my_sublist( [c,d,e], [a,b,c,d,e,f]).
?- my_sublist( [c,d,e], [a,b,c,d,f]).

Here is how the claues would work with my_sublist( [c,d,e], [a,b,c,d,e,f]).
The first clause by itself produces
?- conc( _, L2, [a,b,c,d,e,f]).
Note the repeated values of L2.
Pick the first one of L2.
The second clause by itself produces
?- conc( [c,d,e], _, [a,b,c,d,e,f]).
which fails.
Backtrack. Pick the second one of L2.
The second clause by itself produces
?- conc( [c,d,e], _, [b,c,d,e,f]).
which fails.
Backtrack. Pick the third one of L2.
The second clause by itself produces
?- conc( [c,d,e], _, [c,d,e,f]).
which succeeds.

Note that these are not the same.
Builtin sublist/2 is better than my_sublist/2.
?- sublist( S, [a,b,c]).
?- my_sublist( S, [a,b,c]).

Slide, Figure 3.5
Recall
?- insert( a, [1,2,3], L).
Introduce permutation concept.
?- my_permutation( [a,b,c], P).
Figure 3.5: [X|L] is a permutation, if, after you permute L, you insert X into it.
Order matters.
You need to get the permutations of the smaller list before you insert X into them.

Scroll to my_permutation

Scroll to my_permutation2
Concept: L is a permutation, if, after you remove X from it, it is a permutation of P.

Slide, The is operator

Slide, Arithmetic operations
?- X is 1+2.
?- X is 5/2, Y is 5//2, Z is 5 mod 2.

?- X = 1+2.
?- 1+2 = X.
?- 1+2 is X.
?- X = '+'( 1, 2).

Slide, comparison operations
?- 4 < 5.
?- 5 < 4.
?- 277 * 77 > 1000.

=:= causes arithmetic evaluation and cannot instantiate

?- 1+2 =:= 2+1.
?- 1+2 = 2+1.
?- 1+A = B+2.

Demo
?- gcd( 20, 32, D).

Recursive definition:
gcd( 20, 32, D)
gcd( 20, 12, D)
gcd( 12, 20, D)
gcd( 12, 8, D)
gcd( 8, 12, D)
gcd( 8, 4, D)
gcd( 4, 8, D)
gcd( 4, 4, D)
D = 4

Scroll to gcd

Scroll to my_length
?- my_length( [a,b,c], N).