search

magnars / dash.el

A modern list library for Emacs
GNU General Public License v3.0
1.67k stars 137 forks source link

New function: -tree-map #16

Closed Fuco1 closed 11 years ago

Fuco1 commented 11 years ago

This is another useful abstraction and a fairly common pattern. Works like map but also recursively maps the function to sublists (that is, a "tree" represented by nested lists).

;; helper function
(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)))))

;; the argument order: apply FN to TREE then apply FOLDER, logical :P
(defun -tree-map (fn tree &optional folder)
  "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.

If optional argument FOLDER is non-nil apply this function to the
result of applying FN to each list.  This will convert cons pairs
to lists before applying the FOLDER."
  (cond 
   ((not tree) nil)
   ;; "real" cons pair (a . b), that is `b' is not a list.  This still
   ;; wouldn't work with e.g. (1 2 3 . 4).  ((1 2 3) . 4) is fine.
   ((-cons-pair? tree)
    (let ((res (cons (-tree-map fn (car tree) folder)
                     (-tree-map fn (cdr tree) folder))))
      (if folder (apply folder (car res) (cdr res) nil) res)))
   ((listp tree)
    (let ((res (mapcar (lambda (x) (-tree-map fn x folder)) tree))) 
      (if folder (apply folder res) res)))
   (t
    (funcall fn tree))))

(defmacro --tree-map (form tree &optional folder)
  "Anaphoric form of `-tree-map'."
  `(-tree-map (lambda (it) ,form) ,tree ,folder))

;; examples
(-tree-map '1+ '(1 (2 3) 4)) ;; => (2 (3 4) 5)
(--tree-map (+ 2 it) '(1 (2 3) 4)) ;; => (3 (4 5) 6)
(--tree-map (case it (+ '-) (- '+) (t it)) '(+ 1 2 (- 4 5) (+ 3 4))) ;; => (- 1 2 (+ 4 5) (- 3 4))

This can be used to implement other functions, such as:

;; this version can also flatten alists. SUPER HANDY!
(defun -flatten (list)
  "Take a nested list LIST and return its content as a single, flat list."
  (-tree-map 'list list 'append))

(-flatten '(("(" . ")") ("[" . "]") ("{" . "}") ("`" . "'"))) ;; => ("(" ")" "[" "]" "{" "}" "`" "'")

;; possible name: -clone
(defun -copy (list)
  "Create a deep copy of LIST.
The new list has the same elements 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))

(defmacro -R (&rest forms)
  "Return a function that applies FORMS to (list it)."
  `(lambda (&rest it) ,@forms))

(defun -tree-reverse (tree)
  "Reverse the TREE while preserving the structure."
  (-tree-map 'identity tree (-R (nreverse it))))

(-tree-reverse '((1 (2 3)) (4 5 6))) ; ;; => ((6 5 4) ((3 2) 1))

;; some more examples
(-tree-map 'identity '((1 4 5) (0 (1 2 (3 (3 4) 4)))) '+) ;; => 27
(--tree-map (list (+ 2 it)) '((1 4 5) (0 (1 2 (3 (3 4) 4)))) 'append) ;; => (3 6 7 2 3 4 5 5 6 6)
;; number of items in tree
(--tree-map 1 '((1 4 5) (0 (1 2 (3 (3 4) 4)))) '+) ;; => 10
;; tree depth
(--tree-map 0 '((1 4 5) (0 (1 2 (3 (3 4) 4)))) (-R (1+ (apply 'max it)))) ;; => 5

;; generate HTML from sexps!
(-tree-map 'identity '(html 
                       (head (title "Hello! " "this is" " my homepage"))
                       (body 
                        (p "Welcome, this is " (b "amazing") " fun")
                        (p "Second paragraph."))) 
           (-R (concat
                "<"
                (symbol-name (car it))
                ">"
                (apply 'concat (cdr it))
                "</"
                (symbol-name (car it))
                ">"
                )))

;; output split for readability
;; "<html><head><title>Hello! this is my homepage</title></head>
;; <body><p>Welcome, this is <b>amazing</b> fun</p><p>Second paragraph.</p></body></html>"

Especially the -copy/-clone function is really handy if you work a lot with plists. Because their internal crazy rules for updates... it's just safer to do a copy each time.

magnars commented 11 years ago

Wow, this looks really excellent. Thank you, Matus. I'll get this in pretty soon.

magnars commented 11 years ago

Would you mind splitting this up into -tree-map and -tree-reduce and remove the optional param?

Fuco1 commented 11 years ago

All right, I'm on it. But I feel like sometimes it's handy to have both "mapper" and "reducer" in the single function. Maybe it could be called -tree-mapreduce then. Consider this example:

(--tree-map 1 '((1 4 5) (0 (1 2 (3 (3 4) 4)))) '+)

Very elegant way to find the number of elements in the list. Otherwise it would need two steps, first convert the list into ((1 1 1) (1 (1 1 (1 (1 1) 1)))) and then reduce it with +

That could be achieved using (-tree-reduce '+ (--tree-map 1 '(...))) but currently it's twice as fast as it only traverse the structure once.

So I guess the best solution would be to keep the current version as -tree-mapreduce and provide two new functions: -tree-map, -tree-reduce.

Also the -R macro could be given better name. What it does it it turns the form into "applyable" function. Since apply expect the last argument as a list, if we want our function to operate on the whole list then we need to pass "list of list" to apply because it "splices" the last argument to the funciton. That's why we can apply functions like + or append or concat right away (because they already expect a &rest argument). The functions that operate on just one list attribute need to be "transformed" to (lambda (&rest x) (function x)).

This could be theoretically fixed providing two versions of the function... But then that would jump to 4 with anaphoric versions, so I think it's better to have a helper macro (it's also cleaner when you read the code, I think). Or one can just write it out in total, it's not that long.

(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 -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 apply FOLDER to the result of applying FN to each list.
This will convert cons pairs to lists before applying the FN.

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)
    (apply folder
           (-tree-mapreduce fn folder (car tree))
           (-tree-mapreduce fn folder (cdr tree))
           nil))
   ((listp tree)
    (apply 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) ,folder ,tree))

(defun -tree-map (fn 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."
  (cond
   ((not tree) nil)
   ((-cons-pair? tree)
    (cons (-tree-map fn (car tree))
          (-tree-map fn (cdr 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 (fn tree)
  "Use FN to reduce elements of TREE.
If the elements are themselves trees apply the reduction recursively.

This will convert cons pairs to lists before applying FN."
   (cond
   ((not tree) nil)
   ((-cons-pair? tree)
    (apply fn (car tree) (cdr tree) nil))
   ((listp tree)
    (apply 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) ,form) ,tree))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defmacro -R (&rest forms)
  "Return a function that applies FORMS to (list it)."
  `(lambda (&rest it) ,@forms))

;; this is more like an example than an actual function to add
(defun -tree-reverse (tree)
  "Reverse the TREE while preserving the structure."
  (-tree-reduce (-R (nreverse it)) tree))

(-tree-reverse '((1 (2 3)) (4 5 6))) ; ;; => ((6 5 4) ((3 2) 1))

;; this version can also flatten alists. SUPER HANDY!
(defun --flatten (list)
  "Takes a nested list L and returns its contents as a single, flat list."
  (-tree-mapreduce 'list 'append list))

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

;;; More examples
(-tree-reduce '+ '((1 4 5) (0 (1 2 (3 (3 4) 4))))) ;; => 27

;; structural manipulation
(--tree-map (case it (+ '-) (- '+) (t it))
            '(+ 1 2 (- 4 5) (+ 3 4))) ;; => (- 1 2 (+ 4 5) (- 3 4))

;; depth of tree
(--tree-mapreduce 0 (-R (1+ (apply 'max it))) '((1 4 5) (0 (1 2 (3 (3 4) 4)))))

;; number of items in tree
(--tree-mapreduce 1 '+ '((1 4 5) (0 (1 2 (3 (3 4) 4)))))

(--tree-mapreduce (list (+ 2 it)) 'append '((1 4 5) (0 (1 2 (3 (3 4) 4))))) ;; => (3 6 7 2 3 4 5 5 6 6)

;; generate HTML from sexps!
(-tree-reduce (-R (concat
                   "<"
                   (symbol-name (car it))
                   ">"
                   (apply 'concat (cdr it))
                   "</"
                   (symbol-name (car it))
                   ">"
                   )) 
              '(html 
                (head (title "Hello! " "this is" " my homepage"))
                (body 
                 (p "Welcome, this is " (b "amazing") " fun")
                 (p "Second paragraph."))))
magnars commented 11 years ago

I see your point in having both map, reduce and mapreduce. Having an explicit mapreduce enables both functions to be before the list in the params list. Excellent. -R makes me think of -applify.

Any thoughts on why the anaphoric form of mapreduce takes one form and one function? Should they both be forms?

These are some pretty great examples. Powerful stuff.

Fuco1 commented 11 years ago

Well, now that I think about it, we could make the form in --tree-reduce and --tree-mapreduce for the folder be as if returned by -R, so it will free the user from using that macro. So then the reverse tree function would be even simper:

(defmacro --tree-reduce (form tree)
  "Anaphoric form of `-tree-reduce'."
  `(-tree-reduce (lambda (&rest it) ,form) ,tree))

(--tree-reduce (nreverse it) tree)
;; expands to
(-tree-reduce (lambda (&rest it) (nreverse it)) tree)
;; which is the same as
(-tree-reduce (-R (nreverse it)) tree)

That is after all expected because all the functions that go into the functional version have signature (fn &rest stuff) (see append, concat, + etc.) So a default transformation into that kind of function makes sense.

However, that will make using the "applicative" functions ugly because then they would need to be applied twice (and I'm using applicative here for the lack of terminology, it's not applicative from haskell). That is because they already expect argument in the form &rest and if we transform them into lambda that takes &rest the argument will be "list of list".

For example, to use + with the anaphoric version you'd need:

(--tree-reduce (apply '+ it) '(1 (2 3) (1 (1 (1 1) 1 (1 1)))))
;; expands to
(-tree-reduce (lambda (&rest it) (apply '+ it)) '(1 (2 3) (1 (1 (1 1) 1 (1 1))))) ;; => 13

(--tree-reduce (apply 'concat it) '("a" ("b" "c") "d"))
;;expands to
(-tree-reduce (lambda (&rest it) (apply 'concat it)) '("a" ("b" "c") "d")) ;; => "abcd"

Which again makes sense because basically the --tree-reduce forms should be functions that operate on lists (for example (nreverse it) expect a list as an argument). And (apply '+ it) is a funciton that takes as an argument a list (a list of values to sum). This can be fixed by a "reverse macro" to -R that would be something like:

(defmacro -A (function)
  "Turn the function into \"applicative\" form."
  `(apply ',function it))

So then you can do:

(--tree-reduce (-A +) '(1 (2 3) 4)) ;; => 10
(--tree-reduce (-A concat) '(("[" . "]") ("{" . "}"))) ;; => "[]{}"

This obviously doesn't make sense for --tree-reduce where you could just call (-tree-reduce '+ '(list)) right away. However, with --tree-mapreduce you need to pick one style.

Third option is to test if the input form is a function, if it is than leave it be and if it's a form transform it into -R automatically. I guess this could be done using functionp in the macro.

(defmacro --tree-reduce (form tree)
  `(if (functionp ,form)
       (-tree-reduce ,form ,tree)
     (-tree-reduce (lambda (&rest it) ,@(cdr form)) ,tree)))

(--tree-reduce '+ '(1 (2 3) 4)) ;; => 10
(--tree-reduce '(nreverse it) '(1 (2 3) 4)) ;; => (4 (3 2) 1)

but this has the disadvantage of needing to quote the form as well (which is used nowhere in dash and so would make the interface weird). I can't figure out how to test it without quoting the form.

Fuco1 commented 11 years ago

Hm, this seems to work (the name is with three dashes so you can test it without redefining the normal version)

(defmacro ---tree-reduce (form tree)
  (let ((form-to-test (if (and (listp form)
                               (eq (car form) 'quote))
                          `,form
                        `(quote ,form))))
    `(if (functionp ,form-to-test)
         (-tree-reduce ,form-to-test ,tree)
       (-tree-reduce (lambda (&rest it) ,@(cdr form-to-test)) ,tree))))

All of these are valid:

(---tree-reduce '(nreverse it) '(1 (2 3) 4))
(---tree-reduce (nreverse it) '(1 (2 3) 4))
(---tree-reduce + '(1 (2 3) 4)) 
(---tree-reduce '+ '(1 (2 3) 4))

With this, technically, you won't even need the anaphoric/normal version distinction. It is slightly less efficient as it has to do the functionp test during runtime though. But that's pretty fast I guess.

nicferrier commented 11 years ago

is this in yet? would be great to have this.

Fuco1 commented 11 years ago

I agree :D

I was also recently thinking about somehow making this into full-blown catamorphisms, but with the lack of type system and rather awkward constructions concerning currying/composition/matching in LISP it would be more pain than use, I think. Plus the list and tree variants are probably the most used anyway.

It is of course fairly simple to write specialized variants for new structures if the need arises.

I was also thinking about simulating monads, but that's a different topic. I need to keep reminding me that LISP is not Haskell!

Last thing that keeps bugging me are the -R/-A macros. It feels rather ugly. I wonder if we could maybe implement our own version of apply that would somehow work with both kinds of functions (the "rest" functions like '+ and "give me a list" functions like nreverse). That would make it a lot cleaner. I don't know however if it is possible to extract this "type" information from the function.

(N.B.: with catamorphisms you can "fold" and "map" over any data structure at all, provided you supply a bit of structural information about the structure, namely "where to apply recursion")

magnars commented 11 years ago

No, I've got my hands full lately. Will try to get it in this weekend. I don't like adding stuff when I'm not sure about the API, so I'll likely leave out the -A and -R for now.

On Saturday, March 9, 2013, Matus Goljer wrote:

I agree :D

I was also recently thinking about somehow making this into full-blown catamorphisms, but with the lack of type system and rather awkward constructions concerning currying/composition/matching in LISP it would be more pain than use, I think. Plus the list and tree variants are probably the most used anyway.

It is of course fairly simple to write specialized variants for new structures if the need arises.

I was also thinking about simulating monads, but that's a different topic. I need to keep reminding me that LISP is not Haskell!

Last thing that keeps bugging me are the -R/-A macros. It feels rather ugly. I wonder if we could maybe implement our own version of apply that would somehow work with both kinds of functions (the "rest" functions like '+ and "give me a list" functions like nreverse). That would make it a lot cleaner.

(N.B.: with catamorphisms you can "fold" and "map" over any data structure at all, provided you supply a bit of structural information about the structure, namely "where to apply recursion")

— Reply to this email directly or view it on GitHubhttps://github.com/magnars/dash.el/issues/16#issuecomment-14663459 .

Fuco1 commented 11 years ago

If you want I'll send you a pull request with the version we've agreed on, so you don't have to re-read all this.

magnars commented 11 years ago

That would be great!

On Saturday, March 9, 2013, Matus Goljer wrote:

If you want I'll send you a pull request with the version we've agreed on, so you don't have to re-read all this.

— Reply to this email directly or view it on GitHubhttps://github.com/magnars/dash.el/issues/16#issuecomment-14664579 .

Fuco1 commented 11 years ago

I'm gonna close this and the other discussion and I'll send you a new pull request. The old one would likely have conflicts and other problems.