I had a late night thought that my sparse quad tree structure can be split up into a bunch of functors.
And that is indeed the case:
type SparseQuadTree a = Free Quad (Sparse (Range a))And the scaffold/compact functions are “bring your own algebra” now.
Replace Quad with Binary or Octal and you’d get the matching structure.
Going from a dense (but lazy) scaffold to sparse states that in type:
(a -> Sparse a) -> Free s a -> Free s (Sparse a)And the decider is a simple function that isn’t concerned with structure at all, making it reusable.
Okay, the numbers level out (with a slight advantage for the Free) when its sampling function becomes complicated (a primitive SDF vs a stack of 100 primitives). I’m now more sure that I’m measuring some right thing, and not some laziness fluke.
@dpwiz "bring your own algebra" sounds fascinating. Can you provide a reference or tell me more, please?
@underlap it’s unfold combinator takes (a -> f a) and that f drives the whole thing. You can then traverse, fold, annotate and aggregate using Functor composition.
@dpwiz That sounds a bit more like a DSL than an algebra. I was probably reading too much into "bring your own algebra"...
@underlap there are only 3 combinators. One for unfolding, and two for merging nodes. The rest are ye olde fmap, traverse, etc.
Maaaybe if you put in your AST as a functor and get a driver for peephole optimisation or something like that. The whole thing reminds me of recursion-schemes contents.
Added bisimulation tests for the Free re-implementation (found 2 bugs
) and got to benchmarking the thing.
I was surprised that a round dance of 3 functors and a ping-pong of functions that pass control around is not only “a little slower” than a tight package, but instead twice as fast!