根据 Free 编写 Identity monad

Question

Swierstra 在 "Data types a la carte" 中写道，给定 Free（他称之为 Term）和 Zero 你可以实现 Identity monad：

data Term f a = Pure a
              | Impure (f (Term f a))
data Zero a

Term Zero 现在是 Identity monad。我明白这是为什么。问题是，由于讨厌的 Functor f => 约束，我永远不能将 Term Zero 用作 Monad：

instance Functor f => Monad (Term f) where
    return x = Pure x
    (Pure x) >>= f = f x 
    (Impure f) >>= t = Impure (fmap (>>=f) t)

如何使 Zero 成为函子？

instance Functor Zero where
    fmap f z = ???

这里似乎有一个技巧：由于Zero没有构造函数，Impure永远不能使用，所以>>=的Impure情况永远不会叫。这意味着 fmap 永远不会被调用，所以从某种意义上说这是可以的：

instance Functor Zero where
    fmap f z = undefined

问题是，这感觉像是在作弊。我错过了什么？ Zero 实际上是一个 Functor 吗？或者 Zero 不是一个 Functor，这是我们在 Haskell?

中表达 Free 的一个缺点

Answer 1

如果开启DeriveFunctor，可以写

data Zero a deriving Functor

但你可能会认为这是作弊。如果你想自己写，你可以打开EmptyCase，而不是，然后写看起来很时髦的

instance Functor Zero where
    fmap f z = case z of

Answer 2

解决此问题的一种方法是使用 Data.Void 而不是空的 data 声明，如下所示：

import Data.Void

-- `Zero a` is isomorphic to `Void`
newtype Zero a = Zero Void

instance Functor Zero where
    -- You can promise anything if the precondition is that
    -- somebody's gotta give you an `x :: Void`.
    fmap f (Zero x) = absurd x

有关 Void 的用途的一些非常好的解释，请参阅 this question。但关键思想是 absurd :: Void -> a 函数让您可以从不可能发生的 x :: Void 绑定到您喜欢的任何类型。

Answer 3

定义 Zero a 的技巧如下。

newtype Zero a = Zero (Zero a)

换句话说，它编码了一种愚蠢的、稍微不明显的声明，即实际上有一种方法可以获得 Zero a 的值：你必须已经有一个！

根据这个定义，absurd :: Zero a -> b 可以用 "natural" 的方式定义

absurd :: Zero a -> b
absurd (Zero z) = absurd z

从某种意义上说，这些定义都是合法的，因为它们准确地指出了它们不可能被实例化的原因。 Zero a 的值不能构造，除非其他人先 "cheats"。

instance Functor Zero where
  fmap f = absurd

Answer 4

Luis Casillas 的另一个改进是完全从库存零件构建您的类型：

type Id = Free (Const Void)

Const x 的 Functor 实例将按照您的意愿工作（它的 fmap 不做任何事情，这很好），您只需要采取开箱注意事项：

runId (Pure x) = x
runId (Free (Const ab)) = absurd ab

当然，所有这些东西只是"morally"等同于Identity，因为它们都引入了额外的价值。特别是，我们可以区分

bottom
Pure bottom
Free bottom

根据 Free 编写 Identity monad

Writing the Identity monad in terms of Free

monads

haskell

free-monad