Sorry, I forgot to CC.<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Gustavo</b> <span dir="ltr"><<a href="mailto:gugamilare@gmail.com">gugamilare@gmail.com</a>></span><br>
Date: 2010/8/8<br>Subject: Re: [alexandria-devel] Fold operators on lists and trees in Alexandria?<br>To: Heka Treep <<a href="mailto:zena.treep@gmail.com">zena.treep@gmail.com</a>><br><br><br>Hello, Heka,<br><br>Just to clarify, I'm not a Alexandria developer, but I'll make some criticism.<br>
<br>I'm sorry but <span style="font-family: courier new,monospace;">flatten/fold-right <font face="arial,helvetica,sans-serif">is not faster than <font face="courier new,monospace">flatten</font>. It has a bug that prevents it from working correctly: </font></span><span style="font-family: courier new,monospace;">fold-right</span> version is destructive (it uses nreverse in the incoming list, it should be used in the result)<span style="font-family: courier new,monospace;"><font face="arial,helvetica,sans-serif">.</font></span> Then, if you make a loop that flattens the same tree a lot of times, the original tree is modified so the running time is altered.<br>
<br><span style="font-family: courier new,monospace;">cl-user> (defvar tree '((1 2 3) (4 5 6)))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">tree</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">cl-user> (flatten/fold-right tree)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">(1 2 3 4 5 6)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">cl-user> tree</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">((1))</span><br><br>It doesn't make sense <span style="font-family: courier new,monospace;">flatten/fold-right <font face="arial,helvetica,sans-serif">to be faster than <font face="courier new,monospace">flatten</font></font></span> because it <span style="font-family: courier new,monospace;"><font face="arial,helvetica,sans-serif">calls</font></span> <span style="font-family: courier new,monospace;">append</span><span style="font-family: courier new,monospace;"></span> <font face="arial,helvetica,sans-serif">which</font> needs to traverse the first argument, so it gets slower when the list to be flattened has large sublists. Also, it treats NIL as an atom while <span style="font-family: courier new,monospace;">flatten</span> treats it as the empty list.<br>
<br>The following version of flatten is the only one that I have noted to be faster than flatten (25% to 45% faster) because it doesn't have to call nreverse at the end:<br><br><span style="font-family: courier new,monospace;">(defun flatten/tail (tree)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> (let (list tail)</span><div class="im"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> (labels ((traverse (subtree)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> (when subtree</span><br style="font-family: courier new,monospace;"></div><span style="font-family: courier new,monospace;"> (cond</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> ((consp subtree)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> (progn</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> (traverse (car subtree))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> (traverse (cdr subtree))))</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> (tail (setf (cdr tail) (cons subtree nil)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> tail (cdr tail)))</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> (t (setf list (list subtree)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> tail list))))))</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> (traverse tree))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> list))</span><br><br>Don't worry, everyone commits mistakes. It took me some time to figure out the problem too.<br>
<br>Gustavo.<br><br><div class="gmail_quote">2010/8/7 Heka Treep <span dir="ltr"><<a href="mailto:zena.treep@gmail.com" target="_blank">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;"><div><div></div><div class="h5">Sorry, I made a small typo:<span><span style="background-color: rgb(235, 239, 249);" title="ń ÓÄÅĢĮĢ ĪÅĀĻĢŲŪÕĄ ĻŠÅŽĮŌĖÕ"></span></span><span><span style="background-color: rgb(235, 239, 249);" title="ń ÓÄÅĢĮĢ ĪÅĀĻĢŲŪÕĄ ĻŠÅŽĮŌĖÕ"></span><span style="background-color: rgb(255, 255, 255);" title="īĻ
ÜŌĻ, ĖĻĪÅŽĪĻ, ĪÅ ÓĖĮŚŁ×ĮÅŌÓŃ ĪĮ ĀÅĪŽĶĮŅĖĮ"><div><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></div> + (list (append (flatten/fold-rigth e) rest))))<br> list nil))<br>
</span></span><span><span style="background-color: rgb(255, 255, 255);" title="īĻ
ÜŌĻ, ĖĻĪÅŽĪĻ, ĪÅ ÓĖĮŚŁ×ĮÅŌÓŃ ĪĮ ĀÅĪŽĶĮŅĖĮ"><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" target="_blank">zena.treep@gmail.com</a>></span><div><div></div><div>
<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></div></div><br>
<br></div></div>_______________________________________________<br>
alexandria-devel mailing list<br>
<a href="mailto:alexandria-devel@common-lisp.net" target="_blank">alexandria-devel@common-lisp.net</a><br>
<a href="http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel" target="_blank">http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel</a><br>
<br></blockquote></div><br>
</div><br>