haskell - 了解 Haskell 中的 Fix 数据类型

Question

在 this article关于 Haskell 中的 Free Monad，我们得到了一个由以下定义的 Toy 数据类型:

data Toy b next =
    Output b next
  | Bell next
  | Done

修复定义如下:

data Fix f = Fix (f (Fix f))

它允许通过保留通用类型来嵌套 Toy 表达式:

Fix (Output 'A' (Fix Done))              :: Fix (Toy Char)
Fix (Bell (Fix (Output 'A' (Fix Done)))) :: Fix (Toy Char)

我了解固定点如何用于常规功能，但我看不到这里的类型是如何减少的。编译器遵循哪些步骤来评估表达式的类型？

Answer 1

我将使用 Fix 制作一个更熟悉、更简单的类型看看你会不会明白。

这是正常递归定义中的列表类型:

data List a = Nil | Cons a (List a)

现在，回想一下我们如何使用 fix对于函数，我们知道我们必须将函数作为参数传递给自身。事实上，自从 List是递归的，我们可以编写一个更简单的非递归数据类型，如下所示:

data Cons a recur = Nil | Cons a recur

你能看出这与函数 f a recur = 1 + recur a 有何相似之处吗？ ?同 fix会通过 f作为自变量， Fix通过 Cons作为自己的论据。让我们检查 fix 的定义和 Fix并排:

fix :: (p -> p) -> p
fix f = f (fix f)

-- Fix :: (* -> *) -> *
newtype Fix f = Fix {nextFix :: f (Fix f)}

如果您忽略构造函数名称的绒毛等，您会发现它们本质上是完全相同的定义!

对于 Toy 的示例数据类型，可以像这样递归地定义它:

data Toy a = Output a (Toy a) | Bell (Toy a) | Done

但是，我们可以使用 Fix将自身传递给自身，替换 Toy a 的所有实例带有第二个类型参数:

data ToyStep a recur = OutputS a recur | BellS recur | DoneS

所以，我们可以使用 Fix (ToyStep a) , 相当于 Toy a ，尽管形式不同。事实上，让我们证明它们是等价的:

toyToStep :: Toy a -> Fix (ToyStep a)
toyToStep (Output a next) = Fix (OutputS a (toyToStep next))
toyToStep (Bell next) = Fix (BellS (toyToStep next))
toyToStep Done = Fix DoneS

stepToToy :: Fix (ToyStep a) -> Toy a
stepToToy (Fix (OutputS a next)) = Output a (stepToToy next)
stepToToy (Fix (BellS next)) = Bell (stepToToy next)
stepToToy (Fix (DoneS)) = DoneS

您可能想知道，“为什么要这样做？”通常，没有太多理由这样做。但是，定义这些类型的简化版本的数据类型实际上可以让您制作出极具表现力的函数。这是一个例子:

unwrap :: Functor f => (f k -> k) -> Fix f -> k
unwrap f n = f (fmap (unwrap f) n)

这真是一个不可思议的功能!当我第一次看到它时，我很惊讶!这是一个使用 Cons 的示例我们之前创建的数据类型，假设我们创建了 Functor实例:

getLength :: Cons a Int -> Int
getLength Nil = 0
getLength (Cons _ len) = len + 1

length :: Fix (Cons a) -> Int
length = unwrap getLength

这本质上是 fix免费，因为我们使用 Fix在我们使用的任何数据类型上!

现在让我们想象一个函数，假设 ToyStep a是一个仿函数实例，它简单地收集所有 OutputS s 到一个列表中，如下所示:

getOutputs :: ToyStep a [a] -> [a]
getOutputs (OutputS a as) = a : as
getOutputs (BellS as) = as
getOutputs DoneS = []

outputs :: Fix (ToyStep a) -> [a]
outputs = unwrap getOutputs

这就是使用 Fix 的力量而不是拥有自己的数据类型:一般性。