alexandria-devel August 2010

alexandria-devel@common-lisp.net

2 participants
4 discussions

[alexandria-devel] [PATCH] add lastcons
by Mathieu Lemoine 30 Oct '11

30 Oct '11

Hi everyone. I made a little addition to the library. The lastcons function... It is very simple and I found myself thinking "that's something that ought to be in alexandria"... Not knowing the exact procedure to commit to the repo (and "git push" give me a "fatal: The remote end hung up unexpectedly" which is to be expected, I guess...), I send you the patch. Mathieu Lemoine.

3 4

[alexandria-devel] Simple optimizations for BINOMIAL-COEFFICIENT and COUNT-PERMUTATIONS
by Gustavo 23 Sep '10

23 Sep '10

Hello, Just some simple optimizations. By the way, nice work on FACTORIAL, it is very fast. Gustavo

2 1

[alexandria-devel] Fwd: Fold operators on lists and trees in Alexandria?
by Gustavo 19 Aug '10

19 Aug '10

Sorry, I forgot to CC. ---------- Forwarded message ---------- From: Gustavo <gugamilare(a)gmail.com> Date: 2010/8/8 Subject: Re: [alexandria-devel] Fold operators on lists and trees in Alexandria? To: Heka Treep <zena.treep(a)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(a)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(a)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(a)common-lisp.net > http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel > >

2 1

[alexandria-devel] Fold operators on lists and trees in Alexandria?
by Heka Treep 07 Aug '10

07 Aug '10

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

1 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

alexandria-devel August 2010