Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
peter.
%?- peter.
likes(peter, mary).
likes(peter, sophie).
cool(X) :- likes(peter,X).
%?- trace, cool(sophie).
%?- trace, cool(X).
has_wheels(mybike, 2).
has_wheels(mytricycle, 3).
has_wheels(mytoycar, 4).
has_wheels(mycar, 4).
has_motor(mybike).
has_motor(mycar).
car(X) :- has_wheels(X, 4), has_motor(X).
%?- trace, car(Y).
% Cool cool cool, but how can we code with this?
% The answers is for the most part...RECURSION!
nat(zero).
nat(s(X)) :- nat(X).
% add(X, Y, Z) -> X + Y = Z
add(X, zero, X).
add(X, s(Y), s(Z)) :- add(X, Y, Z).
% We see, there is no "return" in Prolog, only predicates.
% For every predicate please state in a comment which parameters
% are input and which are output.
%% List comprehension:
% list e.g. [1,2,3] or [jamie,cersei], empty list = []
% pattern matching with lists:
% [Head|Tail], where Head is an element and Tail is a List!
% Also works with first 2 elements [X1, X2 | T]
append([],L2,L2).
append([H|T],L2,[H|Res]):-
append(T,L2,Res).
% A practical example
% Signature for our problem:
% countN(N : int, L : List[int]) -> int
% counts the occurrences of N in L and returns the result.
% With Prolog-like lists: countN(N, [H | T]) -> int
% L = [2, 3, 5, 2, 7, 1, 2, 2, 5, 9]
% countN(3, L) -> 1
% countN(2, L) -> 4
% countN(8, L) -> 0
% countN(5, L) -> 2
% Delcarative Approach
% countN(N, L) -> res
% res = 0
% for e in L:
% if e == N:
% res += 1
% return res
% Functional / Recursive Approach
% Base Cases:
% countN(N, []) -> return 0
% Recursive Case:
% countN(N, [H | T]) ->
% if N == H
% return countN(N, [T]) + 1
% else
% return countN(N, [T])
% ... in prolog we can't "return", so we need another variable in the predicate
% countN(N, L, RES) the number of occurrences of N in list L
% will be "returned/safed" in RES (Will be in relation with RES)
% Base Cases:
countN(_, [], 0).
%?- trace, countN(2, [], X).
% Recursive Case:
countN(N, [N | T], RES) :- countN(N, T, OLDRES), RES is OLDRES + 1.
countN(N, [M | T], RES) :- not(N=M), countN(N, T, RES).
% Point out: "N" in first line list compr. "is" can be very useful
%?- trace, countN(2, [2], X).