Re: [Haskell-cafe] Set monad

[Petr Pudlák]

On 04/12/2013 12:49 PM, o...@okmij.org wrote:

One problem with such monad implementations is efficiency. Let's define

 step :: (MonadPlus m) =>  Int ->  m Int
 step i = choose [i, i + 1]

 -- repeated application of step on 0:
 stepN :: (Monad m) =>  Int ->  m (S.Set Int)
 stepN = runSet . f
   where
 f 0 = return 0
 f n = f (n-1)>>= step

Then `stepN`'s time complexity is exponential in its argument. This is
because `ContT` reorders the chain of computations to right-associative,
which is correct, but changes the time complexity in this unfortunate way.
If we used Set directly, constructing a left-associative chain, it produces
the result immediately:

The example is excellent. And yet, the efficient genuine Set monad is
possible.

BTW, a simpler example to see the problem with the original CPS monad is to
repeat
 choose [1,1]>>  choose [1,1]>>choose [1,1]>>  return 1

and observe exponential behavior. But your example is much more
subtle.

Enclosed is the efficient genuine Set monad. I wrote it in direct
style (it seems to be faster, anyway). The key is to use the optimized
choose function when we can.

{-# LANGUAGE GADTs, TypeSynonymInstances, FlexibleInstances #-}

module SetMonadOpt where

import qualified Data.Set as S
import Control.Monad

data SetMonad a where
 SMOrd :: Ord a =>  S.Set a ->  SetMonad a
 SMAny :: [a] ->  SetMonad a

instance Monad SetMonad where
 return x = SMAny [x]

 m>>= f = collect . map f $ toList m

toList :: SetMonad a ->  [a]
toList (SMOrd x) = S.toList x
toList (SMAny x) = x

collect :: [SetMonad a] ->  SetMonad a
collect []  = SMAny []
collect [x] = x
collect ((SMOrd x):t) = case collect t of
  SMOrd y ->  SMOrd (S.union x y)
  SMAny y ->  SMOrd (S.union x (S.fromList y))
collect ((SMAny x):t) = case collect t of
  SMOrd y ->  SMOrd (S.union y (S.fromList x))
  SMAny y ->  SMAny (x ++ y)

runSet :: Ord a =>  SetMonad a ->  S.Set a
runSet (SMOrd x) = x
runSet (SMAny x) = S.fromList x

instance MonadPlus SetMonad where
 mzero = SMAny []
 mplus (SMAny x) (SMAny y) = SMAny (x ++ y)
 mplus (SMAny x) (SMOrd y) = SMOrd (S.union y (S.fromList x))
 mplus (SMOrd x) (SMAny y) = SMOrd (S.union x (S.fromList y))
 mplus (SMOrd x) (SMOrd y) = SMOrd (S.union x y)

choose :: MonadPlus m =>  [a] ->  m a
choose = msum . map return


test1 = runSet (do
   n1<- choose [1..5]
   n2<- choose [1..5]
   let n = n1 + n2
   guard $ n<  7
   return n)
-- fromList [2,3,4,5,6]

-- Values to choose from might be higher-order or actions
test1' = runSet (do
   n1<- choose . map return $ [1..5]
   n2<- choose . map return $ [1..5]
   n<- liftM2 (+) n1 n2
   guard $ n<  7
   return n)
-- fromList [2,3,4,5,6]

test2 = runSet (do
   i<- choose [1..10]
   j<- choose [1..10]
   k<- choose [1..10]
   guard $ i*i + j*j == k * k
   return (i,j,k))
