Como compor `not` com uma função de aridade arbitrária?

Question

Quando tenho alguma função do tipo como

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

Gostaria função make que envolva esta função com não.

por exemplo. função de fazer como este

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

Eu posso fazer combinator como

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

Mas eu não sei como.

*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

O que estou fazendo de errado?

E pergunta bônus como posso fazer este para a função com mais e parâmetros lest por exemplo.

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

Answer 1

A menos que você quer ir cortando ao redor com typeclasses, o que é melhor deixar para experimentos mentais e prova de conceito, você simplesmente não generalizar para vários argumentos. Não tente.

Quanto à sua pergunta principal, este é o mais elegantemente resolvido com combinators editor semânticas do Conal Elliott . A combinator editor semântica é uma função com um tipo como:

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

Onde F(x) alguma expressão envolvendo x. Há também "contravariantes" combinators editor que levam um (b -> a) vez. Intuitivamente, um combinator editor seleciona uma parte de algum valor maior para operar. O que você precisa é chamado result:

result = (.)

Olhe para o tipo da expressão que você está tentando operar em:

a -> a -> Bool

O resultado (codomain) deste tipo é a -> Bool, eo resultado da que tipo é Bool, e isso é o que você está tentando aplicar not para. Portanto, para aplicar not para o resultado do resultado de uma f função, você escreve:

(result.result) not f

Esta muito bem generaliza. Aqui estão mais algumas combinadores:

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

Então, se você tem um valor x do tipo:

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

E você deseja aplicar not ao Bool, basta soletrar o caminho para chegar lá:

(result.left.result.second) not x

Ah, e se você chegou a Functores ainda, você vai perceber que fmap é um combinator editor. Na verdade, o acima pode ser escrito:

(fmap.left.fmap.fmap) not x

Mas eu acho que é mais claro para usar os nomes expandidos.

Aproveite.

Answer 2

Na verdade, fazendo arity arbitrária com aulas tipo acaba por ser incrivelmente fácil:

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

Obrigado por apontar este problema legal. Eu amo Haskell.

Answer 3

O n combinator pode ser escrita:

n = ((not .) .)

Quanto à sua pergunta bônus, a volta típico seria a criação de vários destes:

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

etc.

Answer 4

Re: O que estou fazendo de errado :

Eu acho que sua combinator é bom, mas quando você deixa-vinculá-lo ao mais alto nível, uma das 'regras padrão' irritantes do Haskell entra em jogo ea ligação não é generalizada:

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

Eu acho que você pode estar ficando derrotado pela 'restrição monomorphism', como ele se aplica ao tipo classes. Em qualquer caso, se você ficar fora do circuito de nível superior e colocar as coisas em um arquivo separado com uma assinatura de tipo explícito, tudo funciona bem:

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

Bônus pergunta : para fazer isso com mais e parâmetros de tipo mais, você pode tentar jogar truques escorbuto com o sistema de classe tipo. Dois artigos para consultar são papel Hughes e da Claessen em QuickCheck e papel de Ralf Hinze os genéricos para as massas .