Bảng chân lý từ các hàm ẩn danh trong Haskell

Question

Tôi đang cố gắng tạo một bảng chân lý cho một biểu thức boolean đã cho. Tôi có thể làm điều này với việc tạo một BoolExpr Datatype mới, nhưng tôi muốn làm điều đó với một hàm ẩn danh. Đó là nghĩa vụ phải làm việc như thế này:

> tTable (\x y -> not (x || y)) 
output: 
F F | T 
F T | F 
T F | F 
T T | F 

cách tiếp cận của tôi:

tbl p = [(uncurry p) tuple | tuple <- allval] 
     where allval=[(x,y) | x <- [False,True], y <- [False,True]] 

này hoạt động, nhưng chỉ cho 2 Arguments. Tôi muốn làm điều đó cho bất kỳ số lượng các đối số. Vì vậy, tôi figured tôi sẽ thực hiện một chức năng mà sẽ đưa các luận cứ từ một danh sách:

argsFromList f []  = f 
argsFromList f (x:xs) = argsFromList (f x) xs 

này không hoạt động:

Occurs check: cannot construct the infinite type: t = t1 -> t 
    Expected type: t -> [t1] -> t1 -> t 
    Inferred type: (t1 -> t) -> [t1] -> t1 -> t 
In the expression: argsFromList (f x) xs 

Tôi không hiểu những gì vấn đề là ở đây. Tôi sẽ rất biết ơn nếu có ai có thể chỉ cho tôi đi đúng hướng hoặc đăng một liên kết.

Answer 1

Vấn đề ở đây là bạn đang cố gắng gọi một hàm đệ quy với một kiểu khác cho bước đệ quy. Hãy xem xét định nghĩa:

argsFromList f []  = f 
argsFromList f (x:xs) = argsFromList (f x) xs 

Hãy thử suy ra loại chính mình. Chúng tôi có thể thấy ngay rằng đối số đầu tiên f phải là một chức năng của ít nhất một đối số, đối số thứ hai (x:xs) là một danh sách, và các yếu tố danh sách nên cùng loại như là đối số đầu tiên của f. Trong trường hợp đầu tiên, đối số f được trả về, vì vậy kiểu trả về cuối cùng phải giống với đối số đầu tiên. Vì vậy, chúng ta bắt đầu với điều này:

argsFromList :: (a -> ?) -> [a] -> (a -> ?) 

Để tìm biết loại ?, chúng ta có thể nhìn vào trường hợp thứ hai, trong đó bao gồm một cuộc gọi đệ quy. Đối số xs là cùng một loại danh sách và đối số (f x) có loại ?. Vì nó được sử dụng làm đối số đầu tiên trong cuộc gọi đệ quy, có loại (a -> ?), bây giờ chúng ta có thể kết luận rằng ? là cùng loại với (a -> ?) do đó cùng loại với (a -> (a -> ?)) do đó cùng loại với (a -> (a -> (a -> ?))). oops.

Đó sẽ là "loại vô hạn", tất nhiên.

Nếu bạn muốn thực hiện điều này với các hàm sử dụng một số biến đối số của một loại, có thể bạn sẽ muốn sử dụng các hàm lấy danh sách giá trị thay vì đối số riêng lẻ. Nếu không, bạn sẽ phải viết từng phiên bản riêng lẻ hoặc sử dụng một số thủ thuật phức tạp liên quan đến các tính năng ngôn ngữ nâng cao, cả hai đều không hấp dẫn trong một trường hợp đơn giản như thế này.

Answer 2

Nếu bạn muốn xây dựng một bảng sự thật cho các chức năng boolean với một số tùy ý của các đối số, bạn đang tạo ra một chức năng mà phải làm việc cho nhiều loại, vì vậy bạn sẽ phải sử dụng các lớp học kiểu:

{-# LANGUAGE FlexibleInstances #-} 

class TruthTable a where 
    truthTable :: a -> [([Bool], Bool)] 

instance TruthTable Bool where 
    truthTable b = [([], b)] 

instance TruthTable a => TruthTable (Bool -> a) where 
    truthTable f = [ (True : inps, out) | (inps, out) <- truthTable (f True)] ++ 
       [ (False : inps, out) | (inps, out) <- truthTable (f False)] 

Ví dụ:

*Main> mapM_ print $ truthTable (&&) 
([True,True],True) 
([True,False],False) 
([False,True],False) 
([False,False],False) 

Answer 3

Điều bạn đang yêu cầu không hề đơn giản. Haskell không làm cho nó dễ dàng để đối phó với các hàm áp dụng các hàm với số lượng các đối số thay đổi.Ví dụ: zip functions from Data.List có các biến thể riêng biệt cho các số đối số khác nhau (zip, zip3, zip4, ...). Tương tự như vậy, trong Control.Monad có liftM, liftM2, liftM3 ...

Về cơ bản, loại chung nhất mà bạn có thể gán cho một hàm với một số không rõ các đối số là a -> b; một chức năng thật một chỗ là Bool -> Bool (a = Bool, b = Bool), một chức năng thật hai nơi là Bool -> (Bool -> Bool) (a = Bool, b = Bool -> Bool), ba nơi là Bool -> (Bool -> (Bool -> Bool)) (a = Bool, b = Bool -> (Bool -> Bool)) , v.v. Nhưng không có cách nào dễ dàng để bạn có thể nhìn vào hàm mà bạn đã được truyền vào để biết loại nào ở bên phải mũi tên ban đầu.

Một loại giải pháp có thể được thực hiện để làm việc liên quan đến việc sử dụng các lớp loại để xác định các trường hợp riêng biệt của hàm trình tạo bảng chân lý cho từng loại hàm đối số. Câu trả lời của Sjoerd Visscher trong chủ đề này là làm điều đó cho tất cả các kích thước chức năng bằng cách sử dụng một định nghĩa cá thể đệ quy (lưu ý khai báo đệ quy TruthTable a => TruthTable (Bool -> a)). Có thể có các giải pháp khác có thể được xây dựng bằng cách sử dụng lớp loại Applicative.