从某种意义上说,它们彼此非常相似,因为它们是双重的。构造函数可以被认为是一个数据类型的签名函子的代数和相同函子上的模式余代数。
更明确地说,让我们考虑[]
. 它的签名函子是T_A X = 1 + A * X
或,在 Haskell
type ListF a x = Maybe (a, x)
以明显的Functor
例子。我们可以看到ListF
带有List
载体的-代数只是它的构造函数
-- general definition
type Algebra f a = f a -> a
consList :: Algebra (ListF a) [a]
consList Nothing = []
consList (Just (a, as)) = a:as
对偶,我们可以看ListF
with的余代数List
作为它的载体
type Coalgebra f a = a -> f a
unconsList :: Coalgebra (ListF a) [a]
unconsList [] = Nothing
unconsList (a:as) = Just (a, as)
并进一步看到 and 的安全版本head
是tail
非常自然的析构函数[]
headMay :: [a] -> Maybe a
headMay = fmap fst . unconsList
tailMay :: [a] -> Maybe a
tailMay = fmap snd . unconsList
这激起了个人的不满head
,tail
甚至不是特别好的函数,忽略了它们的偏爱——它们只有在具有签名函子的无限列表上才是自然的T A X = A*X
。
现在在 Haskell 中,一个函子的初始Algebra
和最终Coalgebra
重合为该函子的不动点
newtype Fix f = Fix { unfix :: f (Fix f) }
这正是数据类型。我们可以证明它[a]
同构于Fix (ListF a)
fwd :: [a] -> Fix (ListF a)
fwd [] = Fix Nothing
fwd (a:as) = Fix (Just (a, fwd as))
bwd :: Fix (ListF a) -> [a]
bwd (Fix Nothing) = []
bwd (Fix (Just (a, fixed))) = a : bwd fixed
这为使用数据类型本身作为构造函数和模式提供了理由,但是如果您创建其他类型的“类似代数”的东西,那么您可以拥有一流的模式,例如She或模式组合器提供的模式。
为了更深入地理解模式和构造函数的对偶性,请尝试使用类似的数据类型再次执行上述练习
data Tree a = Leaf | Branch (Tree a) a (Tree a)
它的签名函子是T A X = 1 + X*A*X
或
type TreeF a x = Maybe (x,a,x)