-- fromList [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

test3 = runSet (do
   i<- choose [1..10]
   j<- choose [1..10]
   k<- choose [1..10]
   guard $ i*i + j*j == k * k
   return k)
-- fromList [5,10]

-- Test by Petr Pudlak

-- First, general, unoptimal case
step :: (MonadPlus m) =>  Int ->  m Int
step i = choose [i, i + 1]

-- repeated application of step on 0:
stepN :: Int ->  S.Set Int
stepN = runSet . f
   where
   f 0 = return 0
   f n = f (n-1)>>= step

-- it works, but clearly exponential
{-
*SetMonad>  stepN 14
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
(0.09 secs, 31465384 bytes)
*SetMonad>  stepN 15
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
(0.18 secs, 62421208 bytes)
*SetMonad>  stepN 16
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
(0.35 secs, 124876704 bytes)
-}

-- And now the optimization
chooseOrd :: Ord a =>  [a] ->  SetMonad a
chooseOrd x = SMOrd (S.fromList x)

stepOpt :: Int ->  SetMonad Int
stepOpt i = chooseOrd [i, i + 1]

-- repeated application of step on 0:
stepNOpt :: Int ->  S.Set Int
stepNOpt = runSet . f
   where
   f 0 = return 0
   f n = f (n-1)>>= stepOpt

{-
stepNOpt 14
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
(0.00 secs, 515792 bytes)
stepNOpt 15
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
(0.00 secs, 515680 bytes)
stepNOpt 16
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
(0.00 secs, 515656 bytes)

stepNOpt 30
fromList 
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
(0.00 secs, 1068856 bytes)
-}


Oleg, thanks a lot for this example, and sorry for my late reply. I 
really like the idea and I'm hoping to a similar concept soon for a 
monad representing probability computations.


  With best regards,
  Petr

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[oleg]

> One problem with such monad implementations is efficiency. Let's define
>
> step :: (MonadPlus m) => Int -> m Int
> step i = choose [i, i + 1]
>
> -- repeated application of step on 0:
> stepN :: (Monad m) => Int -> m (S.Set Int)
> stepN = runSet . f
>   where
> f 0 = return 0
> f n = f (n-1) >>= step
>
> Then `stepN`'s time complexity is exponential in its argument. This is
> because `ContT` reorders the chain of computations to right-associative,
> which is correct, but changes the time complexity in this unfortunate way.
> If we used Set directly, constructing a left-associative chain, it produces
> the result immediately:

The example is excellent. And yet, the efficient genuine Set monad is
possible.

BTW, a simpler example to see the problem with the original CPS monad is to
repeat
choose [1,1] >> choose [1,1] >>choose [1,1] >> return 1

and observe exponential behavior. But your example is much more
subtle.

Enclosed is the efficient genuine Set monad. I wrote it in direct
style (it seems to be faster, anyway). The key is to use the optimized
choose function when we can.

{-# LANGUAGE GADTs, TypeSynonymInstances, FlexibleInstances #-}

module SetMonadOpt where

import qualified Data.Set as S
import Control.Monad

data SetMonad a where
SMOrd :: Ord a => S.Set a -> SetMonad a
SMAny :: [a] -> SetMonad a

instance Monad SetMonad where
return x = SMAny [x]

m >>= f = collect . map f $ toList m

toList :: SetMonad a -> [a]
toList (SMOrd x) = S.toList x
toList (SMAny x) = x

collect :: [SetMonad a] -> SetMonad a
collect []  = SMAny []
collect [x] = x
collect ((SMOrd x):t) = case collect t of
 SMOrd y -> SMOrd (S.union x y)
 SMAny y -> SMOrd (S.union x (S.fromList y))
collect ((SMAny x):t) = case collect t of
 SMOrd y -> SMOrd (S.union y (S.fromList x))
 SMAny y -> SMAny (x ++ y)

runSet :: Ord a => SetMonad a -> S.Set a
runSet (SMOrd x) = x
runSet (SMAny x) = S.fromList x

instance MonadPlus SetMonad where
mzero = SMAny []
mplus (SMAny x) (SMAny y) = SMAny (x ++ y)
mplus (SMAny x) (SMOrd y) = SMOrd (S.union y (S.fromList x))
mplus (SMOrd x) (SMAny y) = SMOrd (S.union x (S.fromList y))
mplus (SMOrd x) (SMOrd y) = SMOrd (S.union x y)

choose :: MonadPlus m => [a] -> m a
choose = msum . map return


test1 = runSet (do
  n1 <- choose [1..5]
  n2 <- choose [1..5]
  let n = n1 + n2
  guard $ n < 7
  return n)
-- fromList [2,3,4,5,6]

-- Values to choose from might be higher-order or actions
test1' = runSet (do
  n1 <- choose . map return $ [1..5]
  n2 <- choose . map return $ [1..5]
  n  <- liftM2 (+) n1 n2
  guard $ n < 7
  return n)
-- fromList [2,3,4,5,6]

test2 = runSet (do
  i <- choose [1..10]
  j <- choose [1..10]
  k <- choose [1..10]
  guard $ i*i + j*j == k * k
  return (i,j,k))
-- fromList [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

test3 = runSet (do
  i <- choose [1..10]
  j <- choose [1..10]
  k <- choose [1..10]
  guard $ i*i + j*j == k * k
  return k)
-- fromList [5,10]

-- Test by Petr Pudlak

-- First, general, unoptimal case
step :: (MonadPlus m) => Int -> m Int
step i = choose [i, i + 1]

-- repeated application of step on 0:
stepN :: Int -> S.Set Int
stepN = runSet . f
  where
  f 0 = return 0
  f n = f (n-1) >>= step

-- it works, but clearly exponential
{-
*SetMonad> stepN 14
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
(0.09 secs, 31465384 bytes)
*SetMonad> stepN 15
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
(0.18 secs, 62421208 bytes)
*SetMonad> stepN 16
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
(0.35 secs, 124876704 bytes)
-}

-- And now the optimization
chooseOrd :: Ord a => [a] -> SetMonad a
chooseOrd x = SMOrd (S.fromList x)

stepOpt :: Int -> SetMonad Int
stepOpt i = chooseOrd [i, i + 1]

-- repeated application of step on 0:
stepNOpt :: Int -> S.Set Int
stepNOpt = runSet . f
  where
  f 0 = return 0
  f n = f (n-1) >>= stepOpt

{-
stepNOpt 14
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
(0.00 secs, 515792 bytes)
stepNOpt 15
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
(0.00 secs, 515680 bytes)
stepNOpt 16
fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
(0.00 secs, 515656 bytes)

stepNOpt 30
fromList 
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
(0.00 secs, 1068856 bytes)
-}



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Petr Pudlák]

One problem with such monad implementations is efficiency. Let's define

step :: (MonadPlus m) => Int -> m Int
step i = choose [i, i + 1]

-- repeated application of step on 0:
stepN :: (Monad m) => Int -> m (S.Set Int)
stepN = runSet . f
  where
f 0 = return 0
f n = f (n-1) >>= step

Then `stepN`'s time complexity is exponential in its argument. This is
because `ContT` reorders the chain of computations to right-associative,
which is correct, but changes the time complexity in this unfortunate way.
If we used Set directly, constructing a left-associative chain, it produces
the result immediately:

step' :: Int -> S.Set Int
step' i = S.fromList [i, i + 1]

stepN' :: Int -> S.Set Int
stepN' 0 = S.singleton 0
stepN' n = stepN' (n - 1) `setBind` step'
  where
setBind k f = S.foldl' (\s -> S.union s . f) S.empty k


See also: Constructing efficient monad instances on `Set` (and other
containers with constraints) using the continuation monad <
http://stackoverflow.com/q/12183656/1333025>

Best regards,
Petr Pudlak



2013/4/11 

>
> The question of Set monad comes up quite regularly, most recently at
> http://www.ittc.ku.edu/csdlblog/?p=134
>
> Indeed, we cannot make Data.Set.Set to be the instance of Monad type
> class -- not immediately, that it. That does not mean that there is no
> Set Monad, a non-determinism monad that returns the set of answers,
> rather than a list. I mean genuine *monad*, rather than a restricted,
> generalized, etc. monad.
>
> It is surprising that the question of the Set monad still comes up
> given how simple it is to implement it. Footnote 4 in the ICFP
> 2009 paper on ``Purely Functional Lazy Non-deterministic Programming''
> described the idea, which is probably folklore. Just in case, here is
> the elaboration, a Set monad transformer.
>
> {-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}
>
> module SetMonad where
>
> import qualified Data.Set as S
> import Control.Monad.Cont
>
> -- Since ContT is a bona fide monad transformer, so is SetMonadT r.
> type SetMonadT r = ContT (S.Set r)
>
> -- These are the only two places the Ord constraint shows up
>
> instance (Ord r, Monad m) => MonadPlus (SetMonadT r m) where
> mzero = ContT $ \k -> return S.empty
> mplus m1 m2 = ContT $ \k -> liftM2 S.union (runContT m1 k) (runContT
> m2 k)
>
> runSet :: (Monad m, Ord r) => SetMonadT r m r -> m (S.Set r)
> runSet m = runContT m (return . S.singleton)
>
> choose :: MonadPlus m => [a] -> m a
> choose = msum . map return
>
> test1 = print =<< runSet (do
>   n1 <- choose [1..5]
>   n2 <- choose [1..5]
>   let n = n1 + n2
>   guard $ n < 7
>   return n)
> -- fromList [2,3,4,5,6]
>
> -- Values to choose from might be higher-order or actions
> test1' = print =<< runSet (do
>   n1 <- choose . map return $ [1..5]
>   n2 <- choose . map return $ [1..5]
>   n  <- liftM2 (+) n1 n2
>   guard $ n < 7
>   return n)
> -- fromList [2,3,4,5,6]
>
> test2 = print =<< runSet (do
>   i <- choose [1..10]
>   j <- choose [1..10]
>   k <- choose [1..10]
>   guard $ i*i + j*j == k * k
>   return (i,j,k))
> -- fromList [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
>
> test3 = print =<< runSet (do
>   i <- choose [1..10]
>   j <- choose [1..10]
>   k <- choose [1..10]
>   guard $ i*i + j*j == k * k
>   return k)
> -- fromList [5,10]
>
>
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Set monad

[oleg]

The question of Set monad comes up quite regularly, most recently at
http://www.ittc.ku.edu/csdlblog/?p=134

Indeed, we cannot make Data.Set.Set to be the instance of Monad type
class -- not immediately, that it. That does not mean that there is no
Set Monad, a non-determinism monad that returns the set of answers,
rather than a list. I mean genuine *monad*, rather than a restricted,
generalized, etc. monad. 

It is surprising that the question of the Set monad still comes up
given how simple it is to implement it. Footnote 4 in the ICFP
2009 paper on ``Purely Functional Lazy Non-deterministic Programming'' 
described the idea, which is probably folklore. Just in case, here is
the elaboration, a Set monad transformer.

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

module SetMonad where

import qualified Data.Set as S
import Control.Monad.Cont

-- Since ContT is a bona fide monad transformer, so is SetMonadT r.
type SetMonadT r = ContT (S.Set r)

-- These are the only two places the Ord constraint shows up

instance (Ord r, Monad m) => MonadPlus (SetMonadT r m) where
mzero = ContT $ \k -> return S.empty
mplus m1 m2 = ContT $ \k -> liftM2 S.union (runContT m1 k) (runContT m2 k)

runSet :: (Monad m, Ord r) => SetMonadT r m r -> m (S.Set r)
runSet m = runContT m (return . S.singleton)

choose :: MonadPlus m => [a] -> m a
choose = msum . map return

test1 = print =<< runSet (do
  n1 <- choose [1..5]
  n2 <- choose [1..5]
  let n = n1 + n2
  guard $ n < 7
  return n)
-- fromList [2,3,4,5,6]

-- Values to choose from might be higher-order or actions
test1' = print =<< runSet (do
  n1 <- choose . map return $ [1..5]
  n2 <- choose . map return $ [1..5]
  n  <- liftM2 (+) n1 n2
  guard $ n < 7
  return n)
