emacs-elpa-diffs
[Top][All Lists]
Advanced
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[elpa] externals/dash 75efb60 246/439: Add tree map/reduce

From: Phillip Lord
Subject: [elpa] externals/dash 75efb60 246/439: Add tree map/reduce
Date: Tue, 04 Aug 2015 20:28:31 +0000 
branch: externals/dash
commit 75efb6069adff14ccba361013ae3c906d0518b08
Author: Matus Goljer <address@hidden>
Commit: Matus Goljer <address@hidden>

    Add tree map/reduce
---
 README.md       |  101 +++++++++++++++++++++++++++++++++++++++++
 dash.el         |  135 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 dev/examples.el |   55 +++++++++++++++++++++-
 3 files changed, 289 insertions(+), 2 deletions(-)

diff --git a/README.md b/README.md
index 9ea6343..9439db1 100644
--- a/README.md
+++ b/README.md
@@ -132,6 +132,15 @@ To get function combinators:
 * [-last-item](#-last-item-list) `(list)`
 * [-sort](#-sort-comparator-list) `(comparator list)`
 
+### Tree operations
+
+* [-tree-map](#-tree-map-fn-tree) `(fn tree)`
+* [-tree-reduce](#-tree-reduce-fn-tree) `(fn tree)`
+* [-tree-reduce-from](#-tree-reduce-from-fn-init-value-tree) `(fn init-value 
tree)`
+* [-tree-mapreduce](#-tree-mapreduce-fn-folder-tree) `(fn folder tree)`
+* [-tree-mapreduce-from](#-tree-mapreduce-from-fn-folder-init-value-tree) `(fn 
folder init-value tree)`
+* [-clone](#-clone-list) `(list)`
+
 ### Threading macros
 
 * [->](#--x-optional-form-rest-more) `(x &optional form &rest more)`
@@ -953,6 +962,98 @@ if the first element should sort before the second.
 ```
 
 
+## Tree operations
+
+#### -tree-map `(fn tree)`
+
+Apply `fn` to each element of `tree` while preserving the tree structure.
+
+```cl
+(-tree-map '1+ '(1 (2 3) (4 (5 6) 7))) ;; => '(2 (3 4) (5 (6 7) 8))
+(-tree-map '(lambda (x) (cons x (expt 2 x))) '(1 (2 3) 4)) ;; => '((1 . 2) ((2 
. 4) (3 . 8)) (4 . 16))
+(--tree-map (length it) '("<body>" ("<p>" "text" "</p>") "</body>")) ;; => '(6 
(3 4 4) 7)
+```
+
+#### -tree-reduce `(fn tree)`
+
+Use `fn` to reduce elements of list `tree`.
+If elements of `tree` are lists themselves, apply the reduction recursively.
+
+`fn` is first applied to first element of the list and second
+element, then on this result and third element from the list etc.
+
+See `-reduce-r` for how exactly are lists of zero or one element handled.
+
+```cl
+(-tree-reduce '+ '(1 (2 3) (4 5))) ;; => 15
+(-tree-reduce 'concat '("strings" (" on" " various") ((" levels")))) ;; => 
"strings on various levels"
+(--tree-reduce (cond ((stringp it) (concat it " " acc)) (t (let ((sn 
(symbol-name it))) (concat "<" sn ">" acc "</" sn ">")))) '(body (p "some 
words") (div "more" (b "bold") "words"))) ;; => "<body><p>some words</p> 
<div>more <b>bold</b> words</div></body>"
+```
+
+#### -tree-reduce-from `(fn init-value tree)`
+
+Use `fn` to reduce elements of list `tree`.
+If elements of `tree` are lists themselves, apply the reduction recursively.
+
+`fn` is first applied to `init-value` and first element of the list,
+then on this result and second element from the list etc.
+
+The initial value is ignored on cons pairs as they always contain
+two elements.
+
+```cl
+(-tree-reduce-from '+ 1 '(1 (1 1) ((1)))) ;; => 8
+(--tree-reduce-from (-concat acc (list it)) nil '(1 (2 3 (4 5)) (6 7))) ;; => 
'((7 6) ((5 4) 3 2) 1)
+```
+
+#### -tree-mapreduce `(fn folder tree)`
+
+Apply `fn` to each element of `tree`, and make a list of the results.
+If elements of `tree` are lists themselves, apply `fn` recursively to
+elements of these nested lists.
+
+Then reduce the resulting lists using `folder` and initial value
+`init-value`. See `-reduce-r-from`.
+
+This is the same as calling `-tree-reduce` after `-tree-map`
+but is twice as fast as it only traverse the structure once.
+
+```cl
+(-tree-mapreduce 'list 'append '(1 (2 (3 4) (5 6)) (7 (8 9)))) ;; => '(1 2 3 4 
5 6 7 8 9)
+(--tree-mapreduce 1 (+ it acc) '(1 (2 (4 9) (2 1)) (7 (4 3)))) ;; => 9
+(--tree-mapreduce 0 (max acc (1+ it)) '(1 (2 (4 9) (2 1)) (7 (4 3)))) ;; => 3
+```
+
+#### -tree-mapreduce-from `(fn folder init-value tree)`
+
+Apply `fn` to each element of `tree`, and make a list of the results.
+If elements of `tree` are lists themselves, apply `fn` recursively to
+elements of these nested lists.
+
+Then reduce the resulting lists using `folder` and initial value
+`init-value`. See `-reduce-r-from`.
+
+This is the same as calling `-tree-reduce-from` after `-tree-map`
+but is twice as fast as it only traverse the structure once.
+
+```cl
+(-tree-mapreduce-from 'identity '* 1 '(1 (2 (3 4) (5 6)) (7 (8 9)))) ;; => 
362880
+(--tree-mapreduce-from (+ it it) (cons it acc) nil '(1 (2 (4 9) (2 1)) (7 (4 
3)))) ;; => (2 (4 (8 18) (4 2)) (14 (8 6)))
+(concat "{" (--tree-mapreduce-from (cond ((-cons-pair? it) (concat 
(symbol-name (car it)) " -> " (symbol-name (cdr it)))) (t (concat (symbol-name 
it) " : {"))) (concat it (unless (or (equal acc "}") (equal (substring it (1- 
(length it))) "{")) ", ") acc) "}" '((elips-mode (foo (bar . booze)) (baz . 
qux)) (c-mode (foo . bla) (bum . bam))))) ;; => "{elips-mode : {foo : {bar -> 
booze}, baz -> qux}, c-mode : {foo -> bla, bum -> bam}}"
+```
+
+#### -clone `(list)`
+
+Create a deep copy of `list`.
+The new list has the same elements and structure but all cons are
+replaced with new ones.  This is useful when you need to clone a
+structure such as plist or alist.
+
+```cl
+(let* ((a '(1 2 3)) (b (-clone a))) (nreverse a) b) ;; => '(1 2 3)
+```
+
+
 ## Threading macros
 
 #### -> `(x &optional form &rest more)`
diff --git a/dash.el b/dash.el
index aa7c545..2938398 100644
--- a/dash.el
+++ b/dash.el
@@ -980,6 +980,128 @@ The items for the comparator form are exposed as \"it\" 
and \"other\"."
 The items for the comparator form are exposed as \"it\" and \"other\"."
   `(-min-by (lambda (it other) ,form) ,list))
 
+(defun -cons-pair? (con)
+  "Return non-nil if CON is true cons pair.
+That is (A . B) where B is not a list."
+  (and (listp con)
+       (not (listp (cdr con)))))
+
+(defun -cons-to-list (con)
+  "Convert a cons pair to a list with `car' and `cdr' of the pair 
respectively."
+  (list (car con) (cdr con)))
+
+(defun -value-to-list (val)
+  "Convert a value to a list.
+
+If the value is a cons pair, make a list with two elements, `car'
+and `cdr' of the pair respectively.
+
+If the value is anything else, wrap it in a list."
+  (cond
+   ((-cons-pair? val) (-cons-to-list val))
+   (t (list val))))
+
+(defun -tree-mapreduce-from (fn folder init-value tree)
+  "Apply FN to each element of TREE, and make a list of the results.
+If elements of TREE are lists themselves, apply FN recursively to
+elements of these nested lists.
+
+Then reduce the resulting lists using FOLDER and initial value
+INIT-VALUE. See `-reduce-r-from'.
+
+This is the same as calling `-tree-reduce-from' after `-tree-map'
+but is twice as fast as it only traverse the structure once."
+  (cond
+   ((not tree) nil)
+   ((-cons-pair? tree) (funcall fn tree))
+   ((listp tree)
+    (-reduce-r-from folder init-value (mapcar (lambda (x) 
(-tree-mapreduce-from fn folder init-value x)) tree)))
+   (t (funcall fn tree))))
+
+(defmacro --tree-mapreduce-from (form folder init-value tree)
+  "Anaphoric form of `-tree-mapreduce-from'."
+  `(-tree-mapreduce-from (lambda (it) ,form) (lambda (it acc) ,folder) 
,init-value ,tree))
+
+(defun -tree-mapreduce (fn folder tree)
+  "Apply FN to each element of TREE, and make a list of the results.
+If elements of TREE are lists themselves, apply FN recursively to
+elements of these nested lists.
+
+Then reduce the resulting lists using FOLDER and initial value
+INIT-VALUE. See `-reduce-r-from'.
+
+This is the same as calling `-tree-reduce' after `-tree-map'
+but is twice as fast as it only traverse the structure once."
+  (cond
+   ((not tree) nil)
+   ((-cons-pair? tree) (funcall fn tree))
+   ((listp tree)
+    (-reduce-r folder (mapcar (lambda (x) (-tree-mapreduce fn folder x)) 
tree)))
+   (t (funcall fn tree))))
+
+(defmacro --tree-mapreduce (form folder tree)
+  "Anaphoric form of `-tree-mapreduce'."
+  `(-tree-mapreduce (lambda (it) ,form) (lambda (it acc) ,folder) ,tree))
+
+(defun -tree-map (fn tree)
+  "Apply FN to each element of TREE while preserving the tree structure."
+  (cond
+   ((not tree) nil)
+   ((-cons-pair? tree) (funcall fn tree))
+   ((listp tree)
+    (mapcar (lambda (x) (-tree-map fn x)) tree))
+   (t (funcall fn tree))))
+
+(defmacro --tree-map (form tree)
+  "Anaphoric form of `-tree-map'."
+  `(-tree-map (lambda (it) ,form) ,tree))
+
+(defun -tree-reduce-from (fn init-value tree)
+  "Use FN to reduce elements of list TREE.
+If elements of TREE are lists themselves, apply the reduction recursively.
+
+FN is first applied to INIT-VALUE and first element of the list,
+then on this result and second element from the list etc.
+
+The initial value is ignored on cons pairs as they always contain
+two elements."
+   (cond
+   ((not tree) nil)
+   ((-cons-pair? tree) tree)
+   ((listp tree)
+    (-reduce-r-from fn init-value (mapcar (lambda (x) (-tree-reduce-from fn 
init-value x)) tree)))
+   (t tree)))
+
+(defmacro --tree-reduce-from (form init-value tree)
+  "Anaphoric form of `-tree-reduce-from'."
+  `(-tree-reduce-from (lambda (it acc) ,form) ,init-value ,tree))
+
+(defun -tree-reduce (fn tree)
+  "Use FN to reduce elements of list TREE.
+If elements of TREE are lists themselves, apply the reduction recursively.
+
+FN is first applied to first element of the list and second
+element, then on this result and third element from the list etc.
+
+See `-reduce-r' for how exactly are lists of zero or one element handled."
+   (cond
+   ((not tree) nil)
+   ((-cons-pair? tree) tree)
+   ((listp tree)
+    (-reduce-r fn (mapcar (lambda (x) (-tree-reduce fn x)) tree)))
+   (t tree)))
+
+(defmacro --tree-reduce (form tree)
+  "Anaphoric form of `-tree-reduce'."
+  `(-tree-reduce (lambda (it acc) ,form) ,tree))
+
+(defun -clone (list)
+  "Create a deep copy of LIST.
+The new list has the same elements and structure but all cons are
+replaced with new ones.  This is useful when you need to clone a
+structure such as plist or alist."
+  (-tree-map 'identity list))
+
 (eval-after-load "lisp-mode"
   '(progn
      (let ((new-keywords '(
@@ -1109,6 +1231,19 @@ The items for the comparator form are exposed as \"it\" 
and \"other\"."
                            "-max"
                            "-max-by"
                            "--max-by"
+                           "-cons-to-list"
+                           "-value-to-list"
+                           "-tree-mapreduce-from"
+                           "--tree-mapreduce-from"
+                           "-tree-mapreduce"
+                           "--tree-mapreduce"
+                           "-tree-map"
+                           "--tree-map"
+                           "-tree-reduce-from"
+                           "--tree-reduce-from"
+                           "-tree-reduce"
+                           "--tree-reduce"
+                           "-clone"
                            ))
            (special-variables '(
                                 "it"
diff --git a/dev/examples.el b/dev/examples.el
index b0756dc..baf1257 100644
--- a/dev/examples.el
+++ b/dev/examples.el
@@ -263,11 +263,11 @@
     (-select-by-indices '(4 10 2 3 6) '("v" "e" "l" "o" "c" "i" "r" "a" "p" 
"t" "o" "r")) => '("c" "o" "l" "o" "r")
     (-select-by-indices '(2 1 0) '("a" "b" "c")) => '("c" "b" "a")
     (-select-by-indices '(0 1 2 0 1 3 3 1) '("f" "a" "r" "l")) => '("f" "a" 
"r" "f" "a" "l" "l" "a"))
-  
+
   (defexamples -grade-up
     (-grade-up '< '(3 1 4 2 1 3 3)) => '(1 4 3 0 5 6 2)
     (let ((l '(3 1 4 2 1 3 3))) (-select-by-indices (-grade-up '< l) l)) => 
'(1 1 2 3 3 3 4))
-  
+
   (defexamples -grade-down
     (-grade-down '< '(3 1 4 2 1 3 3)) => '(2 0 5 6 3 1 4)
     (let ((l '(3 1 4 2 1 3 3))) (-select-by-indices (-grade-down '< l) l)) => 
'(4 3 3 3 2 1 1)))
@@ -349,6 +349,57 @@
     (--sort (< it other) '(3 1 2)) => '(1 2 3)
     (let ((l '(3 1 2))) (-sort '> l) l) => '(3 1 2)))
 
+(def-example-group "Tree operations" nil
+  (defexamples -tree-map
+    (-tree-map '1+ '(1 (2 3) (4 (5 6) 7))) => '(2 (3 4) (5 (6 7) 8))
+    (-tree-map '(lambda (x) (cons x (expt 2 x))) '(1 (2 3) 4)) => '((1 . 2) 
((2 . 4) (3 . 8)) (4 . 16))
+    (--tree-map (length it) '("<body>" ("<p>" "text" "</p>") "</body>")) => 
'(6 (3 4 4) 7)
+    (--tree-map 1 '(1 2 (3 4) (5 6))) => '(1 1 (1 1) (1 1))
+    (--tree-map (cdr it) '((1 . 2) (3 . 4) (5 . 6))) => '(2 4 6))
+
+  (defexamples -tree-reduce
+    (-tree-reduce '+ '(1 (2 3) (4 5))) => 15
+    (-tree-reduce 'concat '("strings" (" on" " various") ((" levels")))) => 
"strings on various levels"
+    (--tree-reduce (cond
+                    ((stringp it) (concat it " " acc))
+                    (t (let ((sn (symbol-name it))) (concat "<" sn ">" acc 
"</" sn ">"))))
+                   '(body (p "some words") (div "more" (b "bold") "words"))) 
=> "<body><p>some words</p> <div>more <b>bold</b> words</div></body>")
+
+  (defexamples -tree-reduce-from
+    (-tree-reduce-from '+ 1 '(1 (1 1) ((1)))) => 8
+    (--tree-reduce-from (-concat acc (list it)) nil '(1 (2 3 (4 5)) (6 7))) => 
'((7 6) ((5 4) 3 2) 1))
+
+  (defexamples -tree-mapreduce
+    (-tree-mapreduce 'list 'append '(1 (2 (3 4) (5 6)) (7 (8 9)))) => '(1 2 3 
4 5 6 7 8 9)
+    (--tree-mapreduce 1 (+ it acc) '(1 (2 (4 9) (2 1)) (7 (4 3)))) => 9
+    (--tree-mapreduce 0 (max acc (1+ it)) '(1 (2 (4 9) (2 1)) (7 (4 3)))) => 3
+    (--tree-mapreduce (-value-to-list it)
+                      (-concat it acc)
+                      '((1 . 2) (3 . 4) (5 (6 7) 8))) => '(1 2 3 4 5 6 7 8)
+                      (--tree-mapreduce (if (-cons-pair? it) (cdr it) it)
+                                        (concat it " " acc)
+                                        '("foo" (bar . "bar") ((baz . "baz")) 
"quux" (qwop . "qwop"))) => "foo bar baz quux qwop"
+                                        (--tree-mapreduce (if (-cons-pair? it) 
(list (cdr it)) nil)
+                                                          (append it acc)
+                                                          '((elips-mode (foo 
(bar . booze)) (baz . qux)) (c-mode (foo . bla) (bum . bam)))) => '(booze qux 
bla bam))
+
+  (defexamples -tree-mapreduce-from
+    (-tree-mapreduce-from 'identity '* 1 '(1 (2 (3 4) (5 6)) (7 (8 9)))) => 
362880
+    (--tree-mapreduce-from (+ it it) (cons it acc) nil '(1 (2 (4 9) (2 1)) (7 
(4 3)))) => (2 (4 (8 18) (4 2)) (14 (8 6)))
+    (concat "{" (--tree-mapreduce-from
+                 (cond
+                  ((-cons-pair? it)
+                   (concat (symbol-name (car it)) " -> " (symbol-name (cdr 
it))))
+                  (t (concat (symbol-name it) " : {")))
+                 (concat it (unless (or (equal acc "}")
+                                        (equal (substring it (1- (length it))) 
"{"))
+                              ", ") acc)
+                 "}"
+                 '((elips-mode (foo (bar . booze)) (baz . qux)) (c-mode (foo . 
bla) (bum . bam))))) => "{elips-mode : {foo : {bar -> booze}, baz -> qux}, 
c-mode : {foo -> bla, bum -> bam}}")
+
+  (defexamples -clone
+    (let* ((a '(1 2 3)) (b (-clone a))) (nreverse a) b) => '(1 2 3)))
+
 (def-example-group "Threading macros" nil
   (defexamples ->
     (-> "Abc") => "Abc"
reply via email to
[Prev in Thread] Current Thread [Next in Thread]