En Haskell ¿cómo puedo tomar un predicado m-ary y un predicado n-ary y construir un predicado (m + n) -ary?

Question

Hoy jugué con el uso de clases de tipos para construir inductivamente funciones de un predicado de cualquier aridad tomando como entradas cualquier combinación de cualquier tipo, que devuelva otros predicados del mismo tipo pero con alguna operación básica aplicada. Por ejemplo

conjunction (>2) even 

volvería un predicado que se evalúa como verdadera, incluso para un número mayor de dos y

conjunction (>=) (<=) 

volvería =

Todo esto está muy bien, tiene esa parte de trabajo, pero Planteó la pregunta, ¿qué pasaría si quisiera definir la conjunción de dos predicados como un predicado que toma una entrada para cada entrada de cada predicado combinado? Por ejemplo:

:t conjunction (>) not 

devolvería Ord a => a -> a -> Bool -> Bool. Se puede hacer esto? ¿Si es así, cómo?

Answer 1

Necesitaremos TypeFamilies para esta solución.

{-# LANGUAGE TypeFamilies #-} 

La idea es definir una clase Pred de predicados n-arias:

class Pred a where 
    type Arg a k :: * 
    split :: a -> (Bool -> r) -> Arg a r 

El problema tiene que ver con los argumentos volver a barajar a los predicados, así que esto es lo que la clase tiene como objetivo hacer . El tipo asociado Arg se supone para dar acceso a los argumentos de un predicado n-ary mediante la sustitución de la final Bool con k, así que si tenemos un tipo

X = arg1 -> arg2 -> ... -> argn -> Bool 

entonces

Arg X k = arg1 -> arg2 -> ... -> argn -> k 

Esto permitirá nosotros para construir el tipo de resultado correcto de conjunction donde se deben recopilar todos los argumentos de los dos predicados.

La función split toma un predicado de tipo a y una continuación de tipo Bool -> r y producirá algo de tipo Arg a r. La idea de split es que si sabemos qué hacer con el Bool que obtenemos del predicado al final, entonces podemos hacer otras cosas (r) en el medio.

No es de extrañar, necesitaremos dos casos, uno para Bool y otro para las funciones para las que el destino ya es un predicado:

instance Pred Bool where 
    type Arg Bool k = k 
    split b k = k b 

Un Bool no tiene argumentos, por lo Arg Bool k simplemente devuelve k.Además, para split, ya tenemos Bool, por lo que podemos aplicar inmediatamente la continuación.

instance Pred r => Pred (a -> r) where 
    type Arg (a -> r) k = a -> Arg r k 
    split f k x = split (f x) k 

Si tenemos un predicado de tipo a -> r, entonces Arg (a -> r) k debe comenzar con a ->, y seguimos llamando Arg recursivamente en r. Para split, ahora podemos tomar tres argumentos, el x es del tipo a. Podemos alimentar x a f y luego llamar al split en el resultado.

Una vez que hemos definido la clase Pred, es fácil definir conjunction:

conjunction :: (Pred a, Pred b) => a -> b -> Arg a (Arg b Bool) 
conjunction x y = split x (\ xb -> split y (\ yb -> xb && yb)) 

la función toma dos predicados y devuelve algo del tipo Arg a (Arg b Bool). Veamos el ejemplo:

> :t conjunction (>) not 
conjunction (>) not 
    :: Ord a => Arg (a -> a -> Bool) (Arg (Bool -> Bool) Bool) 

GHCi no expande este tipo, pero podemos. El tipo es equivalente a

Ord a => a -> a -> Bool -> Bool 

que es exactamente lo que queremos. Podemos probar una serie de ejemplos, también:

> conjunction (>) not 4 2 False 
True 
> conjunction (>) not 4 2 True 
False 
> conjunction (>) not 2 2 False 
False 

Tenga en cuenta que el uso de la clase Pred, es trivial para escribir otras funciones (como disjunction), también.

Answer 2

{-# LANGUAGE TypeFamilies #-} 

class RightConjunct b where 
    rconj :: Bool -> b -> b 

instance RightConjunct Bool where 
    rconj = (&&) 

instance RightConjunct b => RightConjunct (c -> b) where 
    rconj b f = \x -> b `rconj` f x 

class LeftConjunct a where 
    type Ret a b 
    lconj :: RightConjunct b => a -> b -> Ret a b 

instance LeftConjunct Bool where 
    type Ret Bool b = b 
    lconj = rconj 

instance LeftConjunct a => LeftConjunct (c -> a) where 
    type Ret (c -> a) b = c -> Ret a b 
    lconj f y = \x -> f x `lconj` y 

conjunction :: (LeftConjunct a, RightConjunct b) => a -> b -> Ret a b 
conjunction = lconj 

Espero que se explique por sí mismo, pero si no, no dude en hacer preguntas.

Además, podría fusionar las dos clases en una, por supuesto, pero creo que las dos clases hacen que la idea sea más clara.