[alexandria-devel] Fwd: Fold operators on lists and trees in Alexandria?
Heka Treep
zena.treep at gmail.com
Thu Aug 19 15:35:56 UTC 2010
Thanks for this explanation, it helped. Now I can say that you was
right - using a list folders on a trees is not a good idea. However,
this folders expressed in an imperative style may be used to express
some functions on the linear lists (hm, probably not - the list is the
essence of Lisp, and all important functions are already defined in
standard).
Well, I checked problem of the global variables affection:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun fold-left/list (function list &optional initial-value)
(let ((list (copy-list list)))
(tagbody
:start
(unless (endp list)
(setq initial-value (funcall function initial-value (car list)))
(setq list (cdr list))
(go :start)))
initial-value))
(defun fold-rigth/list (function list &optional initial-value)
(let ((list (nreverse (copy-list list))))
(tagbody
:start
(unless (endp list)
(setq initial-value (funcall function (car list) initial-value))
(setq list (cdr list))
(go :start)))
initial-value))
(defun flatten/fold-rigth (list)
(fold-rigth/list #'(lambda (e rest)
(if (consp e)
(append (flatten/fold-rigth e) rest)
(cons e rest)))
list nil))
;; Also, this is a folder on vectors:
(defun fold-left/vector (function vector &optional initial-value)
(declare (type vector vector))
(let ((i 0)
(length (length vector)))
(declare (type integer i length))
(tagbody
:start
(unless (>= i length)
(setq initial-value (funcall function initial-value (aref vector i)))
(setq i (1+ i))
(go :start)))
initial-value))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
It work fine on small lists (better then flatten in TCO-way), but
worse on big lists, for example:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defparameter
*big-list*
(labels ((gen-list (n)
(if (zerop n)
(random 10)
(loop :for e :in (make-list n)
:collect (gen-list (1- n))))))
(gen-list 9)))
(time (progn (alexandria:flatten *big-list*) nil))
1x time
1x memory
(time (progn (flatten/fold-rigth *big-list*) nil))
4x time
10x memory
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
By the way, this is a natural folder for trees:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun fold/tree (f g tree)
(typecase tree
(atom (funcall f tree))
(cons (apply g
(mapcar #'(lambda (e)
(fold/tree f g e))
tree)))))
(defun flatten/fold/tree (tree) (fold/tree #'identity #'list* tree))
(time (progn (flatten/fold/tree *big-list*) nil))
2x time
6x memory
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
if it would be possible to write this in an imperative style as well
as fold-list this could give a good performance.
Ok, sorry for offtop ;)
2010/8/8, Gustavo <gugamilare at gmail.com>:
> Sorry, I forgot to CC.
>
> ---------- Forwarded message ----------
> From: Gustavo <gugamilare at gmail.com>
> Date: 2010/8/8
> Subject: Re: [alexandria-devel] Fold operators on lists and trees in
> Alexandria?
> To: Heka Treep <zena.treep at 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 at 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 at 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 at common-lisp.net
>> http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel
>>
>>
>
More information about the alexandria-devel
mailing list