CODEWITHSUNDEEP
haskelltypestype-kinds
Zoey Hewll
Zoey Hewll

Reputation: 5385

Restricting type parameter to Monoid

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.

Upvotes: 3

Views: 137

Answers (2)

Taren
Taren

Reputation: 684

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.

Upvotes: 3

Lee
Lee

Reputation: 144136

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

Upvotes: 9

Related Questions