[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/dash 75efb60 246/426: Add tree map/reduce
From: |
Phillip Lord |
Subject: |
[elpa] externals/dash 75efb60 246/426: Add tree map/reduce |
Date: |
Tue, 04 Aug 2015 19:38:03 +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"
- [elpa] externals/dash d1913c6 210/426: Merge pull request #41 from Wilfred/master, (continued)
- [elpa] externals/dash d1913c6 210/426: Merge pull request #41 from Wilfred/master, Phillip Lord, 2015/08/04
- [elpa] externals/dash b4d84de 243/426: Add debug declarations for `-when-let`s and `-if-let`s, Phillip Lord, 2015/08/04
- [elpa] externals/dash 6d43c4f 235/426: Fix switched around doc strings for -find-index/indices, Phillip Lord, 2015/08/04
- [elpa] externals/dash 459322d 244/426: Update docs, Phillip Lord, 2015/08/04
- [elpa] externals/dash 9936885 245/426: Merge pull request #51 from Fuco1/debug-decl, Phillip Lord, 2015/08/04
- [elpa] externals/dash 0f4cae9 249/426: Improve docs, Phillip Lord, 2015/08/04
- [elpa] externals/dash 23ab726 227/426: Improve formatting of docs, Phillip Lord, 2015/08/04
- [elpa] externals/dash f4ba8db 252/426: Add -snoc, Phillip Lord, 2015/08/04
- [elpa] externals/dash bf85b21 242/426: Change &optional branches to &rest branches in `-if-let`s, Phillip Lord, 2015/08/04
- [elpa] externals/dash bf99147 247/426: Fix `-tree-mapreduce-from` test & reformat the tests, Phillip Lord, 2015/08/04
- [elpa] externals/dash 75efb60 246/426: Add tree map/reduce,
Phillip Lord <=
- [elpa] externals/dash 2ee84cb 251/426: Release 2.3.0, Phillip Lord, 2015/08/04
- [elpa] externals/dash ab727ba 257/426: Correct anchors for links starting with '!', Phillip Lord, 2015/08/04
- [elpa] externals/dash 8052eb9 253/426: Merge pull request #55 from Fuco1/snoc, Phillip Lord, 2015/08/04
- [elpa] externals/dash d8ccf85 254/426: Add replace/update/remove functions for index/indices, Phillip Lord, 2015/08/04
- [elpa] externals/dash ba6e3c6 260/426: Add missing keywords, Phillip Lord, 2015/08/04
- [elpa] externals/dash 87bcbc8 261/426: Merge pull request #59 from Fuco1/add-keywords, Phillip Lord, 2015/08/04
- [elpa] externals/dash 094fdea 262/426: Merge pull request #58 from Fuco1/fontlock-custom, Phillip Lord, 2015/08/04
- [elpa] externals/dash ca9b296 263/426: Add Cask-file., Phillip Lord, 2015/08/04
- [elpa] externals/dash 3bbaed5 256/426: Release 2.4.0, Phillip Lord, 2015/08/04
- [elpa] externals/dash 8005153 259/426: Add customize option to turn on font-lock for dash, Phillip Lord, 2015/08/04