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

8 Aug 2010

      Sorry, I forgot to CC.

---------- 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

Gustavo

Heka Treep

tags

participants (2)