I realized the tree-subst is going to have to be a little more complicated. If the function isn't expecting a list it's going to throw an error.
(tree-subst even [+ _ 1] '((1 . 2) . (3 . 4)))
This code throws an error even though it is very clear what the result should be. I'm not sure what the best way to fix it is. I managed to write a version that does work but it looks pretty ugly.
(def tree-subst (old new tree)
(with (test (testify old)
f (if (isa new 'fn) new (const new)))
(if (no tree) '()
(atom&test tree) (f tree)
(atom tree) tree
t (cons (tree-subst test f (car tree))
(tree-subst test f (cdr tree))))))
I just realized there probably is a better way to write it using treewise. Something like:
(def tree-subst (old new tree)
(with (test (testify old)
f (if (isa new 'fn) new (const new)))
(treewise cons [if (test _) (f _) _] tree)))
But on the other hand tree-subst compared subtrees using is until my change today, and there are no calls to tree-subst in the repo. So I suppose there's no way to see what the original authors had in mind. Anybody else have use cases to share?
On the third hand, it's easy to use tree-subst the way you want with a slight change to the call, like I showed in my tests:
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..?
I didn't notice that your version could check against subtrees. Another possibility would be to use errsafe along with the function (but I'm worried that might be too dangerous). Other than that I would have to agree with your design. I played around with the common lisp design of subst-if and found it does the exact same thing as yours but it also does not test nil. This can easily be done in arc in a similar way to atom&... with idfn&... I would have to go with your design for now but we might want to think about other designs such as whether or not to test nil.
