Re: [Haskell-cafe] Generalizing catMaybes
* Tony Morris tonymor...@gmail.com [2011-01-08 12:56:28+1000] I am wondering if it possible to generalise catMaybes: (Something f, SomethingElse t) = t (f a) - t a I have being doing some gymnastics with Traversable and Foldable and a couple of other things from category-extras to no avail. Perhaps someone else's brain is molded into an appropriate shape to reveal an answer! For example, import Control.Applicative import Data.Foldable as F import Control.Monad.Writer cat' :: (Applicative list, Foldable list, Monoid (list a), Foldable maybe) = list (maybe a) - list a cat' = fold . fmap (execWriter . F.mapM_ (\x - tell (pure x))) However, this looks rather useless -- there are probably not many containers which can be substituted instead of 'list'. I think catMaybes deserves its own typeclass, which would represent truncatable structures: class Truncatable struct where catMaybes :: struct (Maybe a) - Maybe a This would make perfect sense for Set, Map etc. -- Roman I. Cheplyaka :: http://ro-che.info/ Don't worry what people think, they don't do it very often. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Sat, 8 Jan 2011, Roman Cheplyaka wrote: I think catMaybes deserves its own typeclass, which would represent truncatable structures: class Truncatable struct where catMaybes :: struct (Maybe a) - Maybe a But catMaybes has the type catMaybes :: struct (Maybe a) - struct a for struct = [] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
* Henning Thielemann lemm...@henning-thielemann.de [2011-01-08 12:06:33+0100] On Sat, 8 Jan 2011, Roman Cheplyaka wrote: I think catMaybes deserves its own typeclass, which would represent truncatable structures: class Truncatable struct where catMaybes :: struct (Maybe a) - Maybe a But catMaybes has the type catMaybes :: struct (Maybe a) - struct a for struct = [] Thanks, that was a typo. -- Roman I. Cheplyaka :: http://ro-che.info/ Don't worry what people think, they don't do it very often. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Fri, 7 Jan 2011, Brandon S Allbery KF8NH wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 1/7/11 21:56 , Tony Morris wrote: I am wondering if it possible to generalise catMaybes: (Something f, SomethingElse t) = t (f a) - t a I have being doing some gymnastics with Traversable and Foldable and a couple of other things from category-extras to no avail. Perhaps someone else's brain is molded into an appropriate shape to reveal an answer! Looks to me like you want something like: mtraverse :: (Traversable t, Monoid m) = t m - m mtraverse xs = traverse mappend (mempty:xs) or possibly the same kind of thing using MonadPlus instead of Monoid. This is not type-correct, isn't it? Foldable.fold has the type, that you propose. For me, the solutions of Dave Menendez make most sense: Generalize Maybe to Foldable and List to MonadPlus. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On 8 Jan 2011, at 11:14, Henning Thielemann wrote: For me, the solutions of Dave Menendez make most sense: Generalize Maybe to Foldable and List to MonadPlus. What has it to do with monads? There's no bind in sight. Alternative is certainly a more general alternative, but then I would say that, wouldn't I? Even that seems a tad too much. Cheers Conor ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Sat, 8 Jan 2011, Conor McBride wrote: On 8 Jan 2011, at 11:14, Henning Thielemann wrote: For me, the solutions of Dave Menendez make most sense: Generalize Maybe to Foldable and List to MonadPlus. What has it to do with monads? There's no bind in sight. I see a '=' in front of each of his expressions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 1/8/11 07:11 , Conor McBride wrote: On 8 Jan 2011, at 11:14, Henning Thielemann wrote: For me, the solutions of Dave Menendez make most sense: Generalize Maybe to Foldable and List to MonadPlus. What has it to do with monads? There's no bind in sight. Alternative is certainly a more general alternative, but then I would say that, wouldn't I? Even that seems a tad too much. That was my thought too, and no, I didn't actually test first, just tried to think out what he was doing. Bad idea when half asleep :/ - -- brandon s. allbery [linux,solaris,freebsd,perl] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk0oln8ACgkQIn7hlCsL25WL1gCfepiOrw2ptUKah1KNj1vychnZ 1dMAoL2CmnbV2T/ravh6fuc8oyzlncrt =Hx/b -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On 8 Jan 2011, at 15:27, Henning Thielemann wrote: On Sat, 8 Jan 2011, Conor McBride wrote: On 8 Jan 2011, at 11:14, Henning Thielemann wrote: For me, the solutions of Dave Menendez make most sense: Generalize Maybe to Foldable and List to MonadPlus. What has it to do with monads? There's no bind in sight. I see a '=' in front of each of his expressions. That'll teach me to wake up first. Sorry. If you have some m (f x), and you make an (m x) from each inner x, then you do need something joiny. Of course, there is an alternative generalisation. [] and Maybe are both Foldable, hence so is their composition. There's got to be a thing of type collapse :: (Foldable f, Alternative a) = f x - a x which would do the job. Of course, anything which is both foldable and alternative certainly has a function with the type of join. Cheers Conor ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Sat, 8 Jan 2011, Conor McBride wrote: Of course, there is an alternative generalisation. [] and Maybe are both Foldable, hence so is their composition. There's got to be a thing of type collapse :: (Foldable f, Alternative a) = f x - a x which would do the job. Nice! It would be collapse = Data.Foldable.foldr (\a b - pure a | b) empty and with transformers:Data.Functor.Compose (or the one from TypeCompose) we get catMaybes = collapse . Compose Of course, anything which is both foldable and alternative certainly has a function with the type of join. join = collapse . Compose :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Sat, Jan 8, 2011 at 12:05 PM, Conor McBride co...@strictlypositive.org wrote: On 8 Jan 2011, at 15:27, Henning Thielemann wrote: On Sat, 8 Jan 2011, Conor McBride wrote: On 8 Jan 2011, at 11:14, Henning Thielemann wrote: For me, the solutions of Dave Menendez make most sense: Generalize Maybe to Foldable and List to MonadPlus. What has it to do with monads? There's no bind in sight. I see a '=' in front of each of his expressions. That'll teach me to wake up first. Sorry. If you have some m (f x), and you make an (m x) from each inner x, then you do need something joiny. Of course, there is an alternative generalisation. [] and Maybe are both Foldable, hence so is their composition. There's got to be a thing of type collapse :: (Foldable f, Alternative a) = f x - a x which would do the job. Something along these lines, I'd imagine. collapse = foldr (\a b - pure a | b) empty Then, to get catMaybes you could either use composition, or just write it out manually: doubleCollapse = foldr (\a b - foldr (\c d - pure c | d) empty a | b) empty :: (Foldable f, Foldable g, Alternative h) = f (g a) - h a For the generalized catMaybes, f ~ h. Of course, anything which is both foldable and alternative certainly has a function with the type of join. Right, that's doubleCollapse when f ~ g ~ h. Alternative and Foldable are both specified rather loosely, so it's not clear how closely doubleCollapse approximates join. In particular, are | and empty expected to form a monoid? If not, we could define a list- or stream-like structure that uses alternation instead of appending for (|). That would not behave at all like join. Right now, I suspect any type which has with a monoidal structure, pure, and a fold that respects the monoid has a join. That is, if you have: foldMap f mempty = mempty foldMap f (a `mappend` b) = foldMap f a `mappend` foldMap f b then when f = pure you can take a structure apart and put it back together piece by piece. I think that's enough to get you join. Naturally, if you also have pure and fmap, you also have a monad. -- 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] Generalizing catMaybes
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Thanks guys for all the solutions. A slight correction below. On 09/01/11 03:54, David Menendez wrote: Naturally, if you also have pure and fmap, you also have a monad. You have a pointed functor but not necessarily a monad. There are many pointed functors that are not monads. The paper, Applicative Programming with Effects (McBride, Paterson) lists a couple. - -- Tony Morris http://tmorris.net/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk0o4AgACgkQmnpgrYe6r62z4wCgk4A1njS5lLH3RHtxfnIkVGTL t3sAoKNm7HjVQyk/Gb1AL5LxahRHPmKN =5D4j -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Sat, Jan 8, 2011 at 5:07 PM, Tony Morris tonymor...@gmail.com wrote: Thanks guys for all the solutions. A slight correction below. On 09/01/11 03:54, David Menendez wrote: Naturally, if you also have pure and fmap, you also have a monad. You have a pointed functor but not necessarily a monad. You perhaps missed the word also. If you have join, and you also have pure and fmap, then you have a monad. That's admittedly a little fuzzy about what it means to have join, since the laws join must satisfy are defined in terms of fmap and pure. -- 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
[Haskell-cafe] Generalizing catMaybes
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 I am wondering if it possible to generalise catMaybes: (Something f, SomethingElse t) = t (f a) - t a I have being doing some gymnastics with Traversable and Foldable and a couple of other things from category-extras to no avail. Perhaps someone else's brain is molded into an appropriate shape to reveal an answer! - -- Tony Morris http://tmorris.net/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk0n0lwACgkQmnpgrYe6r6155gCeLjYizQ/5w1r2qkecbEqiQqq5 ihIAn1bmmK/qNFxM2sSusqjJu/g2/lH7 =+SdM -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 1/7/11 21:56 , Tony Morris wrote: I am wondering if it possible to generalise catMaybes: (Something f, SomethingElse t) = t (f a) - t a I have being doing some gymnastics with Traversable and Foldable and a couple of other things from category-extras to no avail. Perhaps someone else's brain is molded into an appropriate shape to reveal an answer! Looks to me like you want something like: mtraverse :: (Traversable t, Monoid m) = t m - m mtraverse xs = traverse mappend (mempty:xs) or possibly the same kind of thing using MonadPlus instead of Monoid. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe - -- brandon s. allbery [linux,solaris,freebsd,perl] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk0n20AACgkQIn7hlCsL25V0MACeIJjbHmIjnABHxpykeVdcZ62f fS0AoL2xet/PpuvyuioWNvbzCTqWz5Z/ =2HGT -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing catMaybes
On Fri, Jan 7, 2011 at 9:56 PM, Tony Morris tonymor...@gmail.com wrote: I am wondering if it possible to generalise catMaybes: (Something f, SomethingElse t) = t (f a) - t a I have being doing some gymnastics with Traversable and Foldable and a couple of other things from category-extras to no avail. Perhaps someone else's brain is molded into an appropriate shape to reveal an answer! This gets you part of the way there: (= maybe mzero return) :: (MonadPlus m) = m (Maybe a) - m a I'm not sure what the SomethingElse should look like. One possibility would be Foldable. (= Data.Foldable.foldr (mplus . return) mzero) :: (MonadPlus m, Foldable t) = m (t a) - m a I have a MonadPlus-to-Monoid wrapper I call MSum, so I could also write it, (= getMSum . foldMap (MSum . return)) :: (MonadPlus m, Foldable t) = m (t a) - m a -- 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