-- fromList [2,3,4,5,6]

test2 = print =<< runSet (do
  i <- choose [1..10]
  j <- choose [1..10]
  k <- choose [1..10]
  guard $ i*i + j*j == k * k
  return (i,j,k))
-- fromList [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

test3 = print =<< runSet (do
  i <- choose [1..10]
  j <- choose [1..10]
  k <- choose [1..10]
  guard $ i*i + j*j == k * k
  return k)
-- fromList [5,10]



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Sebastian Fischer]

On Sun, Jan 9, 2011 at 10:11 PM, Lennart Augustsson
wrote:

> That looks like it looses the efficiency of the underlying representation.
>

Yes, I don't think one can retain that cleanly without using restricted
monads to exclude things like

liftM ($42) (mplus (return pred) (return succ))

or just

liftM ($42) (return pred)

Maybe one can hack something to achieve

mplus :: Ord a => Set a -> Set a -> Set a
mplus a b = Set (\k -> S.union (a >>- ret) (b >>- ret) `bind` k)
  where
ret = S.singleton
bind = flip Data.Foldable.foldMap

mplus :: not (Ord a) => Set a -> Set a -> Set a
mplus a b = Set (\k -> S.union (a >>- k) (b >>- k))

using overloading with undecidable instances (?) (and defining a Monoid
instance for the Set monad in terms of the MonadPlus instance)

