Как составить `not` с функцией произвольной арности?

Question

Когда у меня есть какая-то функция типа, например

f :: (Ord a) => a -> a -> Bool
f a b = a > b

Я хотел бы создать функцию, которая обертывает эту функцию с помощью not.

например ,создайте функцию, подобную этой

g :: (Ord a) => a -> a -> Bool
g a b = not $ f a b

Я могу сделать комбинатор, подобный

n f = (\a -> \b -> not $ f a b)

Но я не знаю как.

*Main> let n f = (\a -> \b -> not $ f a b)
n :: (t -> t1 -> Bool) -> t -> t1 -> Bool
Main> :t n f
n f :: (Ord t) => t -> t -> Bool
*Main> let g = n f
g :: () -> () -> Bool

Что я делаю не так?

И дополнительный вопрос, как я могу сделать это для функции с большим количеством параметров, например

t -> Bool
t -> t1 -> Bool
t -> t1 -> t2 -> Bool
t -> t1 -> t2 -> t3 -> Bool

Answer 1

Если вы не хотите разбираться с классами типов, что лучше оставить для мысленных экспериментов и доказательства концепции, вы просто не обобщаете на несколько аргументов.Не пытайся.

Что касается вашего главного вопроса, то этот наиболее элегантно решается с помощью Conal Elliott's комбинаторы семантического редактора.Комбинатор семантического редактора - это функция с типом, подобным:

(a -> b) -> F(a) -> F(b)

Где F(x) является ли какое-то выражение включающим x.Существуют также "контравариантные" комбинаторы редакторов, которые принимают (b -> a) вместо этого.Интуитивно, редактор-комбинатор выбирает часть некоторого большего значения для работы.Тот, который вам нужен, называется result:

result = (.)

Посмотрите на тип выражения, с которым вы пытаетесь оперировать:

a -> a -> Bool

Результатом (кодоменом) этого типа является a -> Bool, и в результате это тип - это Bool, и это то , что вы пытаетесь применить not Для.Итак, чтобы применить not к результату результата функции f, вы пишете:

(result.result) not f

Это прекрасное обобщение.Вот еще несколько комбинаторов:

argument = flip (.)     -- contravariant

first f (a,b) = (f a, b)
second f (a,b) = (a, f b)

left f (Left x) = Left (f x)
left f (Right x) = Right x
...

Итак, если у вас есть ценность x типа:

Int -> Either (String -> (Int, Bool)) [Int]

И вы хотите подать заявку not для Bool вы просто указываете путь, чтобы добраться туда:

(result.left.result.second) not x

О, и если вы уже добрались до Функторов, вы заметите, что fmap является редактором-комбинатором.На самом деле, вышесказанное может быть записано по буквам:

(fmap.left.fmap.fmap) not x

Но я думаю, что понятнее использовать расширенные имена.

Наслаждайся.

Answer 2

На самом деле, выполнение произвольной арности с классами типов оказывается невероятно простым:

module Pred where

class Predicate a where
  complement :: a -> a

instance Predicate Bool where
  complement = not

instance (Predicate b) => Predicate (a -> b) where
  complement f = \a -> complement (f a)  
  -- if you want to be mysterious, then
  -- complement = (complement .)
  -- also works

ge :: Ord a => a -> a -> Bool
ge = complement (<)

Спасибо, что указали на эту классную проблему.Я люблю Хаскелла.

Answer 3

Ваш n-комбинатор может быть записан:

n = ((not .) .)

Что касается вашего бонусного вопроса, типичным обходным путем было бы создать несколько из этих:

lift2 = (.).(.)
lift3 = (.).(.).(.)
lift4 = (.).(.).(.).(.)
lift5 = (.).(.).(.).(.).(.)

и т.д.

Answer 4

Ре: Что я делаю не так?:

Я думаю, что ваш комбинатор в порядке, но когда вы разрешаете привязать его на верхнем уровне, вступает в игру одно из раздражающих "правил по умолчанию" Haskell, и привязка не обобщается:

Prelude> :ty (n f)
(n f) :: (Ord t) => t -> t -> Bool
Prelude> let g = n f
Prelude> :ty g
g :: () -> () -> Bool

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

module X where

n f = (\a -> \b -> not $ f a b)
f a b = a > b

g :: Ord a => a -> a -> Bool
g = n f

Бонусный вопрос:чтобы делать это со все большим количеством параметров типа, вы можете попробовать сыграть злую шутку с системой классов типов.Следует ознакомиться с двумя документами Хьюза и Классена бумага для быстрой проверки и статья Ральфа Хинце Дженерики для широких масс.