教会编码列表的变形

Question

我希望能够使用cata从recursion-schemes包在教会编码的列表。

type ListC a = forall b. (a -> b -> b) -> b -> b

为了方便，我用了第二种类型，但我不在乎。如果你觉得有必要的话，可以随意添加一个newtype，使用add等等。

教会编码的思想是广为人知和简单的：

three :: a -> a -> a -> List1 a 
three a b c = \cons nil -> cons a $ cons b $ cons c nil

基本上使用“抽象未指定”的cons和nil，而不是“普通”构造函数。我相信一切都可以这样编码(Maybe，trees，等等)。

很容易证明List1确实与普通列表同构：

toList :: List1 a -> [a]
toList f = f (:) []

fromList :: [a] -> List1 a
fromList l = \cons nil -> foldr cons nil l

因此，它的基函子与列表是相同的，应该可以为它实现project，并使用来自recursion-schemes的机器。

但我做不到，所以我的问题是“我该怎么做？”对于普通列表，我只需匹配模式：

decons :: [a] -> ListF a [a]
decons [] = Nil
decons (x:xs) = Cons x xs

因为我不能在函数上进行模式匹配，所以我不得不使用折叠来解构列表。我可以为普通列表编写一个基于折叠的project：

decons2 :: [a] -> ListF a [a]
decons2 = foldr f Nil
  where f h Nil = Cons h []
        f h (Cons hh t) = Cons h $ hh : t

然而，我没有把它改编成教会编码的列表：

-- decons3 :: ListC a -> ListF a (ListC a)
decons3 ff = ff f Nil
  where f h Nil = Cons h $ \cons nil -> nil
        f h (Cons hh t) = Cons h $ \cons nil -> cons hh (t cons nil)

cata具有以下签名：

cata :: Recursive t => (Base t a -> a) -> t -> a

要将它与我的列表一起使用，我需要：

1. 使用type family instance Base (ListC a) = ListF a声明列表的基函子类型
2. 实现instance Recursive (List a) where project = ...

我两步都失败了。

Answer 1

事实证明，newtype包装是我错过的关键一步。下面是代码以及来自recursion-schemes的一个样本变形。

{-# LANGUAGE LambdaCase, Rank2Types, TypeFamilies #-}

import Data.Functor.Foldable

newtype ListC a = ListC { foldListC :: forall b. (a -> b -> b) -> b -> b }

type instance Base (ListC a) = ListF a

cons :: a -> ListC a -> ListC a
cons x (ListC xs) = ListC $ \cons' nil' -> x `cons'` xs cons' nil'
nil :: ListC a
nil = ListC $ \cons' nil' -> nil'

toList :: ListC a -> [a]
toList f = foldListC f (:) []
fromList :: [a] -> ListC a
fromList l = foldr cons nil l

instance Recursive (ListC a) where
  project xs = foldListC xs f Nil
    where f x Nil = Cons x nil
          f x (Cons tx xs) = Cons x $ tx `cons` xs

len = cata $ \case Nil -> 0
                   Cons _ l -> l + 1