时间戳

首页 > 解决方案 > 我可以用“递归方案”“cata”来写“foldr”（或“foldMap”）吗？

haskell - 我可以用“递归方案”“cata”来写“foldr”（或“foldMap”）吗？

问题描述

我最近读到了递归方案，其中变态被描述为类似于 generalized foldr。

是否可以在所有情况下编写Foldable（通过foldr或foldMap）的cata实例？

标签： haskellfoldrecursion-schemesfoldablecatamorphism

解决方案

foldMap，作为 的基本操作Foldable，比 . 更适合实施foldr。答案是肯定的。cata只处理递归；它不会告诉您在哪里“找到”结构中的所有值。（同样，实现foldMap @[]withfoldr仍然需要了解 . 的内部细节[]。）这样做需要一点帮助：

class Bifoldable f where
  bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> f a b -> m

然后你可以定义

foldMapDefault ::
  (Recursive (f a), Base (f a) ~ b a, Bifoldable b) =>
  Monoid m => (a -> m) -> f a -> m
foldMapDefault f = cata (bifoldMap f id)

这使您可以执行以下操作

data Tree a = Leaf | Branch (Tree a) a (Tree a)
makeBaseFunctor ''Tree
deriveBifoldable ''TreeF
instance Foldable Tree where foldMap = foldMapDefault

（尽管您也可能刚刚说过deriving Foldable。Tree）为了最大限度地通用，您可能想要更像这样的东西（我说“想要”......）

newtype Fixed f a = Fixed { getFixed :: f a }
newtype Bibase f a b = Bibase { getBibase :: Base (f a) b }
instance (forall a. Recursive (f a), Bifoldable (Bibase f)) =>
         Foldable (Fixed f) where
  foldMap :: forall a m. Monoid m => (a -> m) -> Fixed f a -> m
  foldMap f = cata (bifoldMap f id . Bibase @f @a @m) . getFixed

你现在可以说像

data Tree a = Leaf | Branch (Tree a) a (Tree a)
makeBaseFunctor ''Tree
deriveBifoldable ''TreeF
deriving via TreeF instance Bifoldable (Bibase Tree)
deriving via (Fixed Tree) instance Foldable Tree

但现在你的Base函子可以更不规则：

data List a = Nil | Cons a (List a)
type instance Base (List a) = Compose Maybe ((,) a)
instance Recursive (List a) where
  project Nil = Compose Nothing
  project (Cons x xs) = Compose (Just (x, xs))
instance Bifoldable (Bibase List) where
  bifoldMap f g (Bibase (Compose Nothing)) = mempty
  bifoldMap f g (Bibase (Compose (Just (x, xs)))) = f x <> g xs
deriving via (Fixed List) instance Foldable List

推荐阅读