|
home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)
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. |
; Racket: Prolog: Example: ; '() [] [] ; cons | (infix) [4 | [5 | [6 | []]]] ;The cool thing about Prolog is how it pattern-matches. Example: What are all solutions to:cons2 . (prefix) .(4,[]) .(4,.(5,[])) ; list [ .., .., ..] [4,5,6] ; cons* [ ..,..,.. | .. ] [4,5,6 | [7,8]] [4,5,6 | Rst]
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:
(define (mem target itms) (cond [(empty? itms) #false] [(cons? itms) (or (equal? target (first itms)) (mem target (rest itms)))])) |
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) ); } } |
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()`. */ |
(define (mem target itms) (cons? (filter (λ (itm) (equal? itm target)) itms)) |
(define (mem target itms) (foldr (λ (f rr) (or (equal? f target) rr) false itms)) |
(define (mem target itms) (for/first {[itm itms]} (equal? itm target))) |
Of course, for this problem in real life, we'd just use use the
provided library function
% 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 ). |
% Before: % mem_v1( Target, Itms ) :- Itms = [F|R], mem_v1( Target, R ). % % After: % mem( Target, [F|R] ) :- mem( Target, R ). |
% 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] ). |
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 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
I need a three-argument predicate:
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
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 writeappend/3 ourselves, next. But if you want to first play with the built-inappend for yourself, you can type[basics]. to load the basic-library. (It's the same syntax you used for loading your own file.)
% 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:Useappend/3 .
% 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)
allEvens([H,_]) :- even(H). allEvens([H,T]) :- even(H), allEvens(T). |
squareEach( L1, L2 ). squareEach( [H1,T1], [H2,T2] ) :- H2 is H1*H1, squareEach(T1,T2). |
.(hi, .(bye, .(done, []))) % same as: [hi, bye, done] |
home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)
©2016, Ian Barland, Radford University Last modified 2016.Dec.05 (Mon) |
Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |