[alexandria-devel] reductions
Hi Alexandrians, Clojure has a function that I occasionally find useful, reductions. It's like reduce, only it returns not the last value of calling the two-arg function, but a list consisting of the first element of the input sequence, followed by the result of calling the two-arg with the first and second elements of the input sequence, then the result of calling the two-arg function with the previous result and the third element, and so on... e.g.: CL-USER> (reductions #'+ '(1 2 3 4)) (1 3 6 10) Here's the code. There are probably better ways to do this, but this is at least portable and simple. I think this would be a useful addition to alexandria. (defun reductions (function sequence &rest args) (let ((l (list (first sequence)))) (apply #'reduce (lambda (a b) (let ((val (funcall function a b))) (push val l) val)) sequence args) (nreverse l))) thanks, Cyrus
On Dec 30, 2010, at 02:56 , Cyrus Harmon wrote:
CL-USER> (reductions #'+ '(1 2 3 4)) (1 3 6 10)
I find this a bit surprising behavior: CL-USER> (reductions #'+ '(1 2 3 4) :initial-value 10) (1 11 13 16 20) I would have expected (11 13 16 20) or (10 11 13 16 20). Here's a counter-proposal, with a similar interface as MAP: CL-USER> (left-scan 'vector #'+ 10 '(1 2 3 4)) #(11 13 16 20) ;; (vector (+ 10 1) (+ 11 2) ...) CL-USER> (right-scan 'list #'+ 0 '(1 2 3 4)) (4 7 9 10) ;; (list (+ 0 4) (+ 4 3) (+ 7 2) ...) CL-USER> (left-scan1 'vector #'+ '(1 2 3 4)) #(3 6 10) ;; (vector (+ 1 2) (+ 3 3) (+ 6 4)) (defun left-scan (type fn init seq &rest seqs) (flet ((next (&rest args) (setf init (apply fn init args)))) (apply #'map type #'next seq seqs))) (defun left-scan1 (type fn seq) (if (= 0 (length seq)) (coerce '() type) (scanl type fn (elt seq 0) (subseq seq 1)))) (defun left-scan-into (result fn init &rest seqs) (flet ((next (&rest args) (setf init (apply fn init args)))) (apply #'map-into result #'next seqs))) (defun right-scan (type fn init seq &rest seqs) (let ((rev-seqs (mapcar #'reverse (list* seq seqs)))) (apply #'left-scan type fn init rev-seqs))) (defun right-scan1 (type fn seq) (apply #'left-scan1 type fn (reverse seq))) etc. Obviously under-documented, but the intent should be identifyable. -- Cheers, Michael
Nice catch. Well, once could use left-scan and right-scan, or they could just fix reductions: (defun reductions (function sequence &rest args &key initial-value) (let ((l (list (or initial-value (first sequence))))) (apply #'reduce (lambda (a b) (let ((val (funcall function a b))) (push val l) val)) sequence args) (nreverse l))) left-scan and right-scan also look reasonable. I'm happy with either the clojure-style function or the haskell-style functions. But, one way or the other, I think this would be a useful addition to alexandria. cyrus On Dec 30, 2010, at 9:13 PM, Michael Weber wrote:
On Dec 30, 2010, at 02:56 , Cyrus Harmon wrote:
CL-USER> (reductions #'+ '(1 2 3 4)) (1 3 6 10)
I find this a bit surprising behavior:
CL-USER> (reductions #'+ '(1 2 3 4) :initial-value 10) (1 11 13 16 20)
I would have expected (11 13 16 20) or (10 11 13 16 20).
Here's a counter-proposal, with a similar interface as MAP:
CL-USER> (left-scan 'vector #'+ 10 '(1 2 3 4)) #(11 13 16 20) ;; (vector (+ 10 1) (+ 11 2) ...) CL-USER> (right-scan 'list #'+ 0 '(1 2 3 4)) (4 7 9 10) ;; (list (+ 0 4) (+ 4 3) (+ 7 2) ...) CL-USER> (left-scan1 'vector #'+ '(1 2 3 4)) #(3 6 10) ;; (vector (+ 1 2) (+ 3 3) (+ 6 4))
(defun left-scan (type fn init seq &rest seqs) (flet ((next (&rest args) (setf init (apply fn init args)))) (apply #'map type #'next seq seqs)))
(defun left-scan1 (type fn seq) (if (= 0 (length seq)) (coerce '() type) (scanl type fn (elt seq 0) (subseq seq 1))))
(defun left-scan-into (result fn init &rest seqs) (flet ((next (&rest args) (setf init (apply fn init args)))) (apply #'map-into result #'next seqs)))
(defun right-scan (type fn init seq &rest seqs) (let ((rev-seqs (mapcar #'reverse (list* seq seqs)))) (apply #'left-scan type fn init rev-seqs)))
(defun right-scan1 (type fn seq) (apply #'left-scan1 type fn (reverse seq)))
etc.
Obviously under-documented, but the intent should be identifyable.
-- Cheers, Michael
_______________________________________________ alexandria-devel mailing list alexandria-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel
I'm not fundamentally opposed to this sort of thing, but I think we should refrain from adding more things to Alexandria before we get 1.0 out the door. If people want a playground for this sort of thing, I can add a separate system and package called Byzantium to the repo. Cheers, -- nikodemus
participants (3)
-
Cyrus Harmon -
Michael Weber -
Nikodemus Siivola