Computing-with-Logic-Notes(Structures Lists Difference Lists) Part4

Conditional Evaluation

Conditional operator (the if-then-else construct in Prolog):
- if A then B else C is written as (A -> B ; C)
  - To Prolog this means:
    
    Try A.
    
    If you can prove it, go on to prove B and ignore C.
    
    If A fails, however, go on to prove C ignoring B.
    
    e.g.
    1
    2
    3
    4
    5
    max(X, Y, Z) :-
    ( X =< Y
    -> Z = Y
    ; Z = X
    ).
Consider the computation of n! (i.e. the factorial of n)

factorial(N, F) :- …
- N is the input parameter; and F is the output parameter.
- The body of the rule species how the output is related to the input.
  - For factorial, there are two cases:
    
    N <= 0 and N > 0
    - if N <= 0, then F = 1
    - if N > 0, then F = N * factorial(N-1)
    1
    2
    3
    4
    5
    6
    7
    factorial(N, F) :-
    (N > 0
    -> N1 is N - 1,
    factorial(N1, F1),
    F is N * F1
    ; F = 1
    ).

Imperative Features

Other imperative features:

we can think of prolog rules as imperative programs with backtracking

program :-
    member(X, [1, 2, 3, 4]),
    write(X),
    nl,
    fail;
    true.

?- program. % prints all solutions

fail: always fails, causes backtracking.
!: the cut operator, prevents other rules from matching.

Arithmetic Operators

Integer/Floating Point operators:
- +
- -
- *
- /
- Automatic detection of Integer/Floating Point
Interger operator:
- mod
- // (integer division)
Comparison operators:
- <
- >
- =<
- >=
- Expr1 =:= Expr2 (succeeds if expression Expr1 evaluates to a number equal to Expr2)
- Expr1 =\= Expr2 (succeeds if expression Expr1 evaluates to a number non-equal to Expr2)

Programming with Lists

quicksort:

quicksort([], []).
quicksort([X0 | Xs], Ys) :-
    partition(X0, Xs, Ls, Gs),
    quicksort(Ls, Ys1),
    quicksort(Gs, Ys2),
    append(Ys1, [X0 | Ys2], Ys).
    
partition(Pivot, [], [], []).
partition(Pivot, [X|Xs], [X|Ys], Zs) :-
    X <= Pivot,
    % can add a '!', for cut
    partition(Pivot, Xs, Ys, Zs).
partition(Pivot, [X|Xs], Ys, [X|Zs]) :-
    x > Pivot,
    partition(Pivot, Xs, Ys, Zs).

We want to define delete/3, to remove a given element from a list (called select/3 in XSB’s basic library)
- delete(2, [1, 2, 3], X) should succeed with X = [1, 3]
- delete(X, [1, 2, 3], [1, 3]) should succeed with X = 2
- delete(2, X, [1, 3]) should succeed with X = [2, 1, 3]; X = [1, 2, 3]; X = [1, 3, 2]; fail
- Algorithm:
  - When X is selected from [X | Ys], Ys results.
  - When X is selected from the tail of [H | Ys], [H | Zs] results, where Zs is the result of taking X out of Ys.
  - The program:
  1
  2
  3
  4
  delete(X, [], _) :- fail. % not needed
  delete(X, [X | Ys], Ys).
  delete(X, [Y | Ys], [Y | Zs]) :-
  delete(X, Ys, Zs).
Define permute/2, to find a permutation of a given list.
- e.g. permute([1, 2, 3], X) should return X = [1, 2, 3] and upon backtracking, X = [1, 3, 2], X = [2, 1,3], X = [2, 3, 1], X = [3, 1, 2], and X = [3, 2, 1]
- The program:
  1
  2
  3
  4
  permute([], []).
  permute([X | Xs], Ys) :-
  permute(Xs, Zs),
  delete(X, Ys, Zs)

The Issue of Efficiency

Define a predicate, rev/2 that finds the reverse of a given list.
- e.g. rev([1, 2, 3], X) should succeed with X = [3, 2, 1]
- Hint: what is the relationship between the reverse of [1, 2, 3] and the reverse of [2, 3]?
  
  Answer: append([3, 2], [1], [3, 2, 1])
- The program:
  1
  2
  3
  4
  rev([], []).
  rev([X | Xs], Ys) :-
  rev(Xs, Zs),
  append(Zs, [X], Ys).
- How long does it take to evaluate rev([1, 2, …, n], X)?
  - T(n) = T(n - 1) + time to add 1 element to the end of an n - 1 element list
    
    = T(n - 1) + n - 1
    
    = T(n - 2) + n - 2 + n - 1
    
    = …
    
    = O(n^2)

Making rev/2 faster

Keep an accumulator: a stack all elements seen so far.
- i.e. a list, with elements seen so far in reverse order.

The program:

rev(L1, L2) :- rev(L1, [], L2).
rev([X | Xs], AccBefore, AccAfter) :-
    rev(Xs, [X | AccBefore], AccAfter).
rev([], Acc, Acc). % Base case

Tree Traversal

Assume you have a binary tree, represented by
- node/3 facts: for internal nodes: node(a, b, c) means that a has b and c as children.
- leaf/1 facts: for leaves: leaf(a) means that a is a leaf.
- Example:
  
  node(5, 3, 6).
  
  node(3, 1, 4).
  
  leaf(1).
  
  leaf(4).
  
  leaf(6).
  1
  2
  3
  4
  5
  5
  / \
  3 6
  / \
  1 4
- Write a predicate preorder/2 that traverses the tree (starting from a given node) and returns the list of nodes in pre-order.
- Algorithm:
  1
  2
  3
  4
  5
  6
  7
  8
  preorder(Root, [Root]) :-
  leaf(Root).
  
  preorder(Root, [Root|L]) :-
  node(Root, Child1, Child2),
  preorder(Child1, L1),
  preorder(Child2, L2),
  append(L1, L2, L).
- The program takes O(n^2) time to traverse a tree with n nodes.

Difference Lists

The lists in Prolog are singly-linked; hence we can access the first element in constant time, but need to scan the entire list to get the last element.
However, unlike functional languages like Lisp or SML, we can use variables in data structures:
- We can exploit this to make lists ‘open tailed‘
When X = [1, 2, 3 | Y], X is a list with 1, 2, 3 as its first three elements, followed by Y.
- Now if Y = [4 | Z] then X = [1, 2, 3, 4 | Z]
  - We cN think of Z as ‘pointing to’ the end of X.
- We can now add an element to the end of X in constant time

Graphs in Prolog

There are several ways to represent graphs in Prolog:
- Represent each edge separately as one clause (fact):
  
  edge(a, b).
  
  edge(b, c).
  - isolated nodes cannot be represented, unless we have also node/1 facts
- The whole graph as one data object: as a pair of two sets (nodes and edges): graph([a, b, c, d, f, g], [e(a, b), e(b, c), e(b, f)])
  - list of arcs: [a-b, b-c, b-f]
- Adjacency-list:

p.105