Maybe and recursion on list

Question

我尝试用Maybe实现reverse函数。我不知道如何返回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]工作，但没有，我不知道怎么做。我想知道的是如何去做以及为什么去做。

谢谢你的帮助!

Answer 1

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

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

当然，您需要决定在每种情况下需要做什么，这取决于您希望myReverse做什么。

还请记住，并非每个函数都需要递归，因此如果需要，可以从myReverse调用常规的reverse。

Answer 2

由于[a]是一个Monoid定义为，

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

那么Maybe [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)

注意实例声明中的类型约束，强制a为Monoid，否则Maybe a不会。

然后可以使用mapappend, (<>)在条件处链接递归调用，将列表头转换为单例类型。

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

最后注意，前面的折叠解决方案也可以改进。

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

---

前一个折叠答案

知道反向可以用fold定义，

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

可以重写为，

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

为了适应Maybe类型，我们进行以下转换，

• 种子[]变成(Just [])
• 匿名函数现在必须在Just中应用，我们使用fmap来实现。

这导致我们，

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

最后,

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

Answer 3

我想到了一些与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)