home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

lect38-prolog-lists
lists in prolog

Recall recursive prolog solutions.

parent(homer,bart).
parent(marge,bart).

parent(homer,lisa).
parent(marge,lisa).

parent(abe, homer).
…

% anc(Old,Yng): is Old an ancestor of Yng?
%
anc(P,P).                                    % everybody is trivially their own ancestor.
anc(P1,P2) :- parent(PP2,P2), anc(P1,PP2).   % P1 is an ancester of P2 if P1 is an ancestor of P2's parent.

It's definitely interesting/unusual/new-paradigm-y, that we can query anc and use either a variable or a constant in either of the two “argument” positions. We can view anc simultaneously as four different useful functions:
- A predicate that tells if a particular person is an ancestor of another: anc(abe,bart)
- A function that returns all the ancestors of a particular person: anc(abe,Y)
- A function that returns all the descendents¹ of a particular person: anc(X,bart)
- A function that returns all possible ancestor-relations in the universe (er, knowledge-base): anc(X,Y)
It's fairly common in prolog to write a predicate thinking of it in terms of one narrow predicate/function, and then step back and realize the code is much more general.

Lists in prolog:

;  Racket:       Prolog:               Example:
;    empty         []                    []
;    cons          | (infix)             [4 | [5 | [6 | []]]]
;    cons²         . (prefix)            .(4,[])    .(4,.(5,[]))
;    list          [ .., .., ..]         [4,5,6]
;    cons*         [ ..,..,.. | .. ]     [4,5,6 | [7,8]]  [4,5,6 | Rst]

The cool thing about Prolog is how it pattern-matches. Example: What are all solutions to:

[3,4,5]=[X,4,Z]?
[3,4,5]=[X,5,Z]?
To [3,4,5]=[A|B]?
How about [3,4,5] = [X,4,Z|Blah]?
How about [a,b,c,d,e,f] = [A,b,C|Z]?

N.B. In prolog, strings with double-quotes is just a short-hand for a list of ascii-values. Strings with single-quotes are atomic.
(I find the ascii-ness a bit annoying, myself.)

Writing a function that processes a list: mem/2 (the “/2” indicating 2 arguments): Does a particular value occur inside a list?

mem( sayonara, [hi, bye, tag] ).        % false
mem( hi, [hi, bye, tag] ).              % true 
mem( hi, [aloha, hi, bye, hi, tag] ).   % true (for two different reasons, even).

How to write this in prolog? It can be difficult to get past a blank slate. The solution is: to process a list, use code shaped like the data-definition or a list!

Write the natural, structural recursive version (in racket or Java or whatever). Examples:

Following the data-def'n of a list, in racket:

