如何为 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)

Module Data.Functor.Foldable定义了它，但它将其转换为Fix，这是我想避免的。

如何定义此Show实例？

Answer 1

口号">遵循类型！">在这里为我们工作，全职。

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

{-# 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 ).

事实上，这竟然是池的回答的冗长版本。

编辑：g用于"代数"(谢谢，@chi！(，f(Mu f(用于"折叠"。现在这种类型的含义变得更加清晰：给定一个"代数"(约简函数(，Mu f值将使用它来折叠由这个"折叠函数"表示的"固有列表"。它表示具有一步缩减语义的列表的折叠，并在折叠的每个步骤中使用它。

Answer 2

首先定义自己的代数

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

然后

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

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)