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

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

43 голосов
/ 02 декабря 2011

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

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

как мне это сделать?

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

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

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

, чтобы можно было набрать: 

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

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

1 Ответ

55 голосов
/ 02 декабря 2011

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

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

class Stmt a where
    tautology :: a -> Bool

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

-- A Bool is a tautology if it's 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
...