Экземпляры Haskell в условиях переменной типа

Question

Начиная с конкретного случая моего вопроса, мы все знаем (и любим) класс типа Monad:

class ... => Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> mb
  ...

Рассмотрим следующий потенциальный экземпляр, где мы изменяем стандартный список /экземпляр "недетерминизма", использующий nub для сохранения только одной копии каждого "результата":

type DistinctList a = DL { dL :: [a] }
instance Monad DistinctList where
  return = DL . return
  x >>= f = DL . nub $ (dL x) >>= (dL . f)

... Вы заметили ошибку?Проблема в том, что nub :: Eq a => [a] -> [a] и, следовательно, x >>= f определяется только при условии f :: Eq b => a -> DistinctList b, тогда как компилятор требует f :: a -> DistinctList b.Есть ли какой-нибудь способ, которым я могу продолжить в любом случае?

Отступая назад, предположим, у меня есть потенциальный экземпляр, который определен только при некотором условии в параметрическом типе variable .Я понимаю, что это, как правило, недопустимо, потому что другой код, написанный с классом типа, не может гарантировать значения параметров, которые соответствуют условию.Но есть ли обстоятельства, когда это еще можно осуществить?Если да, то как?

Answer 1

Вот адаптация метода, примененного в set-monad к вашему случаю.

Обратите внимание, что, как и должно быть, есть "обман".Структура включает в себя конструкторы дополнительных значений для представления «return» и «bind».Они действуют как приостановленные вычисления, которые необходимо выполнить.Экземпляр Eq является частью функции run, в то время как конструкторы, создающие «приостановку», Eq свободны.

