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

В моем проекте 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 и др.

Ответ 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, поэтому она все еще довольно централизована.

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

Ответ 2

Этот ответ основан на вопросе о продолжении пандура, в котором предлагается следующая функция:

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 вместо этого можно записать в терминах Applicative Functor, а postmap можно превратить в общий фрагмент кода, подходящий для других типов данных, чем выражения. Как это сделать, описано в этом ответе на вопрос о продолжении ответа.