8

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

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

4

2 回答 2

4

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
于 2019-08-01T10:17:50.557 回答
3

你经常可以，但不是普遍的。所需要的只是一个反例。有几个存在，但考虑一下（我）想到的最简单的一个。

虽然完全没有必要，但您可以使用 F-algebra 定义布尔值：

data BoolF a = TrueF | FalseF deriving (Show, Eq, Read) 

instance Functor BoolF where      
  fmap _  TrueF =  TrueF
  fmap _ FalseF = FalseF

由此（如链接文章所解释的那样），您可以推导出变质：

boolF :: a -> a -> Fix BoolF -> a
boolF x y = cata alg
  where alg TrueF = x
        alg FalseF = y

该类型Fix BoolF与 同构Bool，它不是参数多态的（即它没有类型参数），但存在变态。

Foldable另一方面，类型类是为参数多态容器定义的，t例如

foldr :: (a -> b -> b) -> b -> t a -> b

由于Bool不是参数多态，它不可能是Foldable，但存在变态。Peano 数字也是如此。

另一方面，对于参数多态类型，您通常（也许总是？）可以。这是一个用它的 catamorphism 定义Foldable的树的实例：

instance Foldable TreeFix where
  foldMap f = treeF (\x xs -> f x <> fold xs)

这是一个Maybe：

instance Foldable MaybeFix where
  foldMap = maybeF mempty

一个用于链表：

instance Foldable ListFix where
  foldr = listF
于 2019-08-01T12:05:45.290 回答