我有一个具有 Functor 实例的递归数据类型:
data Expr1 a
= Val1 a
| Add1 (Expr1 a) (Expr1 a)
deriving (Eq, Show, Functor)
现在,我有兴趣修改此数据类型以支持通用递归方案,如 this tutorial 中所述。和 this Hackage package .我设法让变态起作用:
newtype Fix f = Fix {unFix :: f (Fix f)}
data ExprF a r
= Val a
| Add r r
deriving (Eq, Show, Functor)
type Expr2 a = Fix (ExprF a)
cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix
eval :: Expr2 Int -> Int
eval = cata $ \case
Val n -> n
Add x y -> x + y
main :: IO ()
main =
print $ eval
(Fix (Add (Fix (Val 1)) (Fix (Val 2))))
但是现在我不知道如何给
Expr2
与原始 Expr
相同的仿函数实例有。尝试定义仿函数实例时似乎存在一种不匹配:instance Functor (Fix (ExprF a)) where
fmap = undefined
Kind mis-match
The first argument of `Functor' should have kind `* -> *',
but `Fix (ExprF a)' has kind `*'
In the instance declaration for `Functor (Fix (ExprF a))'
如何为
Expr2
编写 Functor 实例? 我想过用
newtype Expr2 a = Expr2 (Fix (ExprF a))
将 Expr2 包装在一个新类型中。但是这个新类型需要解包才能传递给 cata
,我不太喜欢。我也不知道是否可以自动推导出 Expr2
仿函数实例,就像我对 Expr1
所做的那样.
最佳答案
这对我来说是一个老痛处。关键是你的ExprF
它的两个参数都是函数式的。所以如果我们有
class Bifunctor b where
bimap :: (x1 -> y1) -> (x2 -> y2) -> b x1 x2 -> b y1 y2
然后你可以定义(或想象一台机器为你定义)
instance Bifunctor ExprF where
bimap k1 k2 (Val a) = Val (k1 a)
bimap k1 k2 (Add x y) = Add (k2 x) (k2 y)
现在你可以拥有
newtype Fix2 b a = MkFix2 (b a (Fix2 b a))
伴随着
map1cata2 :: Bifunctor b => (a -> a') -> (b a' t -> t) -> Fix2 b a -> t
map1cata2 e f (MkFix2 bar) = f (bimap e (map1cata2 e f) bar)
这反过来又让您知道,当您在其中一个参数中取定点时,剩下的仍然是另一个参数
instance Bifunctor b => Functor (Fix2 b) where
fmap k = map1cata2 k MkFix2
你会得到你想要的。但是你的
Bifunctor
实例不会被魔法构建。你需要一个不同的定点运算符和一种全新的仿函数,这有点烦人。问题是你现在有两种子结构:“值”和“子表达式”。轮到了。 有一个仿函数的概念,它在固定点下是封闭的。打开厨房水槽(尤其是
DataKinds
)并type s :-> t = forall x. s x -> t x
class FunctorIx (f :: (i -> *) -> (o -> *)) where
mapIx :: (s :-> t) -> f s :-> f t
请注意,“元素”的索引类型超过
i
。和“结构”在某种其他o
上的索引.我们采取i
-将元素上的功能保留到o
保留结构上的功能。至关重要的是,i
和 o
可以不同。神奇的词是“1、2、4、8,求幂的时间!”。一种类型
*
可以很容易地变成一种简单索引的 GADT () -> *
.并且可以将两种类型卷在一起制成一种 GADT Either () () -> *
.这意味着我们可以将两种子结构组合在一起。一般来说,我们有一种类型级别 either
.data Case :: (a -> *) -> (b -> *) -> Either a b -> * where
CL :: f a -> Case f g (Left a)
CR :: g b -> Case f g (Right b)
配备了“ map ”的概念
mapCase :: (f :-> f') -> (g :-> g') -> Case f g :-> Case f' g'
mapCase ff gg (CL fx) = CL (ff fx)
mapCase ff gg (CR gx) = CR (gg gx)
所以我们可以将我们的双因子重构为
Either
-索引 FunctorIx
实例。现在我们可以获取任何节点结构的固定点
f
其中有两个元素的位置 p
或子节点。这和我们上面的交易一样。newtype FixIx (f :: (Either i o -> *) -> (o -> *))
(p :: i -> *)
(b :: o)
= MkFixIx (f (Case p (FixIx f p)) b)
mapCata :: forall f p q t. FunctorIx f =>
(p :-> q) -> (f (Case q t) :-> t) -> FixIx f p :-> t
mapCata e f (MkFixIx node) = f (mapIx (mapCase e (mapCata e f)) node)
但是现在,我们得到了
FunctorIx
的事实。在 FixIx
下关闭.instance FunctorIx f => FunctorIx (FixIx f) where
mapIx f = mapCata f MkFixIx
索引集上的仿函数(具有改变索引的额外自由)可以非常精确且非常强大。与
Functor
相比,它们享有更多方便的封闭特性。是的。我不认为他们会 catch 。
关于haskell - 如何将 Functor 实例赋予为一般递归方案构建的数据类型?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27028089/