Đoạn mã scala vòng lặp vô hạn

Question

object Prop { 
    def simplify(prop : Prop) : Prop = { 
    prop match { 
     case Not(Or(a,b)) => simplify(And(Not(a),Not(b))) 
     case Not(And(a,b)) => simplify(Or(Not(a),Not(b))) 
     case Not(Not(a)) => simplify(a) 
     case _ => { 
     if (simplify(prop) == prop) prop 
     else prop 
     } 
    } 
    } 
} 

Tôi chắc chắn tôi đã có vòng lặp vô hạn do trường hợp 'mặc định' của tôi gây ra. Tôi đang sử dụng đệ quy trong mọi trường hợp. Đó là có nghĩa là, nhưng, chỉ khi Prop có thể được đơn giản hóa. Ngay khi Prop không thể được đơn giản hóa, nó sẽ trả về toàn bộ.

Tôi không thấy cách tôi có thể kiểm tra để đơn giản hơn nữa. (Tôi không được phép sử dụng các thư viện khác, như được đề xuất trong kênh freenodes #scala).

Ai đó có thể giải thích cho dù đó là 'trường hợp _' gây ra vòng lặp và cách giải quyết nó? Làm thế nào tôi có thể thử nghiệm để đơn giản hóa có thể mà không cần thực hiện một vòng lặp?

Cảm ơn trước!

Answer 1

Vấn đề là bạn đang cố gắng làm hai việc trong một bước cần phải xảy ra theo thứ tự - áp dụng luật của De Morgan (và loại bỏ đôi phủ định) và đệ quy đơn giản hóa mọi trẻ em. Đây là lý do tại sao chỉ cần thả một số case And(a, b) => And(simplify(a), simplify(b)) vào số match của bạn sẽ không hoạt động.

Hãy thử như sau:

val deMorganAndDoubleNegation: Prop => Prop = { 
    case Not(Or(a, b)) => And(Not(a), Not(b)) 
    case Not(And(a, b)) => Or(Not(a), Not(b)) 
    case Not(Not(a)) => a 
    case a => a 
} 

val simplify: Prop => Prop = deMorganAndDoubleNegation andThen { 
    case And(a, b) => And(simplify(a), simplify(b)) 
    case Or(a, b) => Or(simplify(a), simplify(b)) 
    case Not(a) => Not(simplify(a)) 
    case a => a 
} 

Answer 2

Khá rõ ràng điều gì xảy ra và bạn phù hợp với mặc định case. Nếu đầu vào của bạn prop không khớp với bất kỳ trường hợp nào bạn đang gọi:

simplify(prop) 

với cùng một đối số. Vì trước đây nó đã gây ra cuộc gọi đệ quy đến simplify() và bạn đang gọi hàm của mình với cùng một đầu vào, nó sẽ nhập lại simplify(). Vì vậy, đây không phải là một vòng lặp vô hạn mà không bao giờ chấm dứt cuộc gọi đệ quy:

...simplify(simplify(simplify(simplify(simplify(simplify(simplify(prop))))))) 

Tuy nhiên việc sửa chữa (dựa trên mã của bạn) rất đơn giản:

if (simplify(prop) == prop) prop 
    else prop 

chỉ cần thay thế nó với ...

case _ => prop 

Cả hai chi nhánh đều trả về cùng một giá trị. Điều này thực sự đúng nếu bạn nghĩ về một thời gian. Bạn có một bộ tối ưu hóa. Nếu không ai trong số họ phù hợp với các biểu thức của bạn, điều đó có nghĩa là nó không còn có thể được đơn giản hóa nữa. Do đó bạn đang trả lại nó như là.

BTW có vẻ như bạn đang thực hiện đơn giản hóa biểu thức boolean bằng cách sử dụng các kiểu chữ. Bạn có thể quan tâm đến tôi article nơi tôi làm như vậy nhưng với các biểu thức số học.

Answer 3

Có, trường hợp mặc định đang gây ra vòng lặp. if (simplify(prop) == prop) prop là dòng có vấn đề. Bạn không cần phải thử nghiệm nếu nó có thể được đơn giản hóa hơn nữa bởi vì khi bạn đang ở trong trường hợp mặc định tất cả các đơn giản hóa có thể được cố gắng.