Maybe and recursion on list

Question

I try to implement the reverse function with Maybe. I don't know how to return Just in pattern matching using recursion. By example, ghci> myReverse [1,2,3] need to return Just [3,2,1]. Here is my code :

myReverse :: [a] -> Maybe [a]
myReverse [] = Nothing
myReverse [x] = Just [x]
myReverse (x:xs) = myReverse xs ++ [x] -- here's my problem.

I thought that myReverse (x:xs) = Just $ myReverse xs ++ [x] work, but no and I don't know how to do it. What I would to know it is how to do it and why.

Thanks for your help!

Answer 1

myReverse returns a Maybe [a], which can't be directly appended to something because it is not a list. IOW the value of myReverse xs will be either Nothing, or Just <some list>. You need to pattern match on the result.

myReverse (x:xs) = 
    case myReverse xs of
         Just list -> ...
         Nothing   -> ...

And of course, you need to decide what needs to be done in each of these cases, depending on what you want myReverse to do.

Also keep in mind that not every function needs to be recursive, so you can call the regular reverse from myReverse if you need it.

Answer 2

As [a] is a Monoid define by,

instance Monoid [a] where
        mempty  = []
        mappend = (++)

Then Maybe [a] is also a Monoid,

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Note the type constraint in the instance declaration which impose a to be a Monoid or else Maybe a won't.

We can then use mappend, (<>), to chain our recursive call at the condition to transform the head of the list to a singleton.

import Data.Monoid ((<>))

myReverse :: [a] -> Maybe [a]
myReverse []     = Nothing
myReverse (x:xs) = myReverse xs <> Just [x]

Last note, the previous fold solution can be improve too.

>>> let mrev = foldl' (\x y -> Just [y] <> x ) Nothing
>>> mrev []
Nothing
>>> mrev "hello"
Just "olleh"

---

Previous fold answer

Knowing that reverse can be define using fold as follow,

>>> foldl' (flip (:)) [] [1..5]
[5,4,3,2,1]

This can be rewritten as,

>>> foldl' (\x y -> y:x) [] [1..5]
[5,4,3,2,1]

To adapt for Maybe type, we do the following transformation,

• The seed [] become (Just [])
• The anonymous function must now be apply inside Just, we use fmap to do it.

This lead us to,

>>> foldl' (\x y -> fmap (y:) x) (Just []) [1..5]
Just [5,4,3,2,1]

Finally,

mreverse xs | null xs = Nothing 
            | foldl' (\x y -> fmap (y:) x) (Just []) xs