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

fotNelton 发表于 Dev

尼顿

首先让我道歉，尽管我很确定以前已经问过这个问题，但我只是找不到我的问题的答案。现在：

我想编写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仍然是一个问题。

GS-向Monica致歉

您可以通过多种方式来执行此操作，但是没有一种方法是完全干净的。

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

这是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