tipos - Cómo escribir una función Haskell que toma una función variada como argumento

sintaxis basica de haskell

Question

Intento crear una función que tenga una función variada como argumento , es decir,

func :: (a -> ... -> a) -> a

¿Cómo puedo lograr esto?

He leído sobre las funciones polivariadicas y estoy seguro de que Oleg ya lo hizo , sin embargo, estoy perdido tratando de aplicar el patrón en una función con una función variada como argumento. Especialmente el enfoque de Olegs parece funcionar solo con las extensiones de glasgow y quiero que la solución funcione en Haskell 98 puro (como Text.Printf hace Text.Printf ).

La razón por la que pregunto es que estoy tratando de construir una función que tome una función booleana como argumento y verifique si es una tautología, es decir,

isTautology :: (Bool -> ... -> Bool) -> Bool

para que uno pueda escribir:

isTautology (/x -> x && not x)
isTautology (/x y -> x && y || not y)

Mi problema es que sigo leyendo que el truco fue hacer que el tipo de devolución sea una variable de tipo (para que pueda ser el resultado u otra función), pero mi tipo de devolución es fijo (Bool).

Answer 1

El truco consiste en crear una clase de tipo para la cual definirá una instancia para las funciones y una instancia para el tipo de devolución. El hecho de que sea un Bool no es un problema en absoluto.

Estamos intentando escribir una función que toma un argumento variado y devuelve un Bool , por lo que definiremos una clase de tipo con dicha función.

class Stmt a where
    tautology :: a -> Bool

A continuación, definimos una instancia para el tipo de retorno de la función variadic. En este caso, ese es Bool .

-- A Bool is a tautology if it''s True.
instance Stmt Bool where
    tautology = id

La parte clave es la siguiente instancia para las funciones que toman un argumento Bool , y cuyo tipo de devolución es de algún tipo de nuestra clase. De esta forma, esta instancia se aplicará varias veces si una función toma múltiples argumentos.

-- A function is a tautology if it always returns a tautology.
instance Stmt b => Stmt (Bool -> b) where
    tautology f = tautology (f True) && tautology (f False)

Escribirlo de esta manera requiere FlexibleInstances debido a Bool en la segunda instancia. Para hacer lo mismo con Haskell 98 puro, tendremos que usar una variable de tipo con restricciones adecuadas en su lugar. Podemos, por ejemplo, usar Bounded y Enum (hay instancias para ambos para Bool ), o puede crear su propia clase que le permita construir las entradas apropiadas.

instance (Enum a, Bounded a, Stmt b) => Stmt (a -> b) where
    tautology f = all (tautology . f) [minBound .. maxBound]

Y terminamos. Probémoslo:

> tautology $ /x y -> (not x && not y) == not (x && y)
False
> tautology $ /x y -> (not x && not y) == not (x || y)
True