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.
@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.
