[alexandria-devel] Fwd: Fold operators on lists and trees in Alexandria?

[Gustavo]

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20100808/095fa2f9/attachment.html>