If you want to do substitution using a function, it seems to me like the operation is more of a roundabout map. Particularly if it's just over the atoms of a tree, it's easy to think of the higher-order functions from a different angle, instead of trying to make tree-subst do everything:
Other name ideas: treemap, maptree, hyphenated versions of any of those, map-leaves.
Digression: the issue I've been more annoyed by in Arc's suite of "tree" utilities is sloppiness with direct cdr recursion. Functions have no way of discerning whether some list (a b c) they're looking at is a "top-level" form or if it's just from recursing on cdrs of (x y z a b c). E.g., using ontree in http://arclanguage.org/item?id=18217:
arc> (let if 2 (+ if (do 2)))
4
arc> (count-ifs-with-do (list '(let if 2 (+ if (do 2)))))
1
arc> (ifs-with-do (list '(let if 2 (+ if (do 2)))))
((if (do 2)))
arc> (ifs (list '(let if 2 (+ if (do 2)))))
((if 2 (+ if (do 2))) (if (do 2)))
I usually want the recursion to instead occur more like
(def ontree (f tree)
(f tree)
(unless (atom tree)
(each subexpr tree
(ontree f subexpr))))
Or even just have the above as a separate function, like on-exprs or something.
I'm pretty sure we have to do the car/cdr recursion because functions like map and each don't work on pairs, they only work on proper lists and most trees are not proper lists. Code such as the following wouldn't work mainly because of the use of map/each.
(treemap [cons 'a _] '(a . a))
I'm pretty sure we would also only want treemap to work only on atoms (your first example), it doesn't make much sense to apply the function then recur on the new tree (I find it very hard to figure out what is going happen). The problem with this is we can no longer call functions on subtrees. I do like the idea of treemap which could be written more cleanly as:
(def treemap (f tree)
(treewise cons f tree))
I'm pretty sure we should stick to akkartik's implementation of tree-subst (we can actually remove the first clause because it is covered in the second clause) because it works just like all of the other higher order functions where they testify their input and it works on entire subtrees.
Note: you can use iff instead of writing a new function whenf
I'm pretty sure we have to do the car/cdr recursion because functions like map and each don't work on pairs, they only work on proper lists and most trees are not proper lists.
I think the obvious problem with that reasoning is it reinforces the notion that map, each, etc. "should" break on dotted lists. Even if that's the case, it's not like ontree & pals couldn't open-code a recursive function that worked on dotted tails; I merely used each/map in my example definitions as a convenience. If you prefer:
; Again, not that this has to replace the standard 'ontree...just can't think
; of a better name.
(def ontree (f expr)
(f expr)
(unless (atom expr)
((afn (subexpr)
(if (atom subexpr)
(and subexpr (ontree f subexpr))
(do (ontree f (car subexpr))
(self (cdr subexpr)))))
expr)))
arc> (ontree prn '(def f (x . xs) (cons nil xs)))
(def f (x . xs) (cons nil xs))
def
f
(x . xs)
x
xs
(cons nil xs)
cons
nil
xs
This versus the standard ontree:
arc> (ontree prn '(def f (x . xs) (cons nil xs)))
(def f (x . xs) (cons nil xs))
def
(f (x . xs) (cons nil xs)) ; <-- this potentially looks like a call to f!
f
((x . xs) (cons nil xs))
(x . xs)
x
xs
((cons nil xs))
(cons nil xs)
cons
(nil xs)
nil
(xs)
xs
nil
nil
On that note, I certainly find myself working around Arc's rampant disregard for dotted lists in my projects:
Note: you can use iff instead of writing a new function whenf
Not in vanilla Arc, I'm afraid. :) And I've always thought Anarki's iff is poorly named, due to the English collision with the "if and only if" abbreviation.
It does seem like a good idea, abstracting as a list of lists instead of a binary tree. The best name I can think of is onlol. I really don't think that we should extend map and each to work on dotted lists, instead we should create other functions treemap and treeach since dotted lists are actually trees and no longer lists.
Hmm, it sounds like we need three sets of primitives: for operating on lists, trees and code (like trees, but aware of call vs arg positions). Perhaps we could use the same names like map and count but first tag the arg as tree or code..?
