Include RAlgebra version of `para`

[kevinbarabash]

I've been studying a series of blog posts on recursion schemes. The third in the series covers para. It shows a different formulation of para using an RAlgebra instead of a GAlgebra like matryoshka's para. I find both versions of para are useful in different situations. Here's one example of where the RAlgebra version from the blog post results in less boilerplate:

data ExprF a
  = Num Number
  | Var String
  | Add (Array a)
  | Sub a a
  | Mul (Array a)
  | Div a a

-- using GAlgebra para
removeAddZero :: Expr -> Maybe Expr
removeAddZero = para removeAddZeroF
  where
    removeAddZeroF :: ExprF (Tuple Expr (Maybe Expr)) -> Maybe Expr
    removeAddZeroF (Add args) = do
      let 
        args' = (foldl (\acc x -> 
          case snd x of
            Just y -> case unroll y of
              Num 0.0 -> acc
              _ -> acc <> [y]
            Nothing -> acc
          ) [] args)
      case args' of
        [] -> Nothing
        [x] -> Just x
        xs -> Just (roll $ Add xs)
    removeAddZeroF (Num x) = Just $ num x
    removeAddZeroF (Var x) = Just $ var x
    removeAddZeroF (Sub x y) = Just $ sub (fst x) (fst y)
    removeAddZeroF (Div x y) = Just $ div (fst x) (fst y)
    removeAddZeroF (Mul args) = Just $ mul $ map fst args

type RAlgebra f a = Mu f -> f a -> a

para' :: forall f a. Functor f => RAlgebra f a -> Mu f -> a
para' alg t = unroll t # map (para'' alg) # alg t

-- using RAlgebra para'
removeAddZero' :: Expr -> Maybe Expr
removeAddZero' = para' removeAddZeroF'
  where
    removeAddZeroF' :: RAlgebra' ExprF (Maybe Expr) -- Expr -> ExprF (Maybe Expr) -> Maybe Expr
    removeAddZeroF' _ (Add args) = do
      let 
        args' = (foldl (\acc x -> 
          case x of
            Just y -> case unroll y of
              Num 0.0 -> acc
              _ -> acc <> [y]
            Nothing -> acc
          ) [] args)
      case args' of
        [] -> Nothing
        [x] -> Just x
        xs -> Just (roll $ Add xs)
    removeAddZeroF' x _ = Just x

I was wondering if you'd be willing to include para' and RAlgebra as part of matryoshka?

[cryogenian]

Hello! RAlgebra is the same thing as GAlgebra

type RAlgebra f a = Mu f -> f a -> a 
-uncurring-> 
Tuple (Mu f) (f a) -> a 
-abstracting over Mu ->
Corecursive t f =>Tuple t (f a) -> a 
-use type synonim -> 
Corecursive t f => GAlgebra((Tuple t), f a)

BTW you can use the same "catch all case" with GAlgebra

-- using GAlgebra para
removeAddZero :: Expr -> Maybe Expr
removeAddZero = para removeAddZeroF
  where
    removeAddZeroF :: ExprF (Tuple Expr (Maybe Expr)) -> Maybe Expr
    removeAddZeroF (Add args) = do
      let 
        args' = (foldl (\acc x -> 
          case snd x of
            Just y -> case unroll y of
              Num 0.0 -> acc
              _ -> acc <> [y]
            Nothing -> acc
          ) [] args)
      case args' of
        [] -> Nothing
        [x] -> Just x
        xs -> Just (roll $ Add xs)
    removeAddZeroF fx = Just $ embed fx

[kevinbarabash]

@cryogenian thank you for sharing this. I was struggling to figure out the "catch all case" with GAlgebra. That's super cool that RAlgebra can be written using GAlgebra.