6.1. Let us go back to our (directed) network of the previous
homework, depicted here. Again, and for completeness, we could
represent this network with the following Prolog statements:
link(a,b).
link(a,c).
link(b,c).
link(b,d).
link(c,d).
link(d,e).
link(d,f).
link(e,f).
link(f,g).
In the previous homework, we defined the (recursive) predicate
`connection(X,Y)` which is true if and only if we can get from some
node `X` to another node `Y` via a series of links. Now the task is
to "augment" this predicate, or add a bit more information to it.
Formulate the appropriate Prolog predicate `path(X,Y,N)` which is true
if and only if there is a path of length `N` from nodes `X` to `Y`.
For example, there is a path of length 2 from `a` to `d`: `a->b->d`,
but also `a->c->d`, and so `path(a,d,2)` gives `true` (two times).
There is also a path of length 3 from `a` to `d`: `a->b->c->d`. Test
this predicate out on the above network to verify whether or not it is
working correctly. Once this is working correctly, note now, that
e.g., `path(a,e,N).` will give multiple answers: (a) what do these
mean this time? (b) How could I use this predicate (i.e., in a query
or a sequence of queries) to determine the shortest path between two
nodes?
6.2. Remember the `take` function of Haskell? It can be defined in
Haskell as:
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
Formulate the appropriate Prolog predicate `take(N,Xs,Ys)` which is
true if and only if `Ys` is what results from taking `N` elements from
`Xs`. That is, `take(3,[1,2,3,4,5],[1,2,3]).` would evaluate to
`true`, or `take(3,[1,2,3,4,5],Ys).` would give `Ys = [1,2,3]`
6.3. The sequence of Pell numbers 0,1,2,5,12,29,70,169,408,.. can be
defined recursively as the sequence of numbers in which the first two
numbers are 0 and 1, and each subsequent number is given by adding 2
times the preceding number to the number which precedes this. This
can be defined in Haskell as:
pell :: Int -> Int
pell 0 = 0
pell 1 = 1
pell n = 2 * pell (n-1) + pell (n-2)
Formulate the appropriate Prolog predicate `pell(N,Pn)` which is true
if and only if `Pn` is the `N`-th term of the sequence of Pell numbers
(note that we start numbering the sequence of Pell numbers with 0).
That is, `pell(8,408).` would evaluate to `true`, or `pell(5,Pn).`
would give `Pn = 29`