Làm cách nào để đơn giản hóa một biểu thức số học cơ bản?

Question

Làm cách nào để đơn giản hóa biểu thức số học cơ bản?

ví dụ:

module ExprOps where 

simplify :: Expr -> Expr 
simplify (Plus(Var"x") (Const 0)) = Var "x" 

Tôi phải làm gì?

---

module Expr where 

-- Variables are named by strings, assumed to be identifiers. 
type Variable = String 

-- Representation of expressions. 
data Expr = Const Integer 
      | Var Variable 
      | Plus Expr Expr 
      | Minus Expr Expr 
      | Mult Expr Expr 
      deriving (Eq, Show) 

Các đơn giản hóa tôi có trong tâm trí là:

0*e = e*0 = 0 
1*e = e*1 = 0+e = e+0 = e-0 = e 

và đơn giản hóa subexpressions liên tục, ví dụ Plus (Const 1) (Const 2) sẽ trở thành Const 3. Tôi sẽ không mong đợi biến (hoặc các biến và hằng số) được nối: Var "st" là một biến riêng biệt từ Var "s".

Những gì tôi muốn đạt được là tạo ra một mô-đun như trên có sử dụng một chức năng gọi là simplify :: Expr->Expr rationals

Answer 1

chúng ta đang nói ở đây, giống như rationals GMP của? Nếu vậy, sau đó người ta có thể đơn giản hóa một bộ phận bằng cách làm cho đối số thứ hai vào nghịch đảo của nó và sau đó nhân lên.

Ngoài ra, phép nhân được thực hiện nhiều lần và phép chia được thực hiện nhiều lần.

Như Mitch đã nói trong các nhận xét, chúng tôi có thể làm với một số thông tin khác về những gì bạn đang cố gắng đơn giản hóa.

Answer 2

Vâng, bạn có mô hình chung phù hợp. Bạn chỉ cần thêm quy tắc và đệ quy áp dụng quy trình đơn giản hóa.

simplify :: Expr -> Expr 
simplify (Mult (Const 0) x) = Const 0 
simplify (Mult x (Const 0)) = Const 0 
simplify (Plus (Const 0) x) = simplify x 
simplify (Plus x (Const 0)) = simplify x 
simplify (Mult (Const 1) x) = simplify x 
simplify (Mult x (Const 1)) = simplify x 
simplify (Minus x (Const 0)) = simpify x 
simplify (Plus (Const x) (Const y)) = Const (x + y) 
simplify (Minus (Const x) (Const y)) = Const (x - y) 
simplify (Mult (Const x) (Const y)) = Const (x * y) 
simplify x = x 

Answer 3

Tôi đã làm điều này như một dự án cho lớp AI nhiều thập kỷ trước. Lớp đã sử dụng LISP, vì vậy điều đầu tiên tôi làm là chuyển đổi biểu thức từ ký hiệu infix sang S-Expression.

Sau đó, việc di chuyển "cây" một cách đệ quy và áp dụng một bộ quy tắc tại mỗi nút là một vấn đề. ví dụ. nếu nút này chứa một phép toán có toán hạng là cả hai hằng số, hãy thực hiện thao tác ngay bây giờ và thay thế nút đó bằng kết quả.

Khi chức năng cơ bản được đặt đúng chỗ, việc thêm các quy tắc đơn giản hóa mới vào hệ thống là vấn đề.

Cuối cùng, S-Expression đã được chuyển đổi trở lại ký hiệu infix để hiển thị.

Answer 4

Chỉ cần cung cấp cho bạn một ví dụ, đây là một hàm đơn giản hóa biểu thức bạn đã cung cấp. Ý tưởng là mỗi định nghĩa về đơn giản hóa được cố gắng từ trên xuống dưới cho đến khi một trong các mẫu ở phía bên tay trái của các dấu bằng khớp. Mục đích của định nghĩa cuối cùng là thoát ra khỏi đệ quy nếu không có cách nào được biết để đơn giản hóa thêm nữa.

simplify :: Expr -> Expr 
simplify (Plus l   (Const 0)) = simplify l 
simplify (Plus (Const 0) r  ) = simplify r 
simplify x       = x