haskell - 如何使 Maybe 的这个替代定义起作用？

Question

我刚刚发明了以下“也许”的替代定义:

type Maybe' a = forall b. (b -> (a -> b) -> b)

just :: a -> Maybe' a
just a = \d f -> f a

nothing :: Maybe' a
nothing = const

bind :: Maybe' a -> (a -> Maybe' b) -> Maybe' b
bind ma f = ma nothing (\a -> f a)

问题是我无法添加以下实例声明

instance Monad (Maybe') where
    return = just
    a >>= f = bind a f

错误消息是:

Type synonym Maybe' should have 1 argument, but has been given none

有什么办法可以解决吗？

Answer 1

如果将其包装在 newtype 中，则只能将其设为 Monad 的实例。您还必须使用 PolymorphicComponents 扩展(RankNTypes 的较弱形式)来普遍量化 b:

{-# LANGUAGE PolymorphicComponents #-}

newtype Maybe' a = Maybe' { unMaybe' :: forall b. (b -> (a -> b) -> b) }

just :: a -> Maybe' a
just a = Maybe' (\d f -> f a)

nothing :: Maybe' a
nothing = Maybe' const

bind :: Maybe' a -> (a -> Maybe' b) -> Maybe' b
bind ma f = Maybe' (unMaybe' ma const (\a -> unMaybe' (f a)))

instance Monad Maybe' where
    return = just
    (>>=)  = bind

您需要新类型的原因是 Haskell 类型同义词不会“粘住”。当 Haskell 尝试将没有 newtype 的 Maybe' 类型签名与 Monad 类型类进行匹配时，它根本看不到 Maybe'而是看到原始的底层函数类型。

Haskell 使用“主要类型”来确保每种类型都具有规范形式。底层函数的正常形式是:

(->) b ((->) ((->) a b) b)

类型同义词不会改变类型的正常形式，但新类型会改变。具体来说，本例中的 newtype 正在重新排列类型，以便正常形式现在将 a 作为最后一个类型参数，如 Monad实例需要。