Общая схема рекурсии - PullRequest
Новая
       16

Общая схема рекурсии

13 голосов
/ 01 августа 2010

Я привыкаю к ​​функциям высшего порядка в Haskell. Обычно я могу заменить явные шаблоны рекурсии такими функциями, как map, fold и scan. Однако я часто сталкиваюсь со следующим шаблоном рекурсии, который я не понимаю, как выразить с помощью функций более высокого порядка: 

   f (x:[]) = k x
   f (x:xs) = g x (f xs)

Например, предположим, что я представляю аналитические таблицы. Затем я создаю тип данных, такой как: 

   data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau)

Если я хочу преобразовать список Expr s в структуру таблицы, мне нужна функция, часть которой может напоминать: 

   f (x:[]) = N x
   f (x:xs) = S x (f xs)

Теперь я вижу три варианта: (1) создать функцию, которая с учетом таблицы и списка решает, будет ли следующая ветвь в таблице S или N (или B, но мы проигнорируем этот случай); (2) использовать функцию высшего порядка для инкапсуляции шаблона рекурсии f; (3) используйте функцию типа f.

Каким будет лучший вариант?

Ответы [ 2 ]

8 голосов
/ 01 августа 2010

Скорее всего, я бы использовал следующее: 

f xs = foldr g (k (last xs)) (init xs)

Это в основном означает, что конец списка заменяется на k x при свертывании.Благодаря ленивой оценке, присутствующей везде, она работает даже для бесконечных списков.

Существует два других решения - добавление пустого регистра и использование Maybe.

A) добавление пустого регистра:

Было бы лучше, если бы f [] был четко определен.Затем вы можете написать определение как 

f [] = c
f (x:xs) = g x (f xs)

, что равно f = foldr g c.Например, если вы измените 

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau

на 

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau

, то вы можете представить одноэлементные таблицы как S expr N, а функция определена как однострочная 

f = foldr S N

Это лучшее решение, пока пустой регистр имеет смысл.

B) use Maybe:

С другой стороны, если f [] невозможно определить разумным образом,хуже.Частичные функции часто считаются безобразными.Чтобы сделать его общим, вы можете использовать Maybe.Определите 

 f [] = Nothing
 f [x] = Just (k x)
 f (x:xs) = Just (g x w)
            where Just w = f xs

Это общая функция - это лучше.

Но теперь вы можете переписать функцию в: 

 f [] = Nothing
 f (x:xs) = case f xs of
              Nothing -> Just (k x)
              Just w -> Just (g x w)

, которая является правой складкой: 

 addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux
 addElement x Nothing = Just (N x)
 addElement x (Just w) = Just (S x w)

 f = foldr addElement Nothing

В целом, сворачивание является идиоматическим и должно использоваться, когда вы подходите к шаблону рекурсии.В противном случае используйте явную рекурсию или попробуйте повторно использовать существующие комбинаторы.Если есть новый шаблон, создайте комбинатор, но только если вы будете часто использовать шаблон - иначе это излишне.В этом случае шаблон складывается для непустых списков, определяемых как: data List a = End a | Cons a (List a).

4 голосов
/ 01 августа 2010

Если я правильно понял вопрос, то вот моя оценка ваших вариантов:

  1. Вероятно, немного неприятно соответствовать таблице (предположительно произвольно сложной?)из-под конструктора, чтобы написать эту функцию.Этот подход кажется несколько хрупким, хотя, вероятно, он будет работать просто отлично.

  2. Я не вижу необходимости обобщать шаблон, учитывая, что это рекурсивная функция, работающая с рекурсивной структурой,Введение шаблона более высокого порядка (я думаю) затуманивает реальную логику, стоящую за выполнением рекурсивного обхода этой структуры данных.

  3. Я думаю, что это имеет большой смысл.Как вы заметили, это достаточно узнаваемый «шаблон», но я думаю, что он хорошо соответствует описанию алгоритма, чтобы записать его именно таким образом.Это может быть не так обобщенно или многократно, но, учитывая, что это, по сути, суть алгоритмического подхода, я думаю, что имеет смысл писать случаи напрямую, как вы делали в такой функции, как f.Это был бы мой любимый подход.

Извините, что не могу дать конкретный ответ, но это достаточно субъективный ответ, поэтому, учитывая три варианта выше, я бы выбрал вариант 3 по причинамясности и читабельности.

...