Transcript Ch.8 [B] - Computer Science & Engineering

Programming Style and Technique
Notes for Ch.8 of Bratko
For CSCE 580 Sp03
Marco Valtorta
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Use of Recursion: maplist
• maplist is an example of a “higher-order function”: a
function that applies to another function
• In the original LISP (McCarthy, 1960):
• ((label maplist
(lambda (x f)
(cond ((null x) ‘( ))
(‘t (cons (f (car x)) (maplist (cdr x) f))))))
• Maplist( List, F, NewList) if NewList contains the result of
applying F to each element of List, in order
• The function F the binary relation representing the
function we want to apply
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
maplist II
• Boundary (base) case: List = [ ]
– if List = [ ] then NewList = [ ]
• General case: List = [ X|Tail]
– To transform a list of the form [ X|Tail], do
• transform the item X by F, obtaining New X, and
• transform the list Tail obtaining NewTail
• the whole transformed list if [ NewX|NewTail]
• See ch8_1.pl
• renamed maplist1, because maplist is built in, with
slightly different meaning
• call/2 can be used for a more functional (less
relational) style
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Generalization
• Generalization allows us to use recursion
• Example: eight queens
• without generalization, no integer to recur on!
• Define nqueens( Pos,N)
– if N queens are safe in position Pos
• Base case: N = 0: trivial
• General case: N > 0
• achieve a safe configuration of N-1 queens
• add the remaining queen so that it does attack
• eightqueens( Pos) :- nqueens( Pos,8).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Debugging
• Most Prolog interpreters and compilers use a fourport model for goals
call
retry
UNIVERSITY OF SOUTH CAROLINA
succeed
foo/n
fail
Department of Computer Science and Engineering
Debugging Example
• ch3_1.pl1
• [trace] 1 ?- del( a,[a,b,a],L)
• See Section 2.9 of SWI-Prolog manual for some
extensions
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Improving Efficiency
• Eight queens, again:
• using a more informed initial ordering of queen
coordinate values helps, as described in the
comments at the end of ex4_6.pl
• Map coloring
– start with countries that have many neighbors
• Warnsdorff’s heuristic for the knight’s tour
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Difference Lists
• concat( A1-Z1,Z1-Z2,A1-Z2).
• See UseDefK4.ppt
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Accumulators
• sumlist
• See UseDefK4.ppt
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering