Как написать функцию Haskell, которая принимает вариационную функцию как аргумент

Я пытаюсь создать функцию, которая получает вариационную функцию в качестве аргумента, т.е.

func :: (a -> ... -> a) -> a

как я могу это сделать?

Я читал о поливариадических функциях, и я уверен, что Олег уже сделал это, однако я потерял попытку применить шаблон к функции с вариационной функцией в качестве аргумента. Особенно подход Олега, похоже, работает только с расширениями в Глазго, и я хочу, чтобы решение работало в чистом Haskell 98 (например, Text.Printf).

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

isTautology :: (Bool -> ... -> Bool) -> Bool

чтобы можно было ввести:

isTautology (\x -> x && not x)
isTautology (\x y -> x && y || not y)

Моя проблема в том, что я продолжаю читать об этом трюке, чтобы сделать возвращаемый тип переменной типа (так, чтобы он мог быть результатом или другой функцией), но мой тип возврата исправлен (Bool).

Ответы

Ответ 1

Трюк состоит в том, чтобы создать класс типа, для которого вы будете определять экземпляр для функций, и экземпляр для возвращаемого типа. Тот факт, что он a Bool не является проблемой вообще.

Мы пытаемся написать функцию, которая принимает вариационный аргумент и возвращает Bool, поэтому мы будем определять класс типа с такой функцией.

class Stmt a where
    tautology :: a -> Bool

Далее мы определяем экземпляр для возвращаемого типа вариационной функции. В этом случае Bool.

-- A Bool is a tautology if it True.
instance Stmt Bool where
    tautology = id

Ключевой частью является следующий экземпляр для функций, которые принимают аргумент Bool, а тип возвращаемого типа - это некоторый тип из нашего класса. Таким образом, этот экземпляр будет применяться несколько раз, если функция принимает несколько аргументов.

-- A function is a tautology if it always returns a tautology.
instance Stmt b => Stmt (Bool -> b) where
    tautology f = tautology (f True) && tautology (f False)

Для записи этого метода требуется FlexibleInstances из-за Bool во втором экземпляре. Чтобы сделать то же самое с чистым Haskell 98, нам нужно будет использовать переменную типа с ограниченным ограничением. Например, мы можем использовать Bounded и Enum (есть экземпляры для Bool), или вы можете создать свой собственный класс, который позволит вам построить соответствующие входы.

instance (Enum a, Bounded a, Stmt b) => Stmt (a -> b) where
    tautology f = all (tautology . f) [minBound .. maxBound]

И все готово. Попробуйте:

> tautology $ \x y -> (not x && not y) == not (x && y)
False
> tautology $ \x y -> (not x && not y) == not (x || y)
True