Search code examples
haskellrecursion-schemes

How to update a structure with recursion schemes?


In recursion schemes, how can I construct something with type definition like (Recursive t, CoRecursive t) -> t -> ? -> t

I try to use recursion-schemes to update nodes. Taking list as an example, I can come up with two methods like:

update :: [a] -> Natural -> a -> [a]
update = para palg where
  palg Nil _ _ = []
  palg (Cons a (u, _)) 0 b = b : u
  palg (Cons a (u, f)) n b = a : f (n-1) b

update' :: [a] -> Natural -> a -> [a]
update' = c2 (apo acoalg) where
  c2 f a b c = f (a,b,c)
  acoalg ([], _, _) = Nil
  acoalg (_:as , 0, b) = Cons b $ Left as
  acoalg (a:as , n, b) = Cons a $ Right (as, n-1, b)

However, these two implementations are good. In these two implementations, the constructor of ListF and [] appears in both sides of the equation. And the definition does not appear to be unique. Is there a better way to perform List update with recursion schemes?


Solution

  • Recursion schemes is flexible approach. You can also implement your own variant.

    (Reuse cata)

    zipo :: (Recursive g, Recursive h) => (Base g (h -> c) -> Base h h -> c) -> g -> h -> c
    zipo alg = cata zalg
     where
      zalg x = alg x <<< project
    
    update :: forall a. [a] -> Natural -> a -> [a] 
    update xs n a = zipo alg n xs 
      where
        alg :: Maybe ([a] -> [a]) -> ListF a [a] -> [a]
        alg _ Nil = []
        alg Nothing (Cons y ys) = a:ys
        alg (Just n') (Cons y ys) = y:(n' ys)
    

    Also u can implement some parallel version like

    zipCata :: (Recursive g, Recursive h) => ((g -> h -> r) -> Base g g -> Base h h -> r) -> g -> h -> r
    zipCata phi x y = phi (zipCata phi) (project x) (project y)
    
    update' :: forall a. [a] -> Natural -> a -> [a]    
    update' xs n a = zipCata alg n xs 
      where
        alg :: (Natural -> [a] -> [a]) -> Maybe Natural -> ListF a [a] -> [a]
        alg _ _ Nil = []
        alg _ Nothing (Cons _ ys) = a:ys
        alg f (Just n) (Cons y ys) = y:(f n ys)
    

    Both variants (also as your) will be get the same result

    PS. I hate approach for code sample on SO