1

（这不是专门的 Haskell 问题。）

我有一个递归数据结构。我想在它的每个级别附加一些额外的信息。这是一个简化的示例，其中我将 anX或 a添加Y到树的每个级别：

import Data.Functor.Foldable

data Wrap a = X a | Y a
  deriving Show

data TreeF a b = Leaf a | TreeF a b b
  deriving Show

depth1 :: Wrap (TreeF Int ())
depth1 = X (Leaf 1)

depth2 :: Wrap (TreeF Int (Wrap (TreeF Int ())))
depth2 = Y (TreeF 1 (X $ Leaf 1) (Y $ Leaf 1))

-- depthInfinity :: Fix something something ...

（TreeF对我来说，定义是不自然的。我更喜欢定义data Tree a = Leaf a | Tree a (Tree a) (Tree a)，但如果我这样做，我不知道如何陈述我的问题。所以我以Base仿函数的形式编写了它，ala Data .Functor.Foldable .)

该Wrap类型可用于附加信息X或Y某种数据。depth1'是一个深度 1 TreeF，其中Wrap每个级别都附加了标志（它只有一个级别）。depth2是一个深度 2 TreeF，Wrap在每个级别上都附加了标志（它有两个级别）。

如何创建任意深度的“包裹树”？我应该如何写它的类型签名？这种数据混搭有类别理论术语吗？

4

1 回答 1

6

你可以使用

Fix (Compose Wrap (TreeF Int))

但我可能不会。如果您绝对想走开放递归路线，那么制作自己的变体Fix可能是最明智的：

data WrapData = X | Y
data LabeledFix a f = Labeled a (f (LabeledFix a f))
-- ... and then use LabeledFix WrapData (TreeF Int)

但更理智的仍然是使用普通的旧封闭递归。您甚至不必使您的类型比以前更特别；只是：

data Tree a = Leaf a | Branch a (Tree a) (Tree a)
-- ... and then use Tree (WrapData, Int)
于 2019-06-05T03:52:18.627 回答