使用具有约束类型的方法的类型类实例

Question

首先让我道歉，尽管我很确定以前有人问过这个问题，但我根本找不到我的问题的答案。现在：

我想编写Functor和Monad实例为二进制（搜索）树。更准确地说，一些函数喜欢insert或merge需要 的实例Ord，例如：

data Tree a = Empty | Node a (Tree a) (Tree a)
insert :: (Ord a) => Tree a -> a -> Tree a
merge  :: (Ord a) => Tree a -> Tree a -> Tree a

因此，以下代码无法编译：

instance Monad Tree where
  {- ... -}
  Empty >>= f        = Empty
  (Node v l r) >>= f = merge (f v) (merge newL newR)
                       where newL = l >>= f
                             newR = r >>= f

-- No instance for (Ord b) arising from a use of `merge'...

由于我不知道有什么更好的，我已经尝试Ord使用 ADT声明约束，DatatypeContexts但这已被弃用并且无论如何都不起作用。其他扩展如FlexibleInstancesetc. 似乎都很有用，直到我意识到它们真的意味着别的东西。

那么，有没有办法，我将如何去做？感谢您的时间。

编辑：同时我找到了这个有用的答案，但似乎为类型类做这种事情Functor仍然是一个问题。

Answer 1

有多种方法可以做到这一点，但没有一种方法是完全干净的。

您应该查找的关键术语是“受限单子”。

这是rmonad包的一个例子（我写的）。

{-# LANGUAGE NoImplicitPrelude, TypeFamilies, GADTs,
             FlexibleInstances, MultiParamTypeClasses #-}

import Control.RMonad.Prelude
import Data.Suitable


data Tree a = Empty | Node a (Tree a) (Tree a)
insert :: (Ord a) => Tree a -> a -> Tree a
insert = undefined
merge  :: (Ord a) => Tree a -> Tree a -> Tree a
merge = undefined

data instance Constraints Tree a where
    TreeConstraints :: Ord a => Constraints Tree a

instance Ord a => Suitable Tree a where
  constraints = TreeConstraints


instance RFunctor Tree where
  fmap f Empty = Empty
  fmap f (Node v l r) = Node (f v) (fmap f l) (fmap f r)    


instance RMonad Tree where
  {- ... -}
  Empty >>= f        = Empty
  (Node v l r) >>= f = withResConstraints $ \TreeConstraints ->
        merge (f v) (merge newL newR)
           where newL = l >>= f
                 newR = r >>= f

请参阅此处的包的一般文档。

请注意，这RMonad是与Monad. 如果你想拥有一个真实的Monad实例，你可以使用AsMonad Tree.