Для справки, вот условия ...
data Term a =
Var a
| Lambda a (Term a)
| Apply (Term a) (Term a)
(отмечу, что представление переменных абстрагировано, что часто является хорошим планом.)
...и вот предложенная функция.
fmap' :: (Term a → Term a) → Term a → Term a
fmap' f (Var v) = f (Var v)
fmap' f (Lambda v t) = Lambda v (fmap' f t)
fmap' f (Apply t1 t2) = Apply (fmap' f t1) (fmap' f t2)
Что меня беспокоит в этом определении, так это то, что f когда-либо применяется только к терминам формы (Var v), так что вы могли бы также реализовать substitution .
subst :: (a → Term a) → Term a → Term a
subst f (Var v) = f v
subst f (Lambda v t) = Lambda v (subst f t)
subst f (Apply t1 t2) = Apply (subst f t1) (subst f t2)
Если бы вы немного позаботились о том, чтобы отличить границу от свободных переменных, вы могли бы сделать Term a Monad с заменой, реализующей (>>=).В общем случае термины могут иметь структуру Functor для переименования и структуру Monad для подстановки.Об этом есть прекрасная статья Берда и Патерсона , но я отвлекся.
Между тем, если вы do хотите действовать иначе, чем с переменными, один общий подход заключается виспользовать универсальные наборы инструментов обхода, такие как uniplate, как предполагает augustss.Другая возможность, возможно, немного более дисциплинированная, это работать с 'fold' для вашего типа.
tmFold :: (x -> y) -> (x -> y -> y) -> (y -> y -> y) -> Term x -> y
tmFold v l a (Var x) = v x
tmFold v l a (Lambda x t) = l x (tmFold v l a t)
tmFold v l a (Apply t t') = a (tmFold v l a t) (tmFold v l a t')
Здесь v, l и a определяют альтернативную алгебру для ваших Term -образующих операций, действуя только на y, а не Term x, объясняя, как обрабатывать переменные, лямбда-выражения и приложения.Вы можете выбрать y, чтобы быть m (Term x) для некоторой подходящей монады m (например, потоковое окружение для переменных), а не просто Term x.Каждый подтерм обрабатывается, чтобы дать y, затем выбирается соответствующая функция, чтобы получить y для всего термина.Сгиб захватывает стандартный шаблон рекурсии.
Обычные типы данных первого порядка (и некоторые хорошо организованные типы данных более высокого порядка) могут быть снабжены операторами сгиба.За счет читабельности вы даже можете написать оператор сгиба раз и навсегда.
data Fix f = In (f (Fix f))
fixFold :: Functor f => (f y -> y) -> Fix f -> y
fixFold g (In xf) = g (fmap (fixFold g) xf)
data TermF a t
= VarF a
| LambdaF a t
| ApplyF t t
type Term a = Fix (TermF a)
В отличие от вашего рекурсивного Term a, этот TermF a t объясняет, как сделать один слойтермина, с t элементами в подотчетных местах.Мы возвращаем рекурсивную структуру Term, используя рекурсивный тип Fix.Мы теряем немного косметически, в этом каждый слой имеет дополнительную In, оборачивающую его.Мы можем определить
var x = In (VarF x)
lambda x t = In (LambdaF x t)
apply t t' = In (Apply x t t')
, но мы не можем использовать эти определения при сопоставлении с образцом.Однако выгода в том, что мы можем использовать универсальный fixFold без каких-либо дополнительных затрат.Чтобы вычислить y из термина, нам нужно только дать функцию типа
TermF a y -> y
, которая (как и v, l и a выше) объясняет, как обрабатывать любыетермин, чьи подтермы уже были обработаны до значений типа y.Будучи явным в типах о том, из чего состоит один слой, мы можем подключиться к общей схеме работы слоя за слоем.