在递归数据类型的每个级别附加额外信息?
Attach extra information at every level of a recursive data type?
(这不是一个特定的 Haskell 问题。)
我有一个递归数据结构。我想在它的每个级别附加一些额外的信息。这是一个简化的示例,其中我将 X
或 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
标志(它有两个级别)。
如何创建任意深度的 "Wrapped Tree"?我应该如何写它的类型签名?这种数据混搭是否有类别理论术语?
你可以使用
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)
(这不是一个特定的 Haskell 问题。)
我有一个递归数据结构。我想在它的每个级别附加一些额外的信息。这是一个简化的示例,其中我将 X
或 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
标志(它有两个级别)。
如何创建任意深度的 "Wrapped Tree"?我应该如何写它的类型签名?这种数据混搭是否有类别理论术语?
你可以使用
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)