specter
specter copied to clipboard
redplanetlabs
Stateful navigators
This is an idea for navigators which use state to make navigation decisions. Examples:
(select [ALL (takenav 3)] [1 2 3 4 5])
;; => [1 2 3]
(select [ALL STREAM-UNIQUE] [1 2 2 3 3])
;; => [1 2 3]
(transform [ALL ALL (takenav 3)] inc [[1 2] [3 4 5] [6]])
;; => [[2 3] [4 4 5] [6]]
(transform [ALL STREAM-UNIQUE] - [1 2 2 3 3])
;; => [-1 -2 2 -3 3]
The state is always re-initialized for every run, and the stateful navigator defines how to initialize its state.
Here is what takenav would look like:
(defstatefulnav takenav [p]
[s (volatile! p)]
(select* [this structure next-fn]
(if (zero? @s) NONE (do (set! s (dec @s)) (next-fn structure)))
)
(transform* [this structure next-fn]
(if (zero? @s) structure (do (set! s (dec @s)) (next-fn structure)))
))
Implementation-wise, this would be done using late-bound parameterization along with logic during inline factoring. For example, the following path would factor like so:
[ALL (takenav 3)]
->
[ALL takenav]
And the parameters function would be generated as follows:
(fn []
...
(aset a 0 3)
(aset a 1 (volatile! 3))
)
In summary, stateful navigation functions is a late-bound parameterized navigator with some extra logic done during inline factoring to thread things together.
One open question: is there any way to get something like [ALL (takenav 3)] to stop iterating over the sequence after the 3rd element (for efficiency)? Are transducers capable of this?
Further ideas:
@aengelberg brought up the idea of stateful navigators that reset in the middle of a path. Seems like a natural use case this feature should support. Here's one way to do it:
(select [ALL (freshpath ALL (take-nav 2)) (take-nav 4)]
[[1] [2 3 4] [5 6 7]])
;; => [1 2 3 5]
freshpath would treat its path "from scratch", re-parameterizing it (which would initialize the states) and starting with [] for collected vals. Another possible name is resetted.
Implementation-wise, freshpath would be a macro that generates a function that wraps its path in path. That function would be a parameter to a navigator that calls the function on invocation and then uses compiled-transform* or compiled-traverse* to complete the appropriate operation.
@Pancia Likely Specter would have to leverage that or do something similar. I looked at the Clojure code and it's up to the reduce function on the collection to detect early termination and deref the Reduced object. It's a little trickier in Specter's case because you can do [ALL :a (takenav 3)] in which case
the Reduced object would have to be funneled back through the :a navigator to ALL where it can be used for early termination.
Certain (if not all) stateful navigators have equivalents in terms of subselect, though not necessarily as efficient.
;; With hypothetical take-nav
[ALL :a (take-nav 3)]
;; Doable with subselect
[(subselect ALL :a) (srange 0 3) ALL]
I keep finding use cases for stateful navigations in a tree that has IDs that reference other nodes in the tree. Is there a known pattern for this? e.g. capture some node ids in the navigator path, when when I encounter a leaf ID, use that ID path to drill down to the node that matches the leaf ID reference. Right now it's multiple passes through the datastructure with Specter to get there.
@eslick If you're moving laterally through the tree, you'll need zippers. Using value collection along with collected? would let you filter leaves by ids you collected elsewhere.
Problem I'm looking at is a little different. Imagine I have a tree of maps with a parent tree {id component} and within a component I have a subtree of {id asset} and then I have other parts of the component subtree that have {:assetRef id} which can show up in multiple locations. I'd like to be able to extract data from the asset while I'm in the component subtree that refers to it. I can do this by passing in a closure with the entire tree and doing a subquery, but then I have to query over all components. What I'd like to do is perform that subquery using a collected path, but not as part of the transform. That is to say I have a navigator that takes as an argument the current collected elements and uses that to parameterize a step in the navigation. It's possible this capability exists and I'm just missing it!
@eslick I've just started exploring today is something which I think is close to what you're talking about.
In our case we have a data structure and a notion of our location in the data structure (or index into the another part of the data structure) which is all kept together. When we want to transform the data structure we need to 'know' our location and hence from where to start the transformation and those transformations can themselves change the location/index. I'm sorry that description is so opaque.
What I'm exploring now is collecting the index at the root transformation and using it in the transform method. Another way of looking at it is we 'side-load' the indices into all transformations.
We also batch these transformations together and run them all in one multi-transform so we really do need a running, up to date, set of indices for each transformation. The navigators end up looking something like:
(def CURRENT-THING
(sp/richnav
[]
(select*
[_ vals structure next-fn]
....)
(transform*
[_ vals structure next-fn]
(let [[indices & other-collected] vals
next-fn (fn [x] (next-fn vals x))]
(sp/transform
[:things
(navigate-to indices)]
#(next-fn %)
structure)))))
... of which I have the start of a macro mostly similar to defrichnav that takes care of all the boiler plate.
Caveat; I have no idea whether this will work out or whether it's even a sane thing to do in specter :)
Hi guys, I'm not sure to understand precisely your use cases, but I am looking how to build the topological order of my nested maps. Root nodes set to 0, their child to 1, and so on.
From what I understand here, I'm missing a feature like stateful navigator to perform that. Am I right - is it a new use case for this feature? Thanks in advance.
Here is what I wrote in vanilla clojure awaiting for your answer:
)
(defn do-assign-metadata [json-map level]
(cond
(map? json-map) (into (level-assign level {})
(for [[k v] json-map]
[k (do-assign-metadata v
(inc level))]
))
(vector? json-map) (into (level-assign level [])
(for [val json-map]
(do-assign-metadata val (inc level))
))
:else json-map
)
)
(defn assign-metadata [json-map]
(do-assign-metadata json-map 0)
)
