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

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