Applicative Programming

June 8, 2008 | Filed Under Common Lisp - Touretzky 

———————————————————
Chapter 7
———————————————————

FUNCALL calls a function on some inputs:

(FUNCALL #’cons ‘a ‘b) -> (a . b)

Can also map a function to a symbol:
(SETF fn #’cons)
(FUNCALL fn ‘a ‘b) -> (a . b)

only ordinary functions should be quoted with #’ - macros, symbols or special functions will generate an error (#’IF -> ERROR)

(DEFUN SQUARE (n)
(* n n))
(SQUARE 3) -> 9
(SQUARE ‘(1 2 3 4 5)) ->ERROR

(MAPCAR #’SQUARE ‘(1 2 3 4 5)) -> (1 4 9 16 25)

MAPCAR passes each element of a list to a function.

Pass multiple args by separate lists:
(DEFUN mult (x y)
(* x y ))
(MAPCAR #’mult ‘(2 3 4) ‘(5 6 7)) -> (10 18 28)

(SETF nums
‘( (1 one)
(2 two)
(3 three)))
(MAPCAR #’FIRST nums) -> (1 2 3)
(MAPCAR #’SECOND nums) -> (one two three)
(MAPCAR #’REVERSE nums) -> ((one 1)….)

Lambda functions:
functions defined in-line - can be passed (i.e. to MAPCAR) without having to DEFUN first:

(MAPCAR #’(lambda (n) (* n n)) ‘(1 2 3 4)) -> (1 4 9 16)

FIND-IF returns the FIRST element which matches the predicate/lambda function:
(FIND-IF #’oddp ‘(2 4 7 8 9)) -> 7
(FIND-IF #’(lambda (x) (> x 3)) ‘(1 2 3 4 5)) ->4

(REMOVE-IF #’(lambda (x) (plusp x)) ‘(1 -2 3 -4)) -> (-2 -4)
(REMOVE-IF-NOT #’(lambda (x) (plusp x)) ‘(1 -2 3 -4)) -> (1 3)

; can simply use #’PLUSP X ????

REDUCE applies a function to a list and returns a single result - must be a function that takes two arguments:
(REDUCE #’+ ‘(1 2 3)) -> 6
(REDUCE #’* ‘(2 4 5)) -> 40
Takes the result of each loop of the function and uses the resultant list as one of the input arguments for the next loop.

Can also be used on a list of lists:
(REDUCE #’APPEND ‘(1 2 3) ‘(4 5 6)) -> (1 2 3 4 5 6)
(REDUCE #’UNION ‘(1 2 3) ‘(1 4 5)) -> (1 2 3 4 5)

EVERY applies a predicate to a list, and returns T if every element matches the predicate:
(EVERY #’oddp ‘(1 3 5)) -> T
(EVERY #’(lambda (x) (> x 3)) ‘(4 5 6)) -> T
(EVERY #’(lambda (x) (< x 2)) '(1 2 3)) -> NIL

EVERY on a NIL list will always return T
*** EVERY can also be used on multiple lists, matching each pair in turn:
(EVERY #’> ‘(20 10 5) ‘(18 8 3)) -> T

———————————————————
Notes on Chapter 7 exercises

Look up a value in a paired list with ASSOC:
(SETF tbl ‘((1 one) (2 two)))
(DEFUN LOOK-UP (num)
(assoc num tbl))
(LOOK-UP ‘1) -> (1 one)

Run a test on a list and remove those that pass/don’t pass the test, use REMOVE-IF and REMOVE-IF-NOT:
(DEFUN GET-ODD-NUMS (assoc-list)
(REMOVE-IF-NOT #’(LAMBDA (x) (ODD-P (FIRST x))) assoc-list))
(GET-ODD-NUMS tbl) -> ((1 one))

Run a test and return the first element that matches, use FIND-IF

Does one element of a list come before another? Use MEMBER twice:
(DEFUN cards ‘(1 2 3 4 5))
(DEFUN C1-COMES-FIRST-P (c1 c2)
(MEMBER c2 (MEMBER c1 cards)))
(C1-COMES-FIRST-P ‘1 ‘2) -> (2 3 4 5)
(C1-COMES-FIRST-P ‘2 ‘1) -> NIL

TO run a test on a list where you are comparing each element of a list, and carrying the “winner” forward, use reduce:

(DEFUN high-card (hand)
(REDUCE #’(LAMBDA (card1 card2)
(if (higher-rank-p card1 card2)
card1
card2))
hand))

this runs a test on two cards, returning the higher one and feeding this back into the Lambda as card1 with the next card from hand.

———————————————————

MAPCAR can operate on 2 lists:
(MAPCAR #’* ‘(1 2 3) ‘(4 5 6)) -> (4 10 18)
(MAPCAR #’(LAMBDA (x y) (LIST x ‘gets y))
‘(John Jim Jol) ‘(Job1 Job2 Job3)) -> ((John gets Job1)(Jim gets Job2)..)

FUNCALL works the same as #’
‘CONS -> CONS
#’CONS -> #
#’(LAMBDA (x) (+ x 2)) -> #

Function objects are stored as data, and can be assigned:
(SETF g #’(LAMBDA (x) (* x 10))) -> #
(FUNCALL g 12) -> 120
(G 12) -> error (G is not a function)

Keyword Arguments:
use FROM-END with a non-NIL argument with FIND-IF, REMOVE-IF, REDUCE, etc, to parse from right to left:
(FIND-IF #’ODD-P ‘(1 2 3 4 5) :FROM-END T) -> 5

Especially useful with REDUCE:
(REDUCE #’CONS ‘(a b c d e)) -> ((((A . B) . C) . D) . E)
(REDUCE #’CONS ‘(a b c d e) :FROM-END T) -> (a b c d . e)

Applicative operators:

(DEFUN inalienable-rights (fn)
(funcall fn
‘(life liberty and the pursuit of happiness)))

Any function applied to inalienable-rights will act on the list starting ‘(life..

(inalienable-rights #’length) -> 7
(inalienable-rights #’first) -> life

inalienable-rights will only accept a function that works on a list. CONS requires two lists, so this will not work - would need to wrap in a lambda:

(inalienable-rights #’(lambda (x) (cons ‘high x))) -> (high life liberty…)

alternatively:
(DEFUN func-test (fn)
(funcall fn ‘(1 2 3) ‘(4 5 6)))

(func-test #’cons) -> ((1 2 3) 4 5 6)
(func-test #’(lambda (x y) (mapcar #’* x y))) -> (4 10 18)

By passing back a lexical closure (lambda function) we can make a function that returns a function:

(defun make-greater-than-predicate (n)
#’(lambda (x) (> x n)))

(setf pred (make-greater-than-predicate 3)) -> now have a custom predicate that will take a value x and pass to the lambda function, and returning T if greater than 3.

(find-if pred ‘(1 2 3 4 5 6)) -> 4

Comments