Reminds me of instance chains.. [1]

Sebastian

[1]: http://portal.acm.org/citation.cfm?id=1863596
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Lennart Augustsson]

That looks like it looses the efficiency of the underlying representation.

On Sun, Jan 9, 2011 at 6:45 AM, Sebastian Fischer  wrote:

> On Sun, Jan 9, 2011 at 6:53 AM, Lennart Augustsson  > wrote:
>
>> It so happens that you can make a set data type that is a Monad, but it's
>> not exactly the best possible sets.
>>
>> module SetMonad where
>>
>> newtype Set a = Set { unSet :: [a] }
>>
>
> Here is a version that also does not require restricted monads but works
> with an arbitrary underlying Set data type (e.g. from Data.Set). It uses
> continuations with a Rank2Type.
>
> import qualified Data.Set as S
>
> newtype Set a = Set { (>>-) :: forall b . Ord b => (a -> S.Set b) ->
> S.Set b }
>
> instance Monad Set where
>   return x = Set ($x)
>   a >>= f  = Set (\k -> a >>- \x -> f x >>- k)
>
> Only conversion to the underlying Set type requires an Ord constraint.
>
> getSet :: Ord a => Set a -> S.Set a
> getSet a = a >>- S.singleton
>
> A `MonadPlus` instance can lift `empty` and `union`.
>
> instance MonadPlus Set where
>   mzero = Set (const S.empty)
>   mplus a b = Set (\k -> S.union (a >>- k) (b >>- k))
>
> Maybe, Heinrich Apfelmus's operational package [1] can be used to do the
> same without continuations.
>
> [1]: http://projects.haskell.org/operational/
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Andrea Vezzosi]

