¿Cómo componer `no 'con una función de aridad arbitraria?

Question

Cuando tengo alguna función de tipo como

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

Me gustaría hacer la función que envuelve esta función con no.

por ejemplo hacer funcionar como este

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

Puedo hacer un combinador como

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

Pero no sé cómo.

*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

¿Qué estoy haciendo mal?

Y la pregunta adicional sobre cómo puedo hacer esto para la función con más y menos parámetros, por ejemplo,

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

Answer 1

A menos que quiera ir a piratear con clases de tipos, que es mejor dejar para experimentos de pensamiento y pruebas de concepto, simplemente no generaliza a múltiples argumentos. No lo intentes.

En cuanto a su pregunta principal, esto se resuelve de la manera más elegante con los combinadores de editor semántico de Conal Elliott. Un combinador de editor semántico es una función con un tipo como:

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

Donde F (x) es una expresión que involucra x . También hay " contravariant " combinadores de editor que toman un (b - > a) en su lugar. Intuitivamente, un editor combinator selecciona una parte de un valor mayor para operar. El que necesita se llama resultado :

result = (.)

Observe el tipo de expresión en la que está intentando operar:

a -> a -> Bool

El resultado (codominio) de este tipo es a - > Bool , y el resultado del tipo que es Bool , y eso es a lo que intenta aplicar no . Entonces, para aplicar no al resultado del resultado de una función f , escriba:

(result.result) not f

Esto se generaliza maravillosamente. Aquí hay algunos combinadores más:

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

Entonces, si tiene un valor x de tipo:

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

Y desea aplicar no al Bool, simplemente debe deletrear el camino para llegar allí:

(result.left.result.second) not x

Ah, y si ya has llegado a Functors, te darás cuenta de que fmap es un editor combinador. De hecho, lo anterior se puede deletrear:

(fmap.left.fmap.fmap) not x

Pero creo que es más claro usar los nombres expandidos.

Disfruta.

Answer 2

En realidad, hacer aridades arbitrarias con clases de tipos resulta increíblemente 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 (<)

Gracias por señalar este problema genial. Amo a Haskell.

Answer 3

Tu n combinator se puede escribir:

n = ((not .) .)

En cuanto a tu pregunta de bonificación, la forma típica sería crear varias de estas:

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

etc.

Answer 4

Re: ¿Qué estoy haciendo mal? :

Creo que tu combinador está bien, pero cuando lo vinculas en el nivel superior, una de las molestas "reglas predeterminadas" de Haskell entra en juego y la vinculación no está generalizada:

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

Creo que la restricción de monomorfismo puede verse afectada por la aplicación de clases de tipo. En cualquier caso, si sale del bucle de nivel superior y coloca las cosas en un archivo separado con una firma de tipo explícita, todo funciona bien:

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

Pregunta de bonificación : para hacer esto con más y más parámetros de tipo, puede intentar jugar trucos de escorbuto con el sistema de clase de tipo. Los dos documentos a consultar son el documento sobre QuickCheck y el artículo de Ralf Hinze Genéricos para las masas .