3

我尝试reverse用Maybe. 我不知道如何Just使用递归返回模式匹配。例如，ghci> myReverse [1,2,3]需要返回Just [3,2,1]. 这是我的代码：

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

我认为那myReverse (x:xs) = Just $ myReverse xs ++ [x]行得通，但没有，我不知道该怎么做。我想知道的是如何做以及为什么。

谢谢你的帮助！

4

3 回答 3

5

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
于 2013-04-13T23:48:21.290 回答
5

myReverse返回 a Maybe [a]，它不能直接附加到某个东西，因为它不是一个列表。IOW 的值myReverse xs将是Nothing, 或Just <some list>。您需要对结果进行模式匹配。

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

当然，您需要决定在每种情况下需要做什么，具体取决于您想要myReverse做什么。

另请记住，并非每个函数都需要递归，因此您可以在需要时调用常规reverse函数myReverse。

于 2013-04-13T23:09:26.123 回答
1

我想到了一些类似于 luqui 的东西，除了最后应用 Maybe ：

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

或者，如果你愿意，

myReverse ys | null (reverse ys) = Nothing
             | otherwise         = Just (reverse ys)
于 2013-04-13T23:17:29.533 回答