Sorry, I made a small typo:<span id="result_box" class="short_text"><span style="background-color: rgb(235, 239, 249);" title="ń ÓÄÅĢĮĢ ĪÅĀĻĢŲŪÕĄ ĻŠÅŽĮŌĖÕ" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'"></span></span><span id="result_box" class="short_text"><span style="background-color: rgb(235, 239, 249);" title="ń ÓÄÅĢĮĢ ĪÅĀĻĢŲŪÕĄ ĻŠÅŽĮŌĖÕ" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'"></span><span style="background-color: rgb(255, 255, 255);" title="īĻ
ÜŌĻ, ĖĻĪÅŽĪĻ, ĪÅ ÓĖĮŚŁ×ĮÅŌÓŃ ĪĮ ĀÅĪŽĶĮŅĖĮ" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'"><br><br>(defun flatten/fold-rigth (list)<br> (fold-rigth #'(lambda (e rest)<br>
(typecase e<br> (atom (cons e rest))<br> - (list (append (flatten e) rest))<br> + (list (append (flatten/fold-rigth e) rest))))<br> list nil))<br>
</span></span><span id="result_box" class="short_text"><span style="background-color: rgb(255, 255, 255);" title="īĻ
ÜŌĻ, ĖĻĪÅŽĪĻ, ĪÅ ÓĖĮŚŁ×ĮÅŌÓŃ ĪĮ ĀÅĪŽĶĮŅĖĮ" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'"><br>But this, of course, does
not affect the benchmark</span></span>.<br><br><div class="gmail_quote">2010/8/8 Heka Treep <span dir="ltr"><<a href="mailto:zena.treep@gmail.com">zena.treep@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi.<br><br>I was found that there is no effective fold operators on lists or trees in CL. I know that `reduce' can do this (as an article in Wikipedia sayz) but `reduce' is not very effective. As stated in the Graham Hutton's article ``fold is a standard operator that encapsulates a simple pattern of recursion for processing lists'', also catamorphism at some ADT plays the same role. So I thought that if we introduce an effective fold operators, it becomes possible to express many functions through its shortly and effectively (in fact, almost any function on that ADT).<br>
<br>Take for example the `flatten' function that is defined in Alexandria as follows:<br><br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>;; ok, TCO recursion:<br>;;<br>(defun flatten (tree)<br>
(let (list)<br> (labels ((traverse (subtree)<br> (when subtree<br> (if (consp subtree)<br> (progn<br> (traverse (car subtree))<br> (traverse (cdr subtree)))<br>
(push subtree list)))))<br> (traverse tree))<br> (nreverse list)))<br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br><br>We need an ADT for the trees, but in the first approximation we can use nested lists.<br>
<br>When expressed in terms of reduce:<br><br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>(defun flatten/reduce (list)<br> (reduce #'(lambda (e rest)<br> (typecase e<br>
(atom (cons e rest))<br> (list (append (flatten/reduce e) rest))))<br> list <br> :initial-value nil<br> :from-end t))<br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>
<br>Now if we translate pure functional operator (here is `reduce') to the instructions for tagbody/go "state machine":<br><br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>
;;; fold-left f '(a b c) i<br>;;;<br>;;; f<br>;;; /\<br>;;; f c<br>;;; /\<br>;;; f b<br>;;; /\<br>;;; i a<br>;;;<br>;;; foldl f z [] = z<br>;;; foldl f z (x:xs) = foldl f (f z x) xs<br><br>
(defun fold-left (function list &optional initial-value)<br> (let ((result initial-value))<br> (tagbody<br> :start<br> (unless (endp list)<br> (setq result (funcall function result (car list)))<br> (setq list (cdr list))<br>
(go :start)))<br> result))<br><br>;;; fold-rigth f '(a b c) i<br>;;;<br>;;; f<br>;;; /\<br>;;; a f<br>;;; /\<br>;;; b f<br>;;; /\<br>;;; c i<br>;;;<br>;;; foldr f z [] = z<br>
;;; foldr f z (x:xs) = f x (foldr f z xs)<br><br>(defun fold-rigth (function list &optional initial-value)<br> (let ((result initial-value)<br> (list (nreverse list)))<br> (tagbody<br> :start<br> (unless (endp list)<br>
(setq result (funcall function (car list) result))<br> (setq list (cdr list))<br> (go :start)))<br> result))<br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br><br>
Then `flatten' can be written as:<br><br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>(defun flatten/fold-rigth (list)<br> (fold-rigth #'(lambda (e rest)<br> (typecase e<br>
(atom (cons e rest))<br> (list (append (flatten e) rest))))<br> list nil))<br>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br><br>I try to benchmarc (this <span><span style="background-color: rgb(255, 255, 255); color: rgb(0, 0, 0);" title="">three functions) </span></span>and has the following results:<br>
<br>flatten/fold-rigth<br><br>X time<br>Y memory<br><br>alexandria:flatten<br><br>10 * X time<br>23 * Y memory<br><br>flatten/reduce<br><br>42 * X time<br>83 * Y memory<br><br>So, its look resonable to use folders there.<br>
<br><br><br>((sorry for my english - I just using google.translate :))<br>
</blockquote></div><br>