Рекурсивный тавтологический контролер в Haskell

Question

(Я знаю, что есть similar question на SO, но я не думаю, что это обман, потому что функция, которую я пытаюсь реализовать, рекурсивна и не использует списки или лямбда Я хотел бы знать, как реализовать его таким образом, даже если они функционально эквивалентны, в основном для лучшего понимания Haskell.)

Я изучаю, как выполнять функции, которые проверяют, является ли данная булева функция тавтологией , Вот пример функции из книги я читал, что проверки булевых функций с 1 переменной:

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]] 

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

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 это число переменных в bf, булева функция, которая проверяется. Когда задана булева функция bf с n> 1 переменными, эта функция будет входить в проверку 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