Re: [Haskell-cafe] Set monad
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
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
[Haskell-cafe] Set monad
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
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 o...@okmij.org 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
On Sun, Jan 9, 2011 at 10:11 PM, Lennart Augustsson lenn...@augustsson.netwrote: 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
On Sun, Jan 9, 2011 at 7:45 AM, Sebastian Fischer fisc...@nii.ac.jp 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
That looks like it looses the efficiency of the underlying representation. On Sun, Jan 9, 2011 at 6:45 AM, Sebastian Fischer fisc...@nii.ac.jp wrote: On Sun, Jan 9, 2011 at 6:53 AM, Lennart Augustsson lenn...@augustsson.net 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
[Haskell-cafe] Set monad
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
Re: [Haskell-cafe] Set monad
On 9 January 2011 07:28, Peter Padawitz peter.padaw...@udo.edu 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
Re: [Haskell-cafe] Set monad
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
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 peter.padaw...@udo.eduwrote: 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
On Sat, Jan 8, 2011 at 4:53 PM, Lennart Augustsson lenn...@augustsson.net 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 d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Set monad
On Sun, Jan 9, 2011 at 6:53 AM, Lennart Augustsson lenn...@augustsson.netwrote: 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