On Sun, Jan 9, 2011 at 7:45 AM, Sebastian Fischer  wrote:
> [...]
> Only conversion to the underlying Set type requires an Ord constraint.
>     getSet :: Ord a => Set a -> S.Set a
>     getSet a = a >>- S.singleton

this unfortunately also means that duplicated elements only get
filtered out at the points where you use getSet,
so in "getSet ((return 1 `mplus` return 1) >>= k)" k gets still called twice

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Sebastian Fischer]

On Sun, Jan 9, 2011 at 6:53 AM, Lennart Augustsson
wrote:

> It so happens that you can make a set data type that is a Monad, but it's
> not exactly the best possible sets.
>
> module SetMonad where
>
> newtype Set a = Set { unSet :: [a] }
>

Here is a version that also does not require restricted monads but works
with an arbitrary underlying Set data type (e.g. from Data.Set). It uses
continuations with a Rank2Type.

import qualified Data.Set as S

newtype Set a = Set { (>>-) :: forall b . Ord b => (a -> S.Set b) ->
S.Set b }

instance Monad Set where
  return x = Set ($x)
  a >>= f  = Set (\k -> a >>- \x -> f x >>- k)

Only conversion to the underlying Set type requires an Ord constraint.

getSet :: Ord a => Set a -> S.Set a
getSet a = a >>- S.singleton

A `MonadPlus` instance can lift `empty` and `union`.

instance MonadPlus Set where
  mzero = Set (const S.empty)
  mplus a b = Set (\k -> S.union (a >>- k) (b >>- k))

Maybe, Heinrich Apfelmus's operational package [1] can be used to do the
same without continuations.

[1]: http://projects.haskell.org/operational/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[David Menendez]

On Sat, Jan 8, 2011 at 4:53 PM, Lennart Augustsson
 wrote:
> It so happens that you can make a set data type that is a Monad, but it's
> not exactly the best possible sets.

There's also the infinite search monad, which allows you to search
infinite sets in finite time, provided your queries meet some
termination criteria.

http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/
http://hackage.haskell.org/package/infinite-search


-- 
Dave Menendez 


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Lennart Augustsson]

It so happens that you can make a set data type that is a Monad, but it's
not exactly the best possible sets.

module SetMonad where

newtype Set a = Set { unSet :: [a] }

singleton :: a -> Set a
singleton x = Set [x]

unions :: [Set a] -> Set a
unions ss = Set $ concatMap unSet ss

member :: (Eq a) => a -> Set a -> Bool
member x s = x `elem` unSet s

instance Monad Set where
return = singleton
x >>= f = unions (map f (unSet x))


On Sat, Jan 8, 2011 at 9:28 PM, Peter Padawitz wrote:

> Hi,
>
> is there any way to instantiate m in Monad m with a set datatype in order
> to implement the usual powerset monad?
>
> My straightforward attempt failed because the bind operator of this
> instance requires the Eq constraint on the argument types of m.
>
> Peter
>
>
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Edward Z. Yang]

Hello Peter,

This is a classic problem with the normal monad type class.  You can
achieve this with "restricted monads", but there is a bit of tomfoolery
you have to do to get do-notation support for them.

Here is some relevant reading:

- http://okmij.org/ftp/Haskell/types.html#restricted-datatypes
- http://hackage.haskell.org/package/rmonad-0.4.1

Cheers,
Edward

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Set monad

[Ivan Lazar Miljenovic]

On 9 January 2011 07:28, Peter Padawitz  wrote:
> Hi,
>
> is there any way to instantiate m in Monad m with a set datatype in order to
> implement the usual powerset monad?
>
> My straightforward attempt failed because the bind operator of this instance
> requires the Eq constraint on the argument types of m.

See Ganesh Sittampalam's rmonad [1] package.

[1]: http://hackage.haskell.org/package/rmonad

-- 
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Set monad

[Peter Padawitz]

Hi,

is there any way to instantiate m in Monad m with a set datatype in  
order to implement the usual powerset monad?


My straightforward attempt failed because the bind operator of this  
instance requires the Eq constraint on the argument types of m.


Peter



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe