Set monad - Haskell-Cafe - Haskell.org

newer
HXT is slow?

Set monad

older
Re: [Haskell-cafe] Type System vs...

Peter Padawitz

8 Jan 2011 8 Jan '11

4:28 p.m.

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

Reply

Sign in to reply online Use email software

Show replies by date

Ivan Lazar Miljenovic

8 Jan 8 Jan

4:36 p.m.

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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

Reply

Sign in to reply online Use email software

Edward Z. Yang

4:40 p.m.

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

Reply

Sign in to reply online Use email software

Lennart Augustsson

4:53 p.m.

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

Reply

Sign in to reply online Use email software

David Menendez

5:29 p.m.

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-fin... http://hackage.haskell.org/package/infinite-search -- Dave Menendez http://www.eyrie.org/~zednenem/

Reply

Sign in to reply online Use email software

Sebastian Fischer

9 Jan 9 Jan

1:45 a.m.

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/

Reply

Sign in to reply online Use email software

Andrea Vezzosi

7:36 a.m.

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

Reply

Sign in to reply online Use email software

Lennart Augustsson

8:11 a.m.

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

Reply

Sign in to reply online Use email software

Sebastian Fischer

12 Jan 12 Jan

9:11 a.m.

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

Reply

Sign in to reply online Use email software

5244

Age (days ago)

5248

Last active (days ago)

Download

8 comments

7 participants

tags

participants (7)

Andrea Vezzosi
David Menendez
Edward Z. Yang
Ivan Lazar Miljenovic
Lennart Augustsson
Peter Padawitz
Sebastian Fischer