Re: coerce for arbitrary types

Robert Maas, see http://tinyurl.com/uh3t wrote:

Regarding that proposed koan earlier: Does anybody have a
collection of short code snippets which likewise illustrate a whole
mess of deep understanding, where just trying to understand why
this particular snippet of code produces the result it does will
enlighten a newbie?

As we just witnessed (if you've been reading this list recently),
a 10-line recursive BFS is too much for a
newbie to figure out by himself if he's never seen something
like that done in CL before. I don't have a snippet collection that
you speak of, but if there were such a collection, I would expect
something like recursive BFS to be included since it demonstrates a
powerful problem-solving method so well.


On the other hand, after reviewing my notes, I guess I do have a
few suggestions.

Pascal-B illustrates recursion in a pedagogical and also useful
manner:

(defun enumerate (start end)
(when (< start end)
(cons start (enumerate (1+ start) end))))


A recursive macro written by Mr. Crowe has a certain beauty to it.
Probably not a good idea for the newbie to think they have to fully
understand it, but to understand that this is the type of code that
can be written, nay, should be written. Short, yet flexible and reusable.

CL-USER> (defmacro base-bind (unit-var amount (&rest var-and-radix) &body code)
(if (endp var-and-radix)
`(let ((,unit-var ,amount)) ,@code)
(let ((transfer (gensym)))
`(multiple-value-bind (,transfer ,unit-var)
(floor ,amount ,(cadar var-and-radix))
(base-bind ,(caar var-and-radix) ,transfer ,(cdr var-and-radix)
,@code)))))

CL-USER> (base-bind pence 1000 ((shillings 12)(pounds 20))
(list pounds shillings pence))
=> (4 3 4)

CL-USER> (base-bind seconds 100000 ((minutes 60)(hours 60)(days 24))
(values days hours minutes seconds))
1
3
46
40


The random shuffle algorithm is accessible and shows that
there are lots of ways of accomplishing something seemingly
simple. (Take that Python.)
http://www.pvk.ca/Blog/Lisp/malmesure_quand_tu_nous_tiens.html



I also think Ron's iteration article is well written and
provides insight. He extracts an important pattern.
(Is there any high-level pattern more important than iteration,
other than "IF"?)
http://rondam.blogspot.com/2008/02/joy-of-iterators.html



A nice example of parameterization, first-class functions,
and functional programming:

(defun best (sequence comparison &key (key #'identity))
(reduce (lambda (x y)
(if (funcall comparison (funcall key x) (funcall key y))
x y))
sequence
:initial-value (elt sequence 0)))

[11]> (best '(5 6 42 8 666 9 69 -42) #'> )
666


Why recursion is not always the best solution:

[16]> (defun fact(n) (if (zerop n) 1 (* n (fact (1- n)))))
FACT

[17]> (fact -1)
*** - Lisp stack overflow. RESET

[18]> (fact 10000)
*** - Lisp stack overflow. RESET



Example of clear, concise Lispy style:
[From "Tutorial on Good Lisp Programming Style"]

(defun count-all-numbers (exp)
(typecase exp
(cons
(+ (count-all-numbers (first exp))
(count-all-numbers (rest exp))))
(number 1)
(t 0)))


Learn to use accumulators:
[More from "Tutorial on Good Lisp Programming Style"]

(defun product (numbers &optional (key #'identity)
(accum 1))
"Like (reduce #'* numbers), but bails out early
when a zero is found."
(if (null numbers)
accum
(let ((term (funcall key (first numbers))))
(if (= term 0)
0
(product (rest numbers) key (* accum term))))


SORT has to be handled with care, even if it is destructive.

If you want to sort a list, you have to use the result of SORT.

Wont give a newbie the expected result:

(let ((mylist (list "c" "d" "a")))
(sort mylist #'string<)
mylist)

Better:

(let ((mylist (list "c" "d" "a")))
(setq mylist (sort mylist #'string<))
mylist)



More from Alan Crowe, this time showing how easy it is to
accomplish difficult tasks if you can properly determine
the right lever. [I've made a few spelling corrections.]



The cartesian product of two sets is easy enough, which
suggests using a fold to lift the operation from binary to
n-ary. There is a snag.

{a, b} x {1, 2} = {(a, 1), (a, 2), (b, 1), (b, 2)}

so strictly speaking

{a, b} x {1, 2} x {p, q}

is

( {a, b} x {1, 2} ) x {p, q} =

{((a, 1), p), ((a, 2), p), ((b, 1), p), ((b, 2), p),
((a, 1), q), ((a, 2), q), ((b, 1), q), ((b, 2), q)}

a technicality which mathematicians think of as /hair/ and
try to avoid or shave off.

The exact detail of the pair construction operator matters. I've
written my code to foreground this detail

#| Start from a generalization of the cartesian product of two sets, so that
f, {a,b}, {x,y} => {f(a,x), f(a,y), f(b,x), f(b,y)} |#

(defun product-set (f)
(lambda (u v)
(let (w)
(dolist (x u w)
(dolist (y v)
(push (funcall f x y) w))))))

#| I think this function has a clear theme

(funcall (product-set #'*) '(1 2 3) '(5 7))
=> (21 15 14 10 7 5)

|#

;;; Minor utility function, turns an item into a set
;;; with two elements, the singleton set and the empty set
;;; (in-and-out 3) => ((3) NIL)
(defun in-and-out (x)
"x => ({x} {})"
(list (list x) nil))

;;; Now we can define power-set and cartesian-product as folds
;;; that is, we use REDUCE to raise a suitably chosen product-set function
;;; from binary to n-ary

;;; (power-set '(1 2 3)) => ((2 1) (2 1 3) (1) (1 3) (2) (2 3) NIL (3))

(defun power-set (set)
(reduce (product-set #'union)
(mapcar #'in-and-out set)))

;;; (cartesian-product '(0) '(1 2) '(3 4 5))
;;; => ((0 1 5) (0 1 4) (0 1 3) (0 2 5) (0 2 4) (0 2 3))

(defun cartesian-product (&rest sets)
(reduce (product-set #'cons)
sets
:from-end t
:initial-value (list nil)))



And last, I would stay away from mentioning
the eval operator. There's a reason why its Hamming distance
indicates adjacency to 'evil.' Not because eval is evil,
but asking for it is usually an indicator that the
OP is way off the trail, and sending a bunch of good
people thrashing around after him is a giant waste
of everybody's time.

But it doesn't matter anyway because newbies don't read,
they think it's faster to just start coding.
.

Relevant Pages

  • Re: Its A Big Language Survey
    ... will expell him from the group of compund loop ... Recursion and functional style usually results in a cleaner code, ... (defun collect (item/s) ...   (etypecase x ...
    (comp.lang.lisp)
  • Re: Sorting by enumeration
    ... I want to be able to 1) sort by number, 2) sort by letter, 3) sort by ... (cond ((funcall test (funcall key b) ... (defun sort-by-number (values) ... (check-type x character) ...
    (comp.lang.lisp)
  • Re: Why is lisp better than java perl or python or ruby?
    ... Ruby. ... Sort them by date and time. ... (defun month-number (month) ... ;; encode special-date to universal time ...
    (comp.lang.lisp)