Возможно и рекурсия в списке

Question

Я пытаюсь реализовать функцию 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] работа, но нет, и я не знаю, как это сделать. Что я хотел бы знать, так это, как это сделать и почему.

Спасибо за помощь!

Answer 1

myReverse возвращает Maybe [a], который не может быть непосредственно добавлен к чему-то, потому что это не список. IOW значение myReverse xs будет либо Nothing, либо Just <some list>. Результат должен совпадать с результатом.

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

И, конечно же, вы должны решить, что должно быть сделано в каждом из этих случаев, в зависимости от того, что вы хотите myReverse делать.

Также имейте в виду, что не каждый функция должна быть рекурсивной, так что вы можете вызвать регулярные reverse из myReverse, если вам это нужно.

Answer 2

я думал что-то вдоль линий luqui годов, за исключением того, применяя Может быть в конце:

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) 

Answer 3

Как [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 не будет.

Затем мы можем использовать mappend, (<>), чтобы связать наш рекурсивный вызов при условии, чтобы преобразовать головку списка в одноэлементный.

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" 

---

Предыдущий ответ складка

Зная, что обратный можно определить с помощью складка, как следовать,

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

Это можно переписать в виде,

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

Чтобы адаптироваться к Maybe типа, мы делаем следующее преобразование,

• Семя [] стать (Just [])
• Анонимная функция должна теперь быть применимы внутри Just, мы используем БПМЖ, чтобы сделать это.

Это приводит нас к,

>>> 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