Tablas de verdad de funciones anónimas en Haskell

Question

Estoy tratando de generar una tabla de verdad para una expresión booleana dada. Podría hacer esto con la creación de un nuevo Datatype BoolExpr, pero quiero hacerlo con una función anónima. Se supone que debe funcionar así:

> tTable (\x y -> not (x || y)) 
output: 
F F | T 
F T | F 
T F | F 
T T | F 

Mi enfoque:

tbl p = [(uncurry p) tuple | tuple <- allval] 
     where allval=[(x,y) | x <- [False,True], y <- [False,True]] 

Esto funciona, pero sólo para 2 argumentos. Quiero hacerlo por cualquier cantidad de Argumentos. Así que pensé que iba a hacer una función que toma los argumentos de una lista:

argsFromList f []  = f 
argsFromList f (x:xs) = argsFromList (f x) xs 

Esto no funciona:

Occurs check: cannot construct the infinite type: t = t1 -> t 
    Expected type: t -> [t1] -> t1 -> t 
    Inferred type: (t1 -> t) -> [t1] -> t1 -> t 
In the expression: argsFromList (f x) xs 

No entiendo cuál es el problema aquí. Estaría muy agradecido si alguien pudiera dirigirme en la dirección correcta o publicar un enlace que sí lo haga.

Answer 1

El problema aquí es que está intentando llamar a una función recursivamente con un tipo diferente para el paso recursivo. Considere la definición:

argsFromList f []  = f 
argsFromList f (x:xs) = argsFromList (f x) xs 

Tratemos de inferir el tipo nosotros mismos. Podemos ver inmediatamente que el primer argumento f debe ser una función de al menos un argumento, el segundo argumento (x:xs) es una lista, y los elementos de lista deben ser del mismo tipo que el primer argumento de f. En el primer caso, se devuelve el argumento f, por lo que el tipo de devolución final debe ser el mismo que el del primer argumento. Así que empezamos con esto:

argsFromList :: (a -> ?) -> [a] -> (a -> ?) 

Para encontrar el tipo desconocido ?, podemos ver el segundo caso, que consiste en una llamada recursiva. El argumento xs es el mismo tipo de lista, y el argumento (f x) tiene el tipo ?. Dado que se está utilizando como el primer argumento en la llamada recursiva, que tiene el tipo (a -> ?), ahora podemos concluir que ? es del mismo tipo que (a -> ?) que es por lo tanto del mismo tipo que (a -> (a -> ?)) que es por lo tanto el mismo tipo que (a -> (a -> (a -> ?))) que es .. ¡Uy!

Ese sería el "tipo infinito", por supuesto.

Si desea hacer esto con funciones que usan una cantidad variable de argumentos de un solo tipo, probablemente querrá usar funciones que tomen una lista de valores en lugar de argumentos individuales. De lo contrario, tendrá que escribir cada versión individualmente o utilizar algunos trucos arcanos que implican características avanzadas del lenguaje, ninguno de los cuales es atractivo en un caso simple como este.

Answer 2

Si usted quiere construir una tabla de verdad para las funciones booleanas con un número arbitrario de argumentos, que está creando una función que debe trabajar para varios tipos, por lo que tendrá que usar el tipo clases:

{-# LANGUAGE FlexibleInstances #-} 

class TruthTable a where 
    truthTable :: a -> [([Bool], Bool)] 

instance TruthTable Bool where 
    truthTable b = [([], b)] 

instance TruthTable a => TruthTable (Bool -> a) where 
    truthTable f = [ (True : inps, out) | (inps, out) <- truthTable (f True)] ++ 
       [ (False : inps, out) | (inps, out) <- truthTable (f False)] 

por ejemplo:

*Main> mapM_ print $ truthTable (&&) 
([True,True],True) 
([True,False],False) 
([False,True],False) 
([False,False],False) 

Answer 3

Lo que estamos pidiendo es para nada trivial. Haskell no facilita el tratamiento de funciones que aplican funciones con números variables de argumentos.Por ejemplo, el zip functions from Data.List viene en variantes separadas para diferentes números de argumentos (zip, zip3, zip4, ...). Del mismo modo, en Control.Monad hay liftM, liftM2, liftM3, ...

Básicamente, el tipo más general, se puede asignar a una función con un número indeterminado de argumentos es a -> b; una función de verdad de un lugar es Bool -> Bool (a = Bool, b = Bool), una función de verdad de dos lugar es Bool -> (Bool -> Bool) (a = Bool, b = Bool -> Bool), de tres lugar es Bool -> (Bool -> (Bool -> Bool)) (a = Bool, b = Bool -> (Bool -> Bool)) , y así. Pero no hay una manera fácil de mirar la función que se le ha pasado para saber cuál es el tipo a la derecha de la flecha inicial.

Un tipo de solución que se puede hacer funcionar implica el uso de clases de tipos para definir instancias separadas de la función de fabricante de tabla de verdad para cada tipo de función de argumento. La respuesta de Sjoerd Visscher en este hilo lo está haciendo para todos los tamaños de función mediante el uso de una definición de instancia recursiva (observe la recursiva declaración TruthTable a => TruthTable (Bool -> a)). Puede haber otras soluciones que podrían construirse utilizando la clase de tipo Applicative.