Принудительная оценка первой в сопоставлении с образцом - PullRequest
Новая
       42

Принудительная оценка первой в сопоставлении с образцом

0 голосов
/ 05 февраля 2020

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

func (Plus a b) = func (Plus (func a) (func b))

Обратите внимание, что a и func a относятся к одному типу. Когда я пытаюсь вызвать что-то вроде этого, программа зависает, и я думаю, что происходит то, что шаблон бесконечно сопоставляется с самим собой, прежде чем оценивать внутренние (func a) и (func b), которые в противном случае сопоставили бы его с другим шаблоном. , Я пытался использовать что-то вроде 

func (Plus a b) = func (Plus newa newb)
    where newa = func a
          newb = func b

, чтобы сначала попытаться форсировать оценку func a и func b, но это не работает. То, что я пытаюсь сделать, даже возможно?

Спасибо.

1 Ответ

3 голосов
/ 05 февраля 2020

Вы попадаете в al oop, где вы повторяете Plus снова и снова, но чего вы ожидаете? 

func (Plus a b)
   = func (Plus (func a) (func b))
   = func (Plus (func (func a)) (func (func b)))
   = func (Plus (func (func (func a))) (func (func (func b))))

Проблема в том, что вы, по сути, говорите "оценить * 1005" * на конструкторе Plus, оцените func на конструкторе Plus ".

Как выглядит остальная часть func? Ваш подход, в принципе, мог бы работать, если бы все определение было примерно таким: 

func (Plus (Lit n) (Lit m)) = Lit (n + m)
func (Plus a b) = func (Plus (func a) (func b))

Здесь, если func a и func b в конечном итоге сократятся до Lit, тогда первый шаблон будет соответствовать и вызов будет прекращено. Но я бы не решился написать такую ​​функцию, потому что откуда вы знаете, что повторный вызов func для аргумента в конечном итоге приведет к Lit? Вероятно, будет случай, когда этого не произойдет.

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

data Expr = Lit Int | Var String | Plus Expr Expr

Для этого пример нормальной формы может быть: 

data ExprNF = ExprNF Int [String]

, который представляет собой константу плюс сумму переменных в отсортированном порядке (сохранить отсортировано так, чтобы эквивалентные выражения всегда сравнивались равными). Поэтому, если бы ваше выражение было 

1 + (x + 2) + (3 + 6) + (x + (y + x))

Это стало бы нормальной формой: 

ExprNF 10 ["x","x","x","y"]

Ваш редуктор func :: Expr -> ExprNF вычисляет нормальную форму рекурсивно, и нет необходимости повторно вызывать ее в надежде на сближение. 

func :: Expr -> ExprNF
func (Lit n) = ExprNF n []
func (Var s) = ExprNF 0 [s]
func (Plus a b) = case (func a, func b) of
    (ExprNF n vs, ExprNF n' vs') -> ExprNF (n + n') (sort (vs ++ vs'))

Нам никогда не нужно уменьшать какой-либо узел в дереве более одного раза, потому что мы сразу получаем нормальную форму.

...