Recursion Schemes

[fosskers]

If RFML was v1 of this little DSL of ours, and the current Directive-based formulation is v2, then moving recursion schemes would be our v3. Luckily, our current architecture isn't far off from RSs already. If you squint, you can see them there (i.e. directives are part of an Algebra, and evaluation is just a catamorphism. Functions like Interpreter.naive build the Algebra officially).

Before breaking MAML out, we had lamented that making ASTs handle multiple return types would be a nightmare. That wasn't actually true, all we needed was an ADT of possible return types which would then be matched upon at each Algebra step. This is the purpose of the Result ADT in MAML, and we can see a hint of this idea in the original RDD interpreter where Either was being returned.

So given these tools - Recursion Schemes and a Result return type - we can achieve our multityped AST with very little "type shenanigans". Here's a prototype in Haskell:

{-# LANGUAGE DeriveFunctor #-}

module RS where

import Data.Foldable (foldlM)
import Data.Functor.Foldable

---

-- | A "pattern functor" for a MAML expression tree.
data ExprF a t = Leaf a | Add [t] | Mul [t] deriving (Show, Functor)

-- | A handy alias.
type Expr a = Fix (ExprF a)

-- | "Smart constructors".
leaf :: a -> Expr a
leaf = Fix . Leaf

add :: Expr a -> Expr a -> Expr a
add e0 e1 = Fix $ Add [e0, e1]

mul :: Expr a -> Expr a -> Expr a
mul e0 e1 = Fix $ Mul [e0, e1]

-------------------
-- TILE INTERPRETER
-------------------

-- | GeoTrellis types.
newtype Tile a = Tile [a] deriving (Show, Functor)
newtype MultibandTile a = MultibandTile [Tile a] deriving (Show, Functor)

-- | ADT of possible values that nodes can handle.
data Maml = Lit Int | Single (Tile Int) | Banded (MultibandTile Int) deriving (Show)

algebra :: ExprF Maml (Maybe Maml) -> Maybe Maml
algebra (Leaf m) = Just m
algebra (Add ms) = sequence ms >>= foldlM (resolve (+)) (Lit 0)
algebra (Mul ms) = sequence ms >>= foldlM (resolve (*)) (Lit 1)

-- | Resolve a binary operation between two `Maml` values.
resolve :: (Int -> Int -> Int) -> Maml -> Maml -> Maybe Maml
resolve f (Lit n) (Lit m)        = Just . Lit $ f n m
resolve f (Lit n) (Single t)     = Just . Single $ fmap (f n) t
resolve f t@(Single _) n@(Lit _) = resolve f n t
resolve f (Lit n) (Banded t)     = Just . Banded $ fmap (f n) t
resolve f t@(Banded _) n@(Lit _) = resolve f n t
resolve _ _ _                    = Nothing

eval :: Expr Maml -> Maybe Maml
eval = cata algebra

Notes:

• Maml is a convenient fusion of MamlKind and Result
• The individual directives have been merged back into a single algebra, with fine-grained pattern matching on the child return values handled by some plumbing function (resolve here)
• Maybe Maml in ExprF Maml (Maybe Maml) is the "carrier type" we're used to from recursion schemes
• The final return type being Maybe Maml was just for convenience of prototyping. It could easily be Validated to collect all errors found along the tree.

[fosskers]

Here's a second Algebra example that could be used to count the number of nodes in the tree:

algebra :: Expr Maml Int -> Int
algebra (Leaf m) = 1
algebra (Add ms) = 1 + sum ms
algebra (Mul ms) = 1 + sum ms

Notice how the "carrier type" differs from above.

[pomadchin]

Bumping it up; We tried to use rec schemes here geotrellis/geotrellis-server#207

The PR above is a simple use case with simple (co)algebras implemented for unrelated (via subtyping) datatypes. It also shows the fold of a DSL tree into the result, unfolding and folding it into / from JSON and getting an ability to parse json and evaluate query via hylo (basically for free, since at this point we'll have both algebra to fold query and coalgebra to construct it from the JSON).