英文:
How to define bind operator using type class?
问题
如何使用类型类定义绑定运算符?
我想为一种类型定义monad实例。
以下是我编写的源代码。
data Set a = Eq a => Set [a]
newtype SetMonad a = SetMonad { unMonad :: Set a }
instance Functor SetMonad
instance Applicative SetMonad
-- Monad实例的实现
instance Monad SetMonad where
(>>=) :: SetMonad a -> (a -> SetMonad b) -> SetMonad b
(SetMonad v) >>= f = SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)
-- “Set a” 的工具函数
elems :: Set a -> [a]
elems (Set a) = a
fromList :: Eq a => [a] -> Set a
fromList [] = Set []
fromList (x : xs) = fromList' [] (x : xs)
where
fromList' [] (x : xs) = fromList' [x] xs
fromList' ys (x : xs) = if x `elem` ys then fromList' (x : ys) xs else fromList' ys xs
fromList' ys [] = Set ys
实际上,这段代码存在编译错误。
• 由于对 ‘fromList’ 的使用而产生了 ‘Eq b’ 的实例不可用
可能的修复:
在以下类型签名的上下文中添加 (Eq b):
(>>=) :: forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
• 在 ‘($)’ 使用的第二个参数中
在表达式中:SetMonad $ fromList d
在以下表达式中:
let d = concat $ elems $ unMonad $ mapM f (elems v)
in SetMonad $ fromList dtypecheck(-Wdeferred-type-errors)
绑定运算符的类型是在其他包(Control.Monad)中定义的(无法覆盖,导致编译错误)。
但是我需要在 ‘(>>=)’ 的实现中使用 ‘(==)’ 运算符。我该如何修复?
英文:
How to define bind operator using type class?
I want to define monad instance to a type.
Below is the source code I wrote.
data Set a = Eq a => Set [a]
newtype SetMonad a = SetMonad {unMonad :: Set a}
instance Functor SetMonad
instance Applicative SetMonad
-- Implemention of Monad instance for "SetMonad"
instance Monad SetMonad where
(>>=) :: SetMonad a -> (a -> SetMonad b) -> SetMonad b
(SetMonad v) >>= f = SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)
-- utils for "Set a"
elems :: Set a -> [a]
elems (Set a) = a
fromList :: Eq a => [a] -> Set a
fromList [] = Set []
fromList (x : xs) = fromList' [] (x : xs)
where
fromList' [] (x : xs) = fromList' [x] xs
fromList' ys (x : xs) = if x `elem` ys then fromList' (x : ys) xs else fromList' ys xs
fromList' ys [] = Set ys
Actually, this code has a compile error.
• No instance for (Eq b) arising from a use of ‘fromList’
Possible fix:
add (Eq b) to the context of
the type signature for:
(>>=) :: forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
• In the second argument of ‘($)’, namely ‘fromList d’
In the expression: SetMonad $ fromList d
In the expression:
let d = concat $ elems $ unMonad $ mapM f (elems v)
in SetMonad $ fromList dtypecheck(-Wdeferred-type-errors)
bind operator's type is defined in the other package (Control.Monad) and I cannot override this (compile error occurs.)
but I need to use (==) operator in the implemention of (>>=).
how should I fix it?
What I tried
- Tried to change the type defination of bind operator.
instance Monad SetMonad where
(>>=) :: Eq a => SetMonad a -> (a -> SetMonad b) -> SetMonad b
(SetMonad v) >>= f = SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)
and caused compile errors:
• No instance for (Eq a)
arising from the check that an instance signature is more general
than the type of the method (instantiated for this instance)
instance signature:
>>= :: forall a b.
Eq a =>
SetMonad a -> (a -> SetMonad b) -> SetMonad b
instantiated method type:
forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
Possible fix:
add (Eq a) to the context of
the type signature for:
(>>=) :: forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
• When checking that instance signature for ‘>>=’
is more general than its signature in the class
Instance sig: forall a b.
Eq a =>
SetMonad a -> (a -> SetMonad b) -> SetMonad b
Class sig: forall a b.
SetMonad a -> (a -> SetMonad b) -> SetMonad b
In the instance declaration for ‘Monad SetMonad’
• Could not deduce (Eq b) arising from a use of ‘fromList’
from the context: Eq a
bound by the type signature for:
(>>=) :: forall a b.
Eq a =>
SetMonad a -> (a -> SetMonad b) -> SetMonad b
at /home/txjp/dev/drive2/src/Sandbox2.hs:127:12-64
Possible fix:
add (Eq b) to the context of
the type signature for:
(>>=) :: forall a b.
Eq a =>
SetMonad a -> (a -> SetMonad b) -> SetMonad b
• In the first argument of ‘($)’, namely ‘fromList’
In the second argument of ‘($)’, namely
‘fromList $ concat $ elems $ unMonad $ mapM f (elems v)’
In the expression:
SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)
Background
List monad is usiful for nondeterministic computation.
but sometimes unfavorable because it has the idea of order when I interested only in combinations.
So, I wanted to implement list-like monad which have no concept of order.
Normally, I should use Data.Set package, but it need to be Ord instance to use.
so, I used a list-based implemention to make things easier.
Please give me some help.
Thank you.
答案1
得分: 3
这是一个已知的难题。有一些方法可以让这个工作,但我认为问题的根本是,在 Hask 类别中,集合作为单子实际上是没有意义的。
它们在具有 Eq
实例的类型子类中是有意义的。这就是我为什么编写了 constrained-category
包 的原因。<sub>(还有许多其他替代品:data-category
,constrained-monads
,constrained
,subhask
...)</sub>。思路是限制所有映射,以便您始终保持在允许的类型类中。然后,您实际上不需要在类型中包含 Eq
约束,这只会让事情变得更加复杂。
import qualified Prelude as Hask
import Control.Category.Constrained
import Control.Category.Constrained.Prelude
import Data.List (nub)
newtype Set a = Set { setElems :: [a] }
instance Eq a => Eq (Set a) where
(==) = ... -- 注意顺序可能无关紧要
fromList :: Eq a => [a] -> Set a
fromList = Set . nub
instance Functor Set (Eq ⊢ (->)) (Eq ⊢ (->)) where
fmap (ConstrainedMorphism f) = ConstrainedMorphism
$ \(Set s) -> fromList $ map f s
instance Monoidal Set (Eq⊢(->)) (Eq⊢(->)) where
pureUnit = ConstrainedMorphism pure
fzipWith (ConstrainedMorphism f)
= ConstrainedMorphism $ \(Set xs, Set ys)
-> Set . fromList $ fzipWith f (xs,ys)
instance Applicative Set (Eq ⊢ (->)) (Eq ⊢ (->)) where
pure = ConstrainedMorphism pure
instance Monad Set (Eq ⊢ (->)) where
join (Set s) = fromList $ s >>= setElems
希望这对你有所帮助。
英文:
This is a known conumdrum. There are hacks to get this working, but IMO the issue is ultimately that sets just don't make sense as monads in the Hask category.
They do make sense as monads in the subcategory of types with an Eq
instance. This is the kind of thing that I wrote the constrained-category
package for. <sub>(There are many alternatives: data-category
, constrained-monads
, constrained
, subhask
...)</sub>. The idea is to restrict all mapping so you always stay within the class of allowed types. You don't really need to include the Eq
constraint in the type then, this mostly just complicates things.
import qualified Prelude as Hask
import Control.Category.Constrained
import Control.Category.Constrained.Prelude
import Data.List (nub)
newtype Set a = Set { setElems :: [a] }
instance Eq a => Eq (Set a) where
(==) = ... -- beware that order should not matter
fromList :: Eq a => [a] -> Set a
fromList = Set . nub
instance Functor Set (Eq ⊢ (->)) (Eq ⊢ (->)) where
fmap (ConstrainedMorphism f) = ConstrainedMorphism
$ \(Set s) -> fromList $ map f s
instance Monoidal Set (Eq⊢(->)) (Eq⊢(->)) where
pureUnit = ConstrainedMorphism pure
fzipWith (ConstrainedMorphism f)
= ConstrainedMorphism $ \(Set xs, Set ys)
-> Set . fromList $ fzipWith f (xs,ys)
instance Applicative Set (Eq ⊢ (->)) (Eq ⊢ (->)) where
pure = ConstrainedMorphism pure
instance Monad Set (Eq ⊢ (->)) where
join (Set s) = fromList $ s >>= setElems
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论