如何使用类型类定义绑定操作符?

huangapple go评论87阅读模式
英文:

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-categoryconstrained-monadsconstrainedsubhask...)</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  (-&gt;)) (Eq  (-&gt;)) where
  fmap (ConstrainedMorphism f) = ConstrainedMorphism
           $ \(Set s) -&gt; fromList $ map f s

instance Monoidal Set (Eq(-&gt;)) (Eq(-&gt;)) where
  pureUnit = ConstrainedMorphism pure
  fzipWith (ConstrainedMorphism f)
    = ConstrainedMorphism $ \(Set xs, Set ys)
        -&gt; Set . fromList $ fzipWith f (xs,ys)
instance Applicative Set (Eq  (-&gt;)) (Eq  (-&gt;)) where
  pure = ConstrainedMorphism pure

instance Monad Set (Eq  (-&gt;)) where
  join (Set s) = fromList $ s &gt;&gt;= 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 =&gt; Eq (Set a) where
  (==) = ... -- beware that order should not matter

fromList :: Eq a =&gt; [a] -&gt; Set a
fromList = Set . nub

instance Functor Set (Eq ⊢ (-&gt;)) (Eq ⊢ (-&gt;)) where
  fmap (ConstrainedMorphism f) = ConstrainedMorphism
           $ \(Set s) -&gt; fromList $ map f s

instance Monoidal Set (Eq⊢(-&gt;)) (Eq⊢(-&gt;)) where
  pureUnit = ConstrainedMorphism pure
  fzipWith (ConstrainedMorphism f)
    = ConstrainedMorphism $ \(Set xs, Set ys)
        -&gt; Set . fromList $ fzipWith f (xs,ys)
instance Applicative Set (Eq ⊢ (-&gt;)) (Eq ⊢ (-&gt;)) where
  pure = ConstrainedMorphism pure

instance Monad Set (Eq ⊢ (-&gt;)) where
  join (Set s) = fromList $ s &gt;&gt;= setElems

huangapple
  • 本文由 发表于 2023年5月11日 18:43:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/76226756.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定