Повторное использование шаблонов в шаблонах или выражениях

Question

Мой проект на Haskell включает в себя оценщик выражений, который для целей этого вопроса можно упростить до:

data Expression a where
    I :: Int -> Expression Int
    B :: Bool -> Expression Bool
    Add :: Expression Int  -> Expression Int  -> Expression Int
    Mul :: Expression Int  -> Expression Int  -> Expression Int
    Eq  :: Expression Int  -> Expression Int  -> Expression Bool
    And :: Expression Bool -> Expression Bool -> Expression Bool
    Or  :: Expression Bool -> Expression Bool -> Expression Bool
    If  :: Expression Bool -> Expression a    -> Expression a -> Expression a

-- Reduces an Expression down to the simplest representation.
reduce :: Expression a -> Expression a
-- ... implementation ...

Простой подход к реализации этого заключается в написании case выражение для рекурсивной оценки и сопоставления с образцом, например так:

reduce (Add x y) = case (reduce x, reduce y) of
                    (I x', I y') -> I $ x' + y'
                    (x', y')     -> Add x' y'
reduce (Mul x y) = case (reduce x, reduce y) of
                    (I x', I y') -> I $ x' * y'
                    (x', y')     -> Mul x' y'
reduce (And x y) = case (reduce x, reduce y) of
                    (B x', B y') -> B $ x' && y'
                    (x', y')     -> And x' y'
-- ... and similarly for other cases.

Для меня это определение выглядит несколько неловко, поэтому я переписал определение, используя шаблонные охранники, например:

reduce (Add x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' + y'

Я думаю, что это определение выглядит чище по сравнению с case выражением, но при определении нескольких шаблонов для разных конструкторов шаблон повторяется несколько раз.

reduce (Add x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' + y'
reduce (Mul x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' * y'

Отмечая эти повторяющиеся шаблоны, я надеялся, что будет какой-то синтаксис или структура, которые могли бы сократить повторение в сопоставлении с шаблоном. Существует ли общепринятый метод для упрощения этих определений?

Редактировать: после просмотра паттернов, я понял, что они не работают в качестве замены. Хотя они дают тот же результат, когда x а также y может быть уменьшен до I _, они не уменьшают никаких значений, когда охранники шаблонов не совпадают. Я все еще хотел бы reduce упростить подвыражения Add и другие.

Answer 1

Одно частичное решение, которое я использовал в аналогичной ситуации, состоит в том, чтобы извлечь логику в "подъёмную" функцию, которая принимает обычную операцию на Haskell и применяет ее к значениям вашего языка. Это абстрагируется от обертывания / распаковки и обработки ошибок.

Идея состоит в том, чтобы создать два класса типов для перехода к вашему пользовательскому типу и из него с соответствующей обработкой ошибок. Затем вы можете использовать их для создания liftOp функция, которая может выглядеть так:

liftOp :: (Extract a, Extract b, Pack c) => (a -> b -> c) -> 
            (Expression a -> Expression b -> Expression c)
liftOp err op a b = case res of
  Nothing  -> err a' b'
  Just res -> pack res
  where res = do a' <- extract $ reduce' a
                 b' <- extract $ reduce' b
                 return $ a' `op` b'

Тогда каждый конкретный случай выглядит так:

Mul x y -> liftOp Mul (*) x y

Что не так уж плохо: это не слишком избыточно. Он включает в себя информацию, которая имеет значение: Mul привязан к *и в случае ошибки мы просто применяем Mul снова.

Вам также понадобятся экземпляры для упаковки и распаковки, но они все равно полезны. Один из хитрых трюков заключается в том, что они также позволяют автоматически встраивать функции в DSL с помощью экземпляра формы. (Extract a, Pack b) => Pack (a -> b),

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

Я написал аналогичное решение для связанной (но несколько другой) проблемы. Это также способ обрабатывать переходы назад и вперед между значениями родного языка Haskell и интерпретатором, но интерпретатор структурирован по-другому. Некоторые из тех же самых идей должны все же применяться, хотя!

Answer 2

Этот ответ вдохновлен ответом на вопрос Rampion, который предлагает следующую функцию:

step :: Expression a -> Expression a
step x = case x of
  Add (I x) (I y) -> I $ x + y
  Mul (I x) (I y) -> I $ x * y
  Eq  (I x) (I y) -> B $ x == y
  And (B x) (B y) -> B $ x && y
  Or  (B x) (B y) -> B $ x || y
  If  (B b) x y   -> if b then x else y
  z               -> z

step смотрит на один термин и уменьшает его, если присутствует все необходимое для его сокращения. Оборудовано с stepнам нужен только способ заменить термин везде в дереве выражений. Мы можем начать с определения способа применения функции внутри каждого термина.

{-# LANGUAGE RankNTypes #-}

emap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
emap f x = case x of
    I a -> I a
    B a -> B a
    Add x y   -> Add (f x) (f y)
    Mul x y   -> Mul (f x) (f y)
    Eq  x y   -> Eq  (f x) (f y)
    And x y   -> And (f x) (f y)
    Or  x y   -> Or  (f x) (f y)
    If  x y z -> If  (f x) (f y) (f z)

Теперь нам нужно применять функцию везде, как к термину, так и везде внутри термина. Есть две основные возможности: мы могли бы применить функцию к термину, прежде чем применять его внутри, или мы могли бы применить функцию позже.

premap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
premap f = emap (premap f) . f

postmap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
postmap f = f . emap (postmap f)

Это дает нам две возможности для использования stepкоторый я назову shorten а также reduce,

shorten = premap step
reduce = postmap step

Они ведут себя немного по-другому. shorten удаляет самый внутренний уровень терминов, заменяя их литералами, сокращая высоту дерева выражений на единицу. reduce полностью вычисляет дерево выражения до литерала. Вот результат итерации каждого из них на одном входе

"shorten"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
If (And (B True) (B True)) (Add (I 1) (I 6)) (I 0)
If (B True) (I 7) (I 0)
I 7
"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
I 7

Частичное сокращение

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

data Expression a where
    Var :: Expression Int
    ...

Нам нужно будет добавить поддержку Var в emap:

emap f x = case x of
   Var -> Var
   ...

bind заменит переменную, и evaluateFor выполняет полную оценку, обходя выражение только один раз.

bind :: Int -> Expression a -> Expression a
bind a x = case x of
    Var -> I a
    z   -> z

evaluateFor :: Int -> Expression a -> Expression a
evaluateFor a = postmap (step . bind a)

Сейчас reduce повторяется на примере, содержащем переменную, производит следующий вывод

"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul Var (I 3))) (I 0)
Add (I 1) (Mul Var (I 3))

Если выходное выражение от сокращения оценивается для определенного значения Varмы можем уменьшить выражение до буквального.

"evaluateFor 5"
Add (I 1) (Mul Var (I 3))
I 16

Прикладное

emap вместо этого может быть написано с точки зрения ApplicativeFunctor, а также postmap может быть превращен в общий фрагмент кода, подходящий для других типов данных, кроме выражений. Как это сделать, описано в этом ответе на последующий вопрос Rampion.