Restricting type parameter to Monoid

Question

I've previously defined a function which takes a list of Maybes and turns it into a Maybe of a list, like so:

floop :: [Maybe a] -> Maybe [a]
floop [] = Just []
floop (Nothing:_) = Nothing
floop (Just x:xs) = fmap (x:) $ floop xs

Now I want to redefine it to be compatible with a larger class of containers, not just lists, and I've found that it needs to implement the functions foldr, mappend, mempty, fmap , and pure; so I figure that the following type line would be appropriate:

floop :: (Foldable t, Functor t, Monoid t) => t (Maybe a) -> Maybe (t a)

As (I think) it ensures that those functions are implemented for the given container, however it leads to the following error:

Expecting one more argument to ‘t’
The first argument of ‘Monoid’ should have kind ‘*’,
  but ‘t’ has kind ‘* -> *’
In the type signature for ‘floop'’:
  floop' :: (Foldable t, Functor t, Monoid t) =>
            t (Maybe a) -> Maybe (t a)

After looking into it, I found Monoid's kind is different to that of Functor and Foldable, but I can't see why that would be the case, nor how to correct the error.

For those interested, here's the current implementation:

floop :: (Foldable t, Functor t, Monoid t) => t (Maybe a) -> Maybe (t a)
floop xs = let
                f :: (Foldable t, Functor t, Monoid t) => Maybe a -> Maybe (t a) -> Maybe (t a)
                f Nothing _ = Nothing
                f (Just x) ys = fmap (mappend $ pure x) ys
            in
                foldr f (Just mempty) xs

Note: I have been made aware that this already exists as a builtin function (sequence), but I intend to implement it as a learning exercise.

Tangential note: if you want to compare `floop` to the builtin generalisation, I suggest looking at the more general [`sequenceA`](https://hackage.haskell.org/package/base-4.9.1.0/docs/Data-Traversable.html#v:sequenceA) rather than at `sequence`. — duplode, Feb 01 '17 at 14:05
Relevant: [*What can we do with Alternative but cannot do with Monoid?*](http://stackoverflow.com/q/31770710/2751851) — duplode, Feb 01 '17 at 14:18
(There are quite a few interesting questions about the relationship beetween `Alternative`, `MonadPlus` and `Monoid` that you might want to check as well. I linked to this one in particular because it is realtively brief and more clearly related to your concrete problem.) — duplode, Feb 01 '17 at 14:25
@duplode Thanks for the link, it helped me realise what I was doing wrong with `Monoid t`. I hadn't realised that `Monoid a` is a 'concrete' type, not a type constructor like `Foldable t`. — Zoey Hewll, Feb 02 '17 at 00:23
For what it's worth, you can *also* fix this just by changing `Monoid t` to `Monoid (t a)` everywhere (and upgrading `Functor t` to `Applicative t` everywhere, but that's not relevant to your actual question). — Daniel Wagner, Feb 02 '17 at 02:00
Thanks, yeah, that would have worked too. I actually noticed that t doesn't even need to be a `Functor`. I use `fmap` on the `Maybe`, not on `t` — Zoey Hewll, Feb 02 '17 at 02:14

score 9 · Accepted Answer · answered Feb 01 '17 at 14:21

Monoidal applicatives are described by the Alternative class, using (<|>) and empty instead of mappend and mempty:

floop :: (Foldable t, Alternative t) => t (Maybe a) -> Maybe (t a)
floop xs = let
                f :: (Foldable t, Alternative t) => Maybe a -> Maybe (t a) -> Maybe (t a)
                f Nothing _ = Nothing
                f (Just x) ys = fmap ((<|>) $ pure x) ys
            in
                foldr f (Just empty) xs

score 3 · Answer 2 · answered Feb 01 '17 at 18:19

3

This might be a good place to bring up hoogle.

Searching for t (m a)-> m (t a) returns sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a) as the first result. This then leads to the Traversable type class which is fairly close to what you are looking for.

As Lee said you could use the Alternative class which is the Applicative equivalent of Monoid. Slightly more generalized:

sequence' :: (Alternative t, Foldable t, Applicative a) => t (a b) -> a (t b)
sequence' = foldr step (pure empty)
  where step = liftA2 prepend
        prepend = (<|>) . pure

Here prepend first wraps some single element into t so it can use (<|>) to prepend it. liftA2 lets us abstract over the applicative a, you can imagine it as unwrapping two arguments, applying them to prepend and wrapping the result back up.

answered Feb 01 '17 at 18:19

Taren

674
5
11

1

This works perfectly, and I love that it is considerably more general; however I don't quite understand how `step` and `liftA2` work. Is `liftA2` similar to `fmap`? (though I notice that it has a higher arity) – Zoey Hewll Feb 02 '17 at 00:09
1

Lets look at the signature of fmap, with some brackets added for clarity: `(a -> b) -> (f a -> f b)`. We could see that as lifting a function so that it works over f's. This only works for functions with 1 argument, though. If we fmap `+1` over `Just 1` we get `Just (+1)` and can't continue with fmap. So instead we use the function `<*>` from Applicative which unpacks both sides before applying: `Just (+1) <*> Just 2 == Just 3`. There is also an operator form for fmap, `<$>`. Then we get `liftA2 f a b = f <$> a <*> b`! So your intuition is correct, liftA2 is basically fmap for two arguments. – Taren Feb 02 '17 at 11:05
I presume in that first example you mean to fmap `+` over `Just 1`. As for `<*>`, am I correct in thinking that `(Just f) <*> (Just x) == f <$> (Just x)`? So `liftA2 f a b` conceptually maps `f` over `a`, unwraps the result, then maps that over `b`? – Zoey Hewll Feb 03 '17 at 10:57
1

You got it! Similarly you could also implement fmap/<$> using only applicative, as `fmap f a = pure f <*> a`. – Taren Feb 03 '17 at 18:53

Restricting type parameter to Monoid

2 Answers2