{-# LANGUAGE GADTs #-}

import qualified Data.List            as L
import qualified Data.Functor         as F
import qualified Control.Applicative  as A
import Control.Monad

-- for reference, the bind operation to be implemented
-- bind operation requires Eq
dlbind :: Eq b => [a] -> (a -> [b]) -> [b] 
dlbind xs f = L.nub $ xs >>= f

-- data structure comes with incorporated return and bind 
-- `Prim xs` wraps a list into a DL   
data DL a where
  Prim   :: [a] -> DL a
  Return :: a -> DL a
  Bind   :: DL a -> (a -> DL b) -> DL b

-- converts a DL to a list 
run :: Eq a => DL a -> [a]
run (Prim xs)             = xs
run (Return x)            = [x]
run (Bind (Prim xs) f)    = L.nub $ concatMap (run . f) xs
run (Bind (Return x) f)   = run (f x)
run (Bind (Bind ma f) g)  = run (Bind ma (\a -> Bind (f a) g))

-- lifting of Eq and Show instance
-- Note: you probably should provide a different instance
--       one where eq doesn't depend on the position of the elements
--       otherwise you break functor laws (and everything else)
instance (Eq a) => Eq (DL a) where
  dxs == dys = run dxs == run dys

-- this "cheats", i.e. it will convert to lists in order to show. 
-- executing returns and binds in the process        
instance (Show a, Eq a) => Show (DL a) where
  show = show . run

-- uses the monad instance
instance F.Functor DL where
  fmap  = liftM 

-- uses the monad instance
instance A.Applicative DL where
  pure  = return
  (<*>) = ap

-- builds the DL using Return and Bind constructors
instance Monad DL where
  return = Return
  (>>=)  = Bind

-- examples with bind for a "normal list" and a "distinct list"
list  =  [1,2,3,4] >>= (\x ->  [x `mod` 2, x `mod` 3])   
dlist = (Prim [1,2,3,4]) >>= (\x -> Prim [x `mod` 2, x `mod` 3]) 

---

А вот грязный хак, который нужно сделатьэто более эффективно, рассматривая вопросы, поднятые ниже об оценке связывания.

{-# LANGUAGE GADTs #-}

import qualified Data.List            as L
import qualified Data.Set             as S
import qualified Data.Functor         as F
import qualified Control.Applicative  as A
import Control.Monad


dlbind xs f = L.nub $ xs >>= f

data DL a where
  Prim   :: Eq a => [a] -> DL a
  Return :: a -> DL a
  Bind   :: DL b -> (b -> DL a) -> DL a
--  Fail   :: DL a  -- could be add to clear failure chains

run :: Eq a => DL a -> [a]
run (Prim xs)      = xs
run (Return x)     = [x]
run b@(Bind _ _)   =
  case foldChain b of 
    (Bind (Prim xs) f)   -> L.nub $ concatMap (run . f) xs
    (Bind (Return a) f)  -> run (f a)
    (Bind (Bind ma f) g) -> run (Bind ma (\a -> Bind (f a) g))

-- fold a chain ((( ... >>= f) >>= g) >>= h
foldChain :: DL u -> DL u  
foldChain (Bind b2 g) = stepChain $ Bind (foldChain b2) g 
foldChain dxs         = dxs

-- simplify (Prim _ >>= f) >>= g 
--   if  (f x = Prim _)
--   then reduce to (Prim _ >>= g)
--   else preserve  (Prim _ >>= f) >>= g 
stepChain :: DL u -> DL u
stepChain b@(Bind (Bind (Prim xs) f) g) =
  let dys = map f xs
      pms = [Prim ys   | Prim   ys <- dys]
      ret = [Return ys | Return ys <- dys]
      bnd = [Bind ys f | Bind ys f <- dys]
  in case (pms, ret, bnd) of
       -- ([],[],[]) -> Fail -- could clear failure
       (dxs@(Prim ys:_),[],[]) -> let Prim xs = joinPrims dxs (Prim $ mkEmpty ys)
                                  in Bind (Prim $ L.nub xs) g       
       _  -> b
stepChain dxs = dxs

-- empty list with type via proxy  
mkEmpty :: proxy a -> [a]
mkEmpty proxy = []

-- concatenate Prims in on Prim
joinPrims [] dys = dys 
joinPrims (Prim zs : dzs) dys = let Prim xs = joinPrims dzs dys in Prim (zs ++ xs)  

instance (Ord a) => Eq (DL a) where
  dxs == dys = run dxs == run dys

instance (Ord a) => Ord (DL a) where
  compare dxs dys = compare (run dxs) (run dys)

instance (Show a, Eq a) => Show (DL a) where
  show = show . run    

instance F.Functor DL where
  fmap  = liftM 

instance A.Applicative DL where
  pure  = return
  (<*>) = ap

instance Monad DL where
  return = Return
  (>>=)  = Bind


-- cheating here, Prim is needed for efficiency 
return' x = Prim [x]

s =  [1,2,3,4] >>= (\x ->  [x `mod` 2, x `mod` 3])   
t = (Prim [1,2,3,4]) >>= (\x -> Prim [x `mod` 2, x `mod` 3]) 
r' = ((Prim [1..1000]) >>= (\x -> return' 1)) >>= (\x -> Prim [1..1000])

Answer 2

Если ваш тип может быть монадой, то он должен работать в функциях, которые параметризованы во всех монадах или во всех аппликативах.Но этого не может быть, потому что люди хранят всевозможные странные вещи в своих монадах.В частности, функции очень часто хранятся в качестве значения в аппликативном контексте.Например, рассмотрим:

pairs :: Applicative f => f a -> f b -> f (a, b)
pairs xs ys = (,) <$> xs <*> ys

Несмотря на то, что a и b оба Eq, чтобы объединить их в пару (a, b), нам нужно было сначала отобразить функцию в xs, кратко выдает значение типа f (b -> (a, b)).Если мы позволим f быть вашей монадой DL, мы увидим, что это не может работать, потому что у этого типа функции нет экземпляра Eq.

, поскольку pairs гарантированно будет работать для всех аппликативов, иэто не работает для вашего типа, мы можем быть уверены, что ваш тип не подходит.И поскольку все монады также аппликативны, мы можем заключить, что ваш тип не может быть использован в качестве монады: он будет нарушать законы.