haskell - Haskell 中的递归同义反复检查器

Question

(我知道 SO 上有一个 similar question，但我不认为这是一个骗局，因为我试图实现的函数是递归的，并且不使用列表或 lambda 表达式。我'我想知道如何以这种方式实现它，即使它们在功能上是等效的，主要是为了更好地理解 Haskell。)

我正在学习如何创建函数来检查给定的 bool 函数是否是同义反复。这是我正在阅读的书中的一个示例函数，它检查具有 1 个变量的 bool 函数:

valid1 :: (Bool -> Bool) -> Bool
valid1 bf = (bf True) && (bf False)

对于 2 和 3 个变量:

valid2 :: (Bool -> Bool -> Bool) -> Bool
valid2 bf = (bf True True)
            && (bf True False)
            && (bf False True)
            && (bf False False)

valid3 :: (Bool -> Bool -> Bool -> Bool) -> Bool
valid3 bf = and [ bf p q r | p <- [True,False],
                             q <- [True,False],
                             r <- [True,False]]

但在我看来，应该有一种更好的方法，而不是为每个具有不同数量变量的 bool 函数创建一个单独的检查器函数。例如，我们可以制作如下内容:

validR n bf :: Int -> (Bool -> a) -> Bool
validR n bf | n == 1    = valid1 bf 
            | otherwise = (validR (n-1) (bf True)) && (validR (n-1) (bf False))

其中 n 是正在检查的 bool 函数 bf 中的变量数量。当给定一个带有 n>1 个变量的 bool 函数 bf 时，该函数将分支到检查 bf True 和 bf False，最终检查所有可能的真值-值组合。但是当我尝试加载这个函数时，Haskell 给出错误消息“应用程序中的类型错误”。有没有办法调整这个函数的类型声明以使其工作？

我是 Haskell 新手，所以简单的解释将非常感激。提前致谢。

Answer 1

实际上，这可以很容易地完成。

{-# LANGUAGE FlexibleInstances    #-}

class BooleanFunc f where
  isTautology :: f -> Bool

instance BooleanFunc Bool where
  isTautology = id
instance (BooleanFunc b) => BooleanFunc (Bool -> b) where
  isTautology f = isTautology (f True) && isTautology (f False)

main = do
   print . isTautology $ \a b c d -> True || a || b || c || d
   print . isTautology $ \a b c d ->         a || b || c || d