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 id="result_box" class="short_text"><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>