Блог

Главная - Вопросы по программированию - Хаскелл — рекурсия начинается с последнего члена

Хаскелл — рекурсия начинается с последнего члена

#haskell

Вопрос:

Предположим, что в моем коде haskell определена следующая структура данных

 data Exp = Expnum Int - constant
          | Expplus Exp Exp - addition

data Pair = Pnum Int
           | Plus Pair Pair

Я хотел бы написать функцию, которая может преобразовать выражение в следующее:

 -- Example: (Expplus (Expplus (Enum 5) (Enum 5)) Enum 6)
-- equivalent to ((5 5) 6)
convert :: Exp -> Pair
...

-- Expected output: Plus (Pnum 5 (Plus (Pnum 5) (Pnum 6)) 
-- equivalent to (5 (5 6))

Если здесь ожидаемая запись Plus((Plus (Pnum 5) (Pnum 5)) (Pnum 6) , у меня не будет проблем с написанием подобной функции.

Тем не менее, я понятия не имею, как я могу написать рекурсию, которая начинается с последнего термина, в то время как при анализе выражения оно будет (Expplus (Enum 5) (Enum 5)) вычисляться первым и возвращаться обратно

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

1. Не знаю, правильно ли я понял ваш вопрос, но знаете ли вы, как бы вы превратили список Int в а Pair с правильным ассоциативным уклоном? Тогда ответ состоит в том, чтобы выровнять входные данные с помощью обхода, а затем проанализировать их обратно в Pair

2. Итак: вы пример -> > [5,5,6] и это в Plus (Pnum 5 (Plus (Pnum 5) (Pnum 6)) ?

Ответ №1:

Сначала давайте исправим определения (синтаксис для комментария неправильный, и я хочу видеть результат, поэтому Pair он должен быть Show ), и ваш пример:

 data Exp = Expnum Int
          | Expplus Exp Exp

data Pair = Pnum Int
           | Plus Pair Pair  
           deriving (Show)

example :: Exp
example = Expplus (Expplus (Expnum 5) (Expnum 5)) (Expnum 6)

теперь идея состоит в том, чтобы сначала выровнять Exp или, если вам нравится, извлечь оттуда числа:

 extractConstants :: Exp -> [Int]
extractConstants (Expnum n) = [n]
extractConstants (Expplus a b) = extractConstants a    extractConstants b

это дает

 > extractConstants example
[5,5,6]

следующий шаг-построить на основе этого списка свой окончательный Pair :

 buildPair :: [Int] -> Pair
buildPair xs = foldr1 Plus $ map Pnum xs

поэтому сначала мы добавляем перенос каждого числа в a Pnum , а затем просто foldr1 используем Plus — вы можете eta-уменьшить xs здесь (см. Ниже).

обратите внимание, что это не соответствует [] — это не будет иметь значения, но у вас не должно быть этого в ИМО верхнего уровня-мы исправим это позже

это дает для списка желаемый результат:

 > buildPair [5,5,6]
Plus (Pnum 5) (Plus (Pnum 5) (Pnum 6))

так что все, что остается, — это объединить эти два:

 convert :: Exp -> Pair
convert = buildPair . extractConstants

и это все:

 > convert example
Plus (Pnum 5) (Plus (Pnum 5) (Pnum 6))

теперь проблема с пропущенным случаем решена — если вы подумаете об этом, это никогда не произойдет для формы, полученной в результате списка extractConstants (здесь не может быть пустого списка, так как нет способа выразить это с Exp помощью . В этом случае я бы поставил по крайней мере эту вспомогательную функцию в качестве where — здесь я решаю делать и то, и другое:

 convert :: Exp -> Pair
convert = buildPair . extractConstants
  where
    extractConstants (Expnum n) = [n]
    extractConstants (Expplus a b) = extractConstants a    extractConstants b

    buildPair = foldr1 Plus . map Pnum
Метки: