如何为 Mu 递归类型编写 Show 实例

Question

我想为以下类型的列表编写 Show 的实例：

newtype Mu f = Mu (forall a. (f a -> a) -> a)
data ListF a r = Nil | Cons a r deriving (Show)
type List a = Mu (ListF a)

模块 Data.Functor.Foldable 定义了它，但它把它转换成 Fix，这是我想避免的。

如何定义这个 Show 实例？

Answer 1

先定义自己的代数

showOneLayer :: Show a => ListF a String -> String
showOneLayer ... = ...

然后，

instance Show a => Show (Mu (ListF a)) where
   show (Mu f) = f showOneLayer

Answer 2

口号，"Follow the types!"，全职为我们服务。

根据您的代码，为了更容易理解，进行了一些重命名，

{-# LANGUAGE RankNTypes #-}

data ListF a r = Nil | Cons a r deriving (Show)
newtype List a = Mu {runMu :: forall r. (ListF a r -> r) -> r}

这样我们就可以

fromList :: [a] -> List a
fromList (x:xs) = Mu $ \g -> g   -- g :: ListF a r -> r
                               (Cons x $                 -- just make all types fit
                                  runMu (fromList xs) g)
fromList []     = Mu $ \g -> g Nil

{-   or, equationally,
runMu (fromList (x:xs)) g = g (Cons x $ runMu (fromList xs) g)
runMu (fromList [])     g = g Nil 

     such that (thanks, @dfeuer!)
runMu (fromList [1,2,3]) g = g (Cons 1 (g (Cons 2 (g (Cons 3 (g Nil))))))
-}

我们想要

instance (Show a) => Show (List a) where
 -- show :: List a -> String
 show (Mu f) = "(" ++ f showListF ++ ")"            -- again, just make the types fit

...我们必须生成一个字符串；我们只能调用f；它的论点是什么？根据其类型，

  where
  showListF :: Show a => ListF a String -> String   -- so that, f showListF :: String !
  showListF Nil        = ...
  showListF (Cons x s) = ...

这里没有看到任何其他连接电线的方法。

这样，print $ fromList [1..5] 打印出 (1 2 3 4 5 )。

事实上，这是 chi's 的详细版本。

编辑： g 用于 "algebra"（感谢 @chi！）和 f（在 Mu f 中）适用于 "folding"。现在这个类型的含义变得更清楚了：给定一个 "algebra"（一个归约函数），一个 Mu f 值将在它的 "inherent list" 的折叠中使用它，由这个 "folding function" 表示.它表示具有一步缩减语义的列表折叠，在折叠的 each 步骤上使用它。

Answer 3

如 WillNess 所示，您可能需要一个 newtype 来包装您的 List:

newtype Mu f = Mu {reduce :: forall a. (f a -> a) -> a}
-- I've added a field name for convenience.

data ListF a r = Nil | Cons a r
  deriving (Show, Functor, Foldable, Traversable)
  -- You'll probably want these other instances at some point.

newtype List a = List {unList :: Mu (ListF a)}

WillNess 还写了一个有用的 fromList 函数；这是另一个版本：

fromList :: Foldable f => f a -> List a
fromList xs =
  List $ Mu $ foldr (\a as g -> g (Cons a (as g))) ($ Nil) xs

现在让我们写一个基本的（不太正确）的版本。我将打开 ScopedTypeVariables 以添加类型签名而不会出现烦人的重复。

instance Show a => Show (List a) where
  showsPrec _ xs = reduce (unList xs) go
    where
      go :: ListF a ShowS -> ShowS
      go Nil = id
      go (Cons x r) = (',':) . showsPrec 0 x . r

这将显示一个列表，排序为：

show (fromList []) = ""
show (fromList [1]) = ",1"
show (fromList [1,2]) = ",1,2"

嗯。我们需要安装前导 [ 和尾随 ]，并以某种方式处理额外的前导逗号。做到这一点的一个好方法是跟踪我们是否在第一个列表元素上：

instance Show a => Show (List a) where
  showsPrec _ (List xs) = ('[':) . reduce xs go False . (']':)
    where
      go :: ListF a (Bool -> [Char] -> [Char]) -> Bool -> [Char] -> [Char]
      go Nil _ = id
      go (Cons x r) started =
        (if started then (',':) else id)
        . showsPrec 0 x
        . r True

现在我们真正正确地展示了东西！

但实际上，我们遇到了不必要的麻烦。我们真正需要的只是一个 Foldable 实例：

instance Foldable List where
  foldr c n (List (Mu g)) = g $ \case
    Nil -> n
    Cons a as -> c a as

那么我们可以这样写

instance Show a => Show (List a) where
  showsPrec p xs = showsPrec p (toList xs)

如何为 Mu 递归类型编写 Show 实例

How to write a Show instance for Mu recursive types

haskell

show

recursive-datastructures

fixpoint-combinators