Как составить «не» с функцией произвольной арности? - PullRequest
Новая
       25

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

31 голосов
/ 05 января 2009

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

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

Мне хотелось бы сделать функцию, которая обернет эту функцию не.

например. сделать функцию, как это 

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

Ответы [ 4 ]

40 голосов
/ 08 января 2009

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

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 (<)

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

40 голосов
/ 06 января 2009

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

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

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

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

result = (.)

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

a -> a -> Bool

Результат (codomain) этого типа равен 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

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

(fmap.left.fmap.fmap) not x

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

Наслаждайтесь.

12 голосов
/ 05 января 2009

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

n = ((not .) .)

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

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

и т.д.

9 голосов
/ 05 января 2009

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

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

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

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

...