Общий шаблон рекурсии
Я привыкаю к функциям Haskell высшего порядка. Обычно я могу заменить явные шаблоны рекурсии с функциями как карта, сгиб и сканирование. Однако я часто сталкиваюсь со следующим шаблоном рекурсии, который я не понимаю, как выразить использующие функции высшего порядка:
f (x:[]) = k x
f (x:xs) = g x (f xs)
Например, предположите, что я представляю аналитические таблицы. Затем я создаю тип данных, такой как:
data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau)
Если я хочу преобразовать список Exprs в структуру таблицы, я хочу функциональную часть, которой мог бы напомнить:
f (x:[]) = N x
f (x:xs) = S x (f xs)
Теперь, я вижу три опции: (1) создают функцию, которая решает, учитывая таблицу и список, должно ли следующее ответвление в таблице быть S или N (или B, но мы будем игнорировать тот регистр); (2) используют функцию высшего порядка для инкапсуляции шаблона рекурсии f; (3) используют функцию как f.
Каков наилучший вариант был бы?
2 ответа
Скорее всего, я бы использовал следующее:
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) используйте «Может быть»:
С другой стороны, если f [] не может быть разумно определено, это еще хуже.
Частичные функции часто считаются уродливыми. Чтобы сделать его полным, вы можете использовать Может быть . Определить
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 | Минусы a (Список a) .
Если я правильно понял вопрос, то вот моя оценка ваших вариантов:
Вероятно, немного неприятно сопоставлять (предположительно произвольно сложную?) Таблицу снизу конструктор, чтобы написать эту функцию. Этот подход кажется несколько хрупким, хотя, вероятно, он будет работать нормально.
Я не вижу необходимости обобщать шаблон, учитывая, что это рекурсивная функция, работающая с рекурсивной структурой. Введение шаблона более высокого порядка (я думаю) запутало бы фактическую логику выполнения рекурсивного обхода этой структуры данных.
Я думаю, в этом есть смысл. Как вы заметили, это достаточно распознанный «шаблон», но я думаю, что он хорошо соответствует описанию алгоритма, чтобы записать его именно таким образом. Возможно, он не будет таким универсальным или многоразовым, но, учитывая, что это, по сути, суть алгоритмического подхода, я думаю, имеет смысл писать кейсы напрямую, как вы это делали в такой функции, как f. Это был бы мой предпочтительный подход.
Извините, что не предоставил конкретный ответ, но это достаточно субъективный ответ, поэтому, учитывая три приведенных выше варианта, я бы выбрал вариант 3 из соображений ясности и удобочитаемости.