11

在“点菜数据类型”中，Swierstra 写道，给定Free（他称之为Term），Zero您可以实现 Identity monad：

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

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

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所以永远不能使用，所以永远不会调用Impurecase 。>>=这意味着fmap永远不会被调用，所以在某种意义上这是可以的：

instance Functor Zero where
    fmap f z = undefined

问题是，这感觉像是作弊。我错过了什么？Zero实际上是一个函子吗？或者可能Zero不是 Functor，这是我们Free在 Haskell 中表达方式的一个缺点？

4

4 回答 4

12

如果你打开DeriveFunctor，你可以写

data Zero a deriving Functor

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

instance Functor Zero where
    fmap f z = case z of
于 2015-09-22T04:52:58.040 回答
7

定义的技巧方法Zero a如下。

newtype Zero a = Zero (Zero a)

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

有了这个定义，absurd :: Zero a -> b可以以“自然”的方式定义

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

从某种意义上说，这些定义都是合法的，因为它们准确地指出了它们是如何无法实例化的。Zero a除非其他人先“作弊”，否则无法构造of 的值。

instance Functor Zero where
  fmap f = absurd
于 2015-09-22T13:45:02.487 回答
7

解决此问题的一种方法是使用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但关键的想法是，该absurd :: Void -> a函数可以让您从不可能发生的x :: Void绑定转变为您喜欢的任何类型。

于 2015-09-22T06:19:50.683 回答
3

Luis Casillas 的另一个答案是完全使用库存零件构建您的类型：

type Id = Free (Const Void)

for的Functor实例Const x将按照您的意愿工作（它fmap不做任何事情，这很好），您只需要在解包时小心：

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

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

bottom
Pure bottom
Free bottom
于 2015-09-22T20:40:08.710 回答