CODEWITHSUNDEEP
haskell
vildric
vildric

Reputation: 950

Maybe and recursion on list

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!

Upvotes: 3

Views: 1136

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

I thought of something along the lines of luqui's, except applying the Maybe at the end:

myReverse :: [a] -> Maybe [a]
myReverse ys
  | null (myReverse' ys) = Nothing
  | otherwise            = Just (myReverse' ys)
 where
   myReverse' []     = []
   myReverse' (x:xs) = myReverse' xs ++ [x]

Or, if you will,

myReverse ys | null (reverse ys) = Nothing
             | otherwise         = Just (reverse ys)

Upvotes: 1

zurgl
zurgl

Reputation: 1930

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

Upvotes: 5

luqui
luqui

Reputation: 60463

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.

Upvotes: 5

Related Questions