在Haskell中定义一个monad

Question

我目前正在阅读《Kan Extensions for Program Optimisation》这本书，作者在论文的第一页中定义了给定M为一个单子的以下单子。

type C a = ∀z . (a → M z ) → M z
instance Monad C where
  return a = λc → c a
  m >>= k = λc → m (λa → k a c)

所以我尝试着用M=Maybe来玩一下，于是写了以下代码。

type C a = forall z . (a -> Maybe z) -> Maybe z

instance Monad C where
  return a = \c -> c a
  m >>= k = \c -> m $ \a -> k a c

但是它无法编译并输出

Main.hs:22:10: 错误： • 类型同义词‘C’应该有1个参数，但没有给出任何参数

我无法解释这个错误。出了什么问题？ （我学过一些范畴论，但刚开始学习Haskell）。

- Julia

---

在Haskell中，由于复杂的技术原因，类型同义词无法部分应用。请改用newtype代替。 - Fyodor Soikin

嗯，我猜你在语法方面打错了一个字。 - Fyodor Soikin

@Julia 你不能简单地将关键字 type 替换为 newtype。newtype 更类似于 data 而不是 type；你需要在右侧定义它的构造函数，而不仅仅写一个类型表达式。 - Ben

@Julia 研究论文通常以伪代码而非实际代码给出示例，这样他们就不必担心type和newtype之间的差异等问题，只需将想法写下来。这个示例是伪Haskell代码（lambda函数是一个明显的线索；UnicodeSyntax可以提供漂亮的箭头，但不包括λ）。如果你想编译类似的东西，你需要先将其翻译成实际的Haskell代码。我谦卑地建议，“我刚开始学Haskell”并不是将研究论文中的思想转化为可工作代码的合适经验水平。 - Ben

@FyodorSoikin：深层次的原因可能很复杂，但有一个相当简单的解释。部分应用的类型同义词会让我们创建类型级别的闭包。这将导致在使用高阶类型（如Functor和Monad）时出现不可靠的类型推断（以及更糟糕的错误信息）。 - Jon Purdy

Answer 1

如评论中所指出的，您需要一个newtype。 type别名只是程序员的便利，不是独立的实体，而且您想要实现一个类型类，因此您需要一个独立的实体。您可以这样编写newtype。

newtype C a = C (forall z . (a -> Maybe z) -> Maybe z)

虽然我建议包含一个访问器，因为我们马上就需要它进行编组。

newtype C a = C { unC :: forall z . (a -> Maybe z) -> Maybe z }

（如果你在家里跟着做，你需要{-# LANGUAGE RankNTypes #-}来使用这个forall语法。它是一个编译器扩展，使得那种更高级的类型成为可能）

明确一点，我们不会为forall z. (a -> Maybe z) -> Maybe z写一个Monad实例。那个类型不属于我们。我们将为C a写一个Monad实例，这是一个我们刚刚创造出来的新类型，以一种很好的方式与forall z. (a -> Maybe z) -> Maybe z同构。

现在Monad依赖于Functor和Applicative，所以我们从这里开始。 Functor是可以派生的，所以我们可以直接写deriving (Functor)，但是了解如何手动编写这些代码也是很好的实践。

instance Functor C where
    fmap f (C a) = C $ \k -> a (k . f)

现在是Applicative。在实现Applicative时，通常会使用对应的Monad实例，所以我们在这里也会这样做。

instance Applicative C where
    pure = return
    (<*>) = ap

（注意：`ap`来自`Control.Monad`模块，所以你也需要导入它）

这总是有效的，只要你编写的`Monad`实例不调用`pure`或`<*>`。

现在是`Monad`。它基本上就是你写的那样，只是加了一些`C`和`unC`的转换，以使类型检查器满意。

instance Monad C where
    return a = C (\c -> c a)
    m >>= k = C (\c -> unC m $ \a -> unC (k a) c)

最后，注意我们实际上从未使用过Maybe或其任何属性。我们不仅不关心那个M是什么，甚至不需要它成为一个Functor。因此，我们也可以通过参数化来处理它。

{-# LANGUAGE RankNTypes #-}

import Control.Monad

newtype C m a = C { unC :: forall z . (a -> m z) -> m z }

instance Functor (C m) where
    fmap f (C a) = C $ \k -> a (k . f)

instance Applicative (C m) where
    pure = return
    (<*>) = ap

instance Monad (C m) where
    return a = C (\c -> c a)
    m >>= k = C (\c -> unC m $ \a -> unC (k a) c)

现在 C Maybe 与你刚刚使用的 C 类型是相同的，但我们可以将任何类型为 * -> * 的东西放在 m 的位置上。不仅仅是 Functor，任何东西都可以。尽情发挥吧。

- Silvio Mayolo

Answer 2

你不能使用部分应用的类型别名来创建实例。在这种情况下通常会使用一个newtype，它创建了一个新的类型，但本质上只是包装的类型。

{-# LANGUAGE RankNTypes #-}
{-# Language UnicodeSyntax #-}

newtype C m a = C { getC :: ∀z . (a → m z ) → m z}

然后将实例定义为：

instance Monad m => Monad (C m) where
  return a = C (\c -> c a)
  C m >>= k = C (\c -> m (\a -> getC (k a) c))

它因此在C构造函数中进行一些包装和解包操作，但这些基本上是无操作。

- Willem Van Onsem