(define (mem target itms)
  (cond [(empty? itms) #f]
        [(cons?  itms) (or (equal? target (first itms))
                           (mem target (rest itms)))]))

Following the list data-definition, using Java's built-in java.util.List (and java.util.List#sublist to get the rest of the list):

static <T> boolean mem( T target, List<T> itms ) {
  if (itms.isEmpty()) {
    return false;
    }
  else {
    return target.equals(itms.get(0)) || mem( target, itms.subList(1) );
    }
  }

Following the list data-definition in Java, using object-oriented design:

 
abstract class SList<T> {
  abstract boolean mem(T target);
  }

class Empty<T> extends SList<T> {
  boolean mem(T target, List<T> itms ) { return false; }
  }

class Cons<T> extends SList<T> {
  T first;
  SList<T> rest;
  
  boolean mem( /* Cons this */ T target) { 
    return this.first.equals(target)
        || this.rest.contains(target);
    }
  }

/* Of course, we're omitting the constructor.  And, the `toString()`.
 * And, the `equals(Object)`.  And, the `hashCode()`.
 */

Or, using filter (racket):
(define (mem target itms) (cons? (filter (λ (itm) (equal? itm target)) itms))
Drawback: filter doesn't short-circuit, and it takes the time to build/allocate a new list.
Using fold (racket):
(define (mem target itms) (foldr (λ (f rr) (or (equal? f target) rr) false itms))
Drawback: fold still doesn't short-circuit — it's purpose is to iterate over the entire list.
(define (mem target itms) (for/first {[itm itms]} (equal? itm target)))
This is full #lang racket, using one of the idiomatic for-loops (which work on all collecitons: lists, strings, numeric ranges, arrays, hash-tables, ...). (does short-circuit; generalizes to collections).

In each case above, the green code is the only part that doesn't follow automatically from the data-definition for a list.

Of course, for this problem in real life, we'd just use use the provided library function member?/java.util.Collection#contains. But if you have a different list/collection problem, then the above approaches would be ways you'd write it yourself.

Convert each branch of code to a prolog clause.

% itms is empty:
mem_v1( Target, Itms ) :- Itms=[], false. 

% itms is a constructed list, and its first item is the target:
mem_v1( Target, Itms ) :- Itms = [F|R], Target=F.

% itms is a constructed list, and the recursive call is true:
mem_v1( Target, Itms ) :- Itms = [F|R], mem_v1( Target, R ).

Test your prolog version.

Go back and idiomize your prolog program. In general:

Any branch which always fails (always evaluates to false) isn't really needed at all — we can just drop the rule mem_v1( Target, Itms ) :- Itms=[], false. entirely ³.

Factor out any Var=Patterns: wherever else Var occurs, just in-line Pattern directly. (The term Var=Patterns itself disappears ⁴.)

% Before:
%
mem_v1( Target, Itms ) :- Itms = [F|R], mem_v1( Target, R ).
%
% After:
%
mem( Target, [F|R] ) :- mem( Target, R ).

and similarly

% Before:

mem_v1( Target, Itms ) :- Itms = [F|R], Target=F.

% becomes:

mem_v1( Target, [F|R] ) :- Target=F.

% which further becomes:

mem_v1( Target, [Target|R] ) :- .

% After:

mem( Target, [Target|R] ).

Replace any singleton variables with underscores.

mem( Target, [Target|_] ).                 % Target is in the list if: the list starts with Target.
mem( Target, [_|R] ) :- mem( Target, R ).  % Target is in the list if: it's (recursively) in the rest of the list.

(Note that we can't replace R with an underscore; it's important to say that we recur on the same rest-of-the-list we were handed.)

Test your factored version, just to be sure you didn't introduce bugs.

Note that for our hws, it's not required to use underscore for singleton variables, for full credit; arguably it even makes more sense (esp. for a learner) to use a descriptive name in matching, even if it's never used elsewhere in the clause.
However, for full credit, it is required to get rid of Var=Patterns for full credit. (You can still get most of the credit though even if you still have them.)

Note how we think of mem as a predicate taking in two values and returning yes/no, but actually we can use it more generally, with variables.
What is mem( X, [2,3,5,7,11,13] )?
What is mem( hello, X )?!?

If we did append in prolog, how would we call it?
append( [hi,there], [every,body] ) is not enough — our prolog predicates can only return true or false(fail) — they can't return a new list!
So: How could I possibly call append, to find out the result of appending [hi,there] with [every,body]?

I need a three-argument predicate: append(L1,L2,L3) takes in three lists, and returns true iff L1 appended with L2 yields L3:

append( [hi,there], [every,body], [hi,there,every,body] )  % true
append( [hi,there], [every,body], [whazzup,doodz,hi] )     % false

But still, how do I have the computer tell me the result of appending [hi,there] with [every,body]?
Aha, we can use variables in our queries, remember?

append( [hi,there], [every,body], Z )   % Tell me the result of appending
  
% And for free, we also get remove-prefix and remove-suffix:
append( [hi,there], Y, [hi,there,every,body] )     % remove the given prefix from the list (!)
append( X, [every,body], [hi,there,every,body] )   % remove the given tail/suffix from the list (!)

% We even get, for free:
append( X, Y, [hi,there,every,body] )  % Find all ways to split a list!

aside: We'll write append/3 ourselves, next. But if you want to first play with the built-in append for yourself, you can type [basics]. to load the basic-library. (It's the same syntax you used for loading your own file.)

Write append/3 ourselves.
Hint, if you're stuck:
1. write the natural, structural recursive version (in racket or Java or whatever).
2. convert each branch of code to a prolog clause.
3. Go back and “idiomize” your prolog program:
  Factor out any =s (just get rid of the variable on one side, substituting-in the other side of the equality), and then (optional) change any singleton variables to underscores.
How to write a predicate to tell if one list is a sublist of another? (Remember, prolog treats double-quoted strings as a list-of-chars, so this is a function implemented in many languages.)
% examples / tests: sublist( [3,4,5], [a,b,3,4,5,x,y] ) % true sublist( [3,4,5], [a,b,3,hello,4,5,x,y] ) % false sublist( [3,4,5], [3,4] ) % false sublist( [], [a,b,c] ) % true
hint:Use append/3.

Note that Prolog's pattern matching is neat: how to tell if some target is precisely the third element in a list?
Third to last?

% true iff Itm is the fourth element of L
%
getFourthItem( L, Itm ) :- L=[X,Y,Z,Itm|R].

% we can simplify the `=`:

getFourthItem( [X,Y,Z,Itm|R], Itm ).

% we can use underscore for variables we don't care about:

getFourthItem( [_,_,_,Itm | _], Itm ).

% Other functions to write:
% atLast(X,L)
% removeLast(L1,L2)
% reverse(L,R)
% append (L1,L2,L)
% zip(L1,L2,L)
%   e.g.  zip( [a,b,c], [d,e,f], [a,d,b,e,c,f] ).
%
%       removeOnce( Target, Data, Result )   (search)
%       contains(Target, Data)               (search)
%       isAllEvens(Data)                     (search)
%       filterEvens(Data,Result)             (filter)
%       squareEach(Data,Result)              (map)
%       sum(Data,Total)                      (fold)

Here is an incorrect attempt at writing allEvens. What is wrong?

allEvens([H,_]) :- even(H).
allEvens([H,T]) :- even(H), allEvens(T).

How about:

squareEach( L1, L2 ).
squareEach( [H1,T1], [H2,T2] ) :- H2 is H1*H1, squareEach(T1,T2).

¹that is, inverse-ancestors ↩

² Calling . (cons) is one of the few (non-boolean) functions we have in prolog:

.(hi, .(bye, .(done, [])))

% same as:
[hi, bye, done]

In practice, we only use the square-bracket syntax (along with |). ↩

³ Note that, according to rule ii, we would have phrased mem_v1(Target,Itms) :- Itms=[], fail. as mem_v1(Target,[]) :- fail. to start with, if we'd written it down at all. ↩

⁴ Actually, the term Var=Pattern gets re-written as Pattern=Pattern, which simplifies to the term true, which can be elided from the right-hand-side (since that right-hand-side is a list-of-anded-terms). ↩

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

©2015, Ian Barland, Radford University
Last modified 2015.Dec.27 (Sun) Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu

lect38-prolog-lists lists in prolog

lect38-prolog-lists
lists in prolog