---------- Forwarded message ----------
From:
Gustavo <gugamilare@gmail.com>
Date: 2010/8/8
Subject: Re: [alexandria-devel] Fold operators on lists and trees in Alexandria?
To: Heka Treep <
zena.treep@gmail.com>
Hello, Heka,
Just to clarify, I'm not a Alexandria developer, but I'll make some criticism.
I'm sorry but
flatten/fold-right is not faster than flatten. It has a bug that prevents it from working correctly: fold-right version is destructive (it uses nreverse in the incoming list, it should be used in the result)
. 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.
cl-user> (defvar tree '((1 2 3) (4 5 6)))tree
cl-user> (flatten/fold-right tree)(1 2 3 4 5 6)
cl-user> tree((1))It doesn't make sense
flatten/fold-right to be faster than flatten because it
calls append which 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
flatten treats it as the empty list.
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:
(defun flatten/tail (tree)
(let (list tail)
(labels ((traverse (subtree)
(when subtree
(cond
((consp subtree) (progn
(traverse (car subtree)) (traverse (cdr subtree))))
(tail (setf (cdr tail) (cons subtree nil) tail (cdr tail)))
(t (setf list (list subtree) tail list))))))
(traverse tree)) list))Don't worry, everyone commits mistakes. It took me some time to figure out the problem too.
Gustavo.
2010/8/7 Heka Treep
<zena.treep@gmail.com>
Sorry, I made a small typo:
(defun flatten/fold-rigth (list)
(fold-rigth #'(lambda (e rest)
(typecase e
(atom (cons e rest))
- (list (append (flatten e) rest))
+ (list (append (flatten/fold-rigth e) rest))))
list nil))
But this, of course, does
not affect the benchmark.
2010/8/8 Heka Treep
<zena.treep@gmail.com>
Hi.
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).
Take for example the `flatten' function that is defined in Alexandria as follows:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ok, TCO recursion:
;;
(defun flatten (tree)
(let (list)
(labels ((traverse (subtree)
(when subtree
(if (consp subtree)
(progn
(traverse (car subtree))
(traverse (cdr subtree)))
(push subtree list)))))
(traverse tree))
(nreverse list)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
We need an ADT for the trees, but in the first approximation we can use nested lists.
When expressed in terms of reduce:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun flatten/reduce (list)
(reduce #'(lambda (e rest)
(typecase e
(atom (cons e rest))
(list (append (flatten/reduce e) rest))))
list
:initial-value nil
:from-end t))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Now if we translate pure functional operator (here is `reduce') to the instructions for tagbody/go "state machine":
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; fold-left f '(a b c) i
;;;
;;; f
;;; /\
;;; f c
;;; /\
;;; f b
;;; /\
;;; i a
;;;
;;; foldl f z [] = z
;;; foldl f z (x:xs) = foldl f (f z x) xs
(defun fold-left (function list &optional initial-value)
(let ((result initial-value))
(tagbody
:start
(unless (endp list)
(setq result (funcall function result (car list)))
(setq list (cdr list))
(go :start)))
result))
;;; fold-rigth f '(a b c) i
;;;
;;; f
;;; /\
;;; a f
;;; /\
;;; b f
;;; /\
;;; c i
;;;
;;; foldr f z [] = z
;;; foldr f z (x:xs) = f x (foldr f z xs)
(defun fold-rigth (function list &optional initial-value)
(let ((result initial-value)
(list (nreverse list)))
(tagbody
:start
(unless (endp list)
(setq result (funcall function (car list) result))
(setq list (cdr list))
(go :start)))
result))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Then `flatten' can be written as:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun flatten/fold-rigth (list)
(fold-rigth #'(lambda (e rest)
(typecase e
(atom (cons e rest))
(list (append (flatten e) rest))))
list nil))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
I try to benchmarc (this three functions) and has the following results:
flatten/fold-rigth
X time
Y memory
alexandria:flatten
10 * X time
23 * Y memory
flatten/reduce
42 * X time
83 * Y memory
So, its look resonable to use folders there.
((sorry for my english - I just using google.translate :))
alexandria-devel mailing list
alexandria-devel@common-lisp.net
http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel