[Haskell-cafe] Generalizing catMaybes

[David Menendez]

On Sat, Jan 8, 2011 at 12:05 PM, Conor McBride
<conor at 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>