Блог

Главная - Вопросы по программированию - Понимание рекурсии в функции, которая преобразует список Возможно a в Возможно [a]

Понимание рекурсии в функции, которая преобразует список Возможно a в Возможно [a]

#haskell #recursion

Вопрос:

Изучая Хаскелл, я наткнулся на эту функцию flipMaybe:

 flipMaybe :: [Maybe a] -> Maybe [a]
flipMaybe [] = Just []
flipMaybe (Nothing:xs) = Nothing
flipMaybe (Just x:xs) = case flipMaybe xs of  
    Nothing -> Nothing
    Just ls  -> Just (x:ls)

Я не могу понять последнюю строчку. Что ls здесь такое? Как здесь работает рекурсия? Или, другими словами, может ли кто-нибудь показать мне, как решает эта функция flipMaybe [Just 1, Just 2, Just 3] ? (шаг за шагом)

Комментарии:

1. ls являются ли данные, завернутые в a Just рекурсии , поэтому , если flipMaybe [Just 2, Just 3] это a Just (здесь Just [2, 3] , то ls это список [2, 3] , и это, таким образом, дополняется x и завернуто в a Just .

2. flipMaybe [Just 1, Just 2, Just 3] —> case flipMaybe [Just 2, Just 3] of ... —> case Just [2, 3] of Nothing -> Nothing; Just ls -> Just (1: ls) —> Just (1:[2, 3])

3. Другими словами, Just ls в case ... of ... is сопоставление с образцом, аналогичное сопоставлению с Just x:xs образцом в определении filpMaybe . Но на этот раз вместо сопоставления шаблонов на входе функции мы выполняем сопоставление шаблонов на выходе рекурсивного вызова flipMaybe xs

4. То, что вы здесь реализовали, является частным случаем sequence с m ~ Maybe и. t ~ []

Ответ №1:

Я не могу понять последнюю строчку. Что ls здесь такое?

Если рекурсивный вызов в конце списка возвращает a Just ls , то ls это список, завернутый в Just . Поэтому, если flipMaybe [Just 3] вызывается, это вернет a Just [3] , и, таким образом ls , есть [3] .

Это используется для добавления списка xs . Если мы таким образом оцениваем flipMaybe [Just 1, Just 2] , то сначала осматриваем первый пункт, если это а Nothing , мы возвращаемся Nothing : нас не волнует остальная часть списка, мы знаем , что результат будет а Nothing , если это а Just … , мы должны проверить, что flipMaybe [Just 2] вернется. Если он возвращает a Nothing , то мы , таким образом, возвращаемся Nothing , так как тогда это означает, что Nothing в конце списка есть a. Если это a Just ls , то мы возвращаем a Just (x : ls) , таким образом, мы добавляем элемент списка к результату рекурсивного вызова.

Если список таким образом выглядит [Just 2, Nothing, Just 3] , то мы сначала исследуем Just 2 , так как это не Nothing так , мы делаем рекурсивный вызов с. flipMaybe [Nothing, Just 3] Так как этот список начинается с a Nothing , Nothing возвращается из flipMaybe [Nothing, Just 3] , и, таким образом, мы возвращаемся Nothing за flipMaybe [Just 2, Nothing, Just 3] .

Метки: ,