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