function - que - how to put hashtags on youtube videos

¿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 una función que ajuste esta función con no.

por ejemplo, hacer funcionar de esta manera

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

Puedo hacer combinator 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 una pregunta adicional 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 quieras piratear con clases de tipos, lo cual es mejor dejar para experimentos de pensamiento y prueba de concepto, simplemente no generalizar a múltiples argumentos. No intentes.

En cuanto a su pregunta principal, esto se soluciona de forma 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 combinadores de editor "contravariantes" que toman un (b -> a) lugar. Intuitivamente, un combinador de editor selecciona una parte de un valor mayor para operar. El que necesita se llama result :

result = (.)

Mira el tipo de expresión con la que intentas operar:

a -> a -> Bool

El resultado (codomain) de este tipo es a -> Bool , y el resultado de ese tipo es Bool , y eso es a lo que intentas aplicar not . Entonces, para aplicar not al resultado del resultado de una función f , usted escribe:

(result.result) not f

Esto bellamente generaliza. Aquí hay algunos más 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
...

Entonces, si tiene un valor x de tipo:

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

Y si quieres postularte not al Bool, solo debes deletrear el camino para llegar allí:

(result.left.result.second) not x

Ah, y si ya has hablado con Functors, notarás que fmap es un editor combinador. De hecho, lo anterior se puede escribir:

(fmap.left.fmap.fmap) not x

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

Disfrutar.

Answer 2

En realidad, hacer aria arbitraria 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 genial problema. Amo a Haskell.

Answer 3

Re: ¿Qué estoy haciendo mal? :

Creo que su combinador está bien, pero cuando lo dejas en el nivel superior, entra en juego una de las molestas ''reglas predeterminadas'' de Haskell y el enlace no se generaliza:

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

Creo que es posible que la "restricción de monomorfismo" te afecte en lo que respecta a las 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 escándalo con el sistema de tipo de clase. Dos documentos para consultar son el trabajo de Hughes y Claessen sobre QuickCheck y el artículo de Ralf Hinze, Generics for the Masses .

Answer 4

Su n combinador puede escribirse:

n = ((not .) .)

En cuanto a su pregunta de bonificación, la forma típica sería crear varios de estos:

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

etc.