Упрощая вложенные умножения в математическом выражении

Question

У меня есть следующий союз как мой AST для символического выражения математики:

type Expr = 
| Const of float 
| X of float * float 
| Sum of Expr * Expr 
| Mul of Expr * Expr 
| Pow of Expr * Expr 
| Sin of Expr 
| Cos of Expr 

static member (+) (e1,e2) = Sum(e1,e2) 
static member (*) (e1,e2) = Mul(e1,e2) 
static member (/) (e1,e2) = Mul(e1, Pow(e2,Const -1.0)) 

let (!) e = Mul(Const -1.0,e) 
let (^) e n = Pow(e ,n) 

Проблема:

Я пытаюсь упростить выражения, как Mul(Mul(expr1,expr2),expr3) или Mul(e,Mul(e1,e2)) или вообще при наличии n-вложенных умножений в выражении.

Я написал эту функцию simp, которая принимает Expr и рекурсивно упрощает вещи вниз. (Только некоторая алгебра), два правила этой функции (читать комментарии в коде) вызывает бесконечную рекурсию, когда функция simp вызывается из fullSimp

let rec simp expr = 
    match expr with 
    | Mul(Sum(e1,e2),e) -> simp (e1*e) + simp (e2*e) 
    | Mul(e,Sum(e1,e2)) -> simp (e1*e) + simp (e2*e) 
    | Mul(e1,e2) when e1 = e2 -> simp e1^Const 2.0 
    | Mul(Mul(e1,e2),e) -> Mul(simp (e1*e),simp e2) // adding this rule makes the function 'fullSimp' recurse infinitely 
    | Mul(e,Mul(e1,e2)) -> Mul(simp (e2*e), simp e1) // same as above 
    | Mul(e1,e2) -> simp e1 * simp e2 
    | Cos e -> Cos(simp e) 
    | Sin e -> Sin(simp e) 
    | _ -> expr 

, а затем есть функция fullSimp, которая вызывает simp до simp не возвращает никаких изменений в упрощенной версии выражения

let rec fullSimp e = 
    let simplified = simp e 
    if simplified <> e then fullSimp simplified 
    else simplified 

Попытка оценить следующее выражение дает бесконечную рекурсию !!!

fullSimp (Mul (Mul (Const 2.0,Cos (X (1.0,1.0))),Sin (X (1.0,1.0)))) 
// notice the nested multiplications here 
// also notice that this does not simplify any furthur so the function 
// should return the same input. 

Удаление двух правил из simp решает бесконечную рекурсию, но не проблема упрощения вложенных умножений.

Редактировать: Чтобы думать о проблеме по-другому, я пытаюсь собрать (умножить) константы и varibales, которые находятся в вложенных узлах mulitplication. Например, я пытаюсь принять такое выражение

Mul(Const 5.0,Mul(Mul (Const 2.0,Sin (X (4.0,2.0))),Mul (Cos (X (4.0,2.0)),X (8.0,1.0))))

и превратить его в Mul (Mul (X (80.0,1.0),Sin (X (4.0,2.0))),Cos (X (4.0,2.0))), который не может упрощенный любую Furthur

Примечания: Согласно обратной связи в комментариях я редактировал это пару раз. Теперь, надеюсь, ясно, в чем проблема. Извинения за несоответствия.

Answer 1

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

Это то, что я перегоняют свой упрощенный вариант для:

let rec simp expr = 
    match expr with 
    | Mul(Mul(e1,e2),e) -> Mul(simp (e1*e), simp e2) 
    | _ -> expr 

При попытке его на выражение тест, вы увидите, что она просто колеблется между двумя состояниями:

[Mul (Mul (Const 2.0,Sin (X (1.0,1.0))),Cos (X (1.0,1.0))); 
Mul (Mul (Const 2.0,Cos (X (1.0,1.0))),Sin (X (1.0,1.0))); 
Mul (Mul (Const 2.0,Sin (X (1.0,1.0))),Cos (X (1.0,1.0))); 
Mul (Mul (Const 2.0,Cos (X (1.0,1.0))),Sin (X (1.0,1.0))); ...] 

Какие на самом деле не удивительно, учитывая, что все это имеет значение e и e2 выражения (что еще более затушевано тем фактом, что вы перегрузили (*)). Этот случай представляет собой просто бесконечный цикл в ящике.

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

Answer 2

Я думаю, что я нашел то, что искал:

избежать inifinte рекурсию, или на самом деле не ввести его в первую очередь должен был изменить функцию fullSimp, как это только проверить, являются ли два выражения «равны» , так что теперь он также проверяет количество узлов изменилось после упрощения, так что я добавил ли эта длина функции:

let rec length expr = 
    match expr with 
    | Const _ 
    | X(_,_) -> 1 
    | Sum(e1,e2) 
    | Mul(e1,e2) 
    | Pow(e1,e2) -> 1 + (length e1) + length (e2) 
    | Sin(e) | Cos(e) | Exp(e) | Log(e) | Sinh(e) | Cosh(e) -> 1 + (length e) 

let notSameLength e1 e2 = 
    length e1 <> length e2 

затем я заменила 25+ образцы с теми, глядя на gaurds, она только меняет порядок умножения, когда оно «имеет смысл», т. е. когда вещи МОЖЕТ упростить Furthur: (я знаю, я звоню simp здесь дважды, пока не полностью оптимизирован)

| Mul(Mul(e1,e2),e) 
| Mul(e,Mul(e1,e2)) when notSameLength (e1*e) (simp (e1*e)) -> Mul(simp (e1*e),simp e2) 
| Mul(Mul(e1,e2),e) 
| Mul(e,Mul(e1,e2)) when notSameLength (e2*e) (simp (e2*e)) -> Mul(simp (e2*e),simp e1) 

и, наконец, fullSimp становится:

let rec fullSimp e = 
    let simplified = simp e 
    if simplified <> e && (length simplified <> length e) then fullSimp simplified 
    else simplified 

Каждый пример я попытался так далеко упрощает красиво, поэтому я думаю, что это решение.