¿Por qué no hay una clase de tipo para funciones?

En un problema de aprendizaje con el que he estado jugando, me di cuenta de que necesitaba una clase de tipo para funciones con operaciones para aplicar, componer, etc. Razones ...

1. Puede ser conveniente tratar una representación de una función como si fuera la función misma, de modo que al aplicar la función implícitamente se usa un intérprete, y componer funciones deriva una nueva descripción.

2. Una vez que tenga una clase de tipos para funciones, puede tener clases de tipos derivadas para tipos especiales de funciones; en mi caso, quiero funciones invertibles.

Por ejemplo, las funciones que aplican desplazamientos de enteros podrían representarse mediante un ADT que contenga un entero. Aplicar esas funciones solo significa agregar el número entero. La composición se implementa agregando los enteros envueltos. La función inversa tiene el entero negado. La función de identidad envuelve cero. La función constante no se puede proporcionar porque no hay una representación adecuada para ella.

Por supuesto, no necesita deletrear las cosas como si los valores fueran funciones genuinas de Haskell, pero una vez que tuve la idea, pensé que ya debía existir una biblioteca como esa y tal vez incluso usar las ortografías estándar. Pero no puedo encontrar una clase de este tipo en la biblioteca de Haskell.

Encontré el módulo Data.Function , pero no hay una clase de tipos, solo algunas funciones comunes que también están disponibles en Prelude.

Entonces, ¿por qué no hay una clase de tipo para las funciones? ¿Es "solo porque no la hay" o "porque no es tan útil como crees"? ¿O tal vez hay un problema fundamental con la idea?

El mayor problema posible en el que he pensado hasta ahora es que la aplicación de la función en funciones reales probablemente tendría que estar cubierta especialmente por el compilador para evitar un problema de bucle: para aplicar esta función, necesito aplicar la función de aplicación de la función, y para hacer eso necesito llamar a la función de aplicación de función, y para hacer eso ...

Más pistas

Código de ejemplo para mostrar lo que busco ...

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}

--  In my first version, Doable only had the one argument f. This version
--  seemed to be needed to support the UndoableOffset type.
--
--  It seems to work, but it also seems strange. In particular,
--  the composition function - a and b are in the class, but c isn't,
--  yet there's nothing special about c compared with a and b.
class Doable f a b where
  fwdApply :: f a b -> a -> b
  compDoable :: f b c -> f a b -> f a c

--  In the first version, I only needed a constraint for
--  Doable f a b, but either version makes sense.
class (Doable f a b, Doable f b a) => Undoable f a b where
  bwd      :: f a b -> f b a

  bwdApply :: f a b -> b -> a
  bwdApply f b = fwdApply (bwd f) b

--  Original ADT - just making sure I could wrap a pair of functions
--  and there were no really daft mistakes.
data UndoableFn a b = UFN { getFwd :: a -> b, getBwd :: b -> a }

instance Doable UndoableFn a b where
  fwdApply = getFwd
  compDoable f g = UFN ((getFwd f) . (getFwd g)) ((getBwd g) . (getBwd f))

instance Undoable UndoableFn a b where
  bwd f    = UFN (getBwd f) (getFwd f)
  bwdApply = getBwd

--  Making this one work led to all the extensions. This representation
--  can only represent certain functions. I seem to need the typeclass
--  arguments, but also to need to restrict which cases can happen, hence
--  the GADT. A GADT with only one constructor still seems odd. Perhaps
--  surprisingly, this type isn't just a toy (except that the whole thing's
--  a toy really) - it's one real case I need for the exercise. Still a
--  simple special case though.
data UndoableOffset a b where
  UOFF :: Int -> UndoableOffset Int Int

instance Doable UndoableOffset Int Int where
  fwdApply (UOFF x) y = y+x
  compDoable (UOFF x) (UOFF y) = UOFF (x+y)

instance Undoable UndoableOffset Int Int where
  bwdApply (UOFF x) y = y-x
  bwd (UOFF x) = UOFF (-x)

--  Some value-constructing functions
--  (-x) isn't shorthand for subtraction - whoops.
undoableAdd :: Int -> UndoableFn Int Int
undoableAdd x = UFN (+x) (\y -> y-x)

undoableMul :: Int -> UndoableFn Int Int
undoableMul x = UFN (*x) (`div` x)

--  With UndoableFn, it's possible to define an invertible function
--  that isn't invertible - to break the laws. To prevent that, need
--  the UFN constructor to be private (and all public ops to preserve
--  the laws). undoableMul is already not always invertible.
validate :: Undoable f a b => Eq a => f a b -> a -> Bool
validate f x = (bwdApply f (fwdApply f x)) == x

--  Validating a multiply-by-zero invertible function shows the flaw
--  in the validate-function plan. Must try harder.
main = do putStrLn . show $ validate (undoableAdd 3) 5
          putStrLn . show $ validate (undoableMul 3) 5
          --putStrLn . show $ validate (undoableMul 0) 5
          fb1 <- return $ UOFF 5
          fb2 <- return $ UOFF 7
          fb3 <- return $ compDoable fb1 fb2
          putStrLn $ "fwdApply fb1  3 = " ++ (show $ fwdApply fb1  3)
          putStrLn $ "bwdApply fb1  8 = " ++ (show $ bwdApply fb1  8)
          putStrLn $ "fwdApply fb3  2 = " ++ (show $ fwdApply fb3  2)
          putStrLn $ "bwdApply fb3 14 = " ++ (show $ bwdApply fb3 14)

La aplicación implica un tipo de unificación donde los valores unificados no son iguales, sino que están relacionados a través de esas funciones invertibles: lógica de estilo Prolog pero con a = f(b)restricciones en lugar de a = b. La mayor parte de la composición resultará de la optimización de una estructura de búsqueda de unión. La necesidad de inversas debería ser obvia.

Si ningún elemento en un conjunto unificado tiene un valor exacto, entonces un elemento en particular solo puede cuantificarse en relación con otro elemento en ese conjunto unificado. Es por eso que no quiero usar funciones "reales": calcular esos valores relativos. Podría eliminar todo el aspecto de la función y solo tener cantidades absolutas y relativas, probablemente solo necesito números / vectores y (+), pero mi astronauta de arquitectura interior quiere su diversión.

La única forma en que vuelvo a separar los enlaces es a través del retroceso, y todo es puro: la búsqueda de unión se realizará utilizando las teclas IntMapcomo "punteros". Tengo un simple trabajo de búsqueda de unión, pero como todavía no he agregado las funciones invertibles, no tiene sentido enumerarlo aquí.

Razones por las que no puedo usar Aplicativo, Mónada, Flecha, etc.

Las operaciones principales que necesito que proporcione la clase de abstracción de funciones son la aplicación y la composición. Eso suena familiar, por ejemplo Applicative (<*>), Monad (>>=)y Arrow (>>>)todas son funciones de composición. Sin embargo, los tipos que implementan la abstracción de funciones en mi caso contendrán cierta estructura de datos que representa una función, pero que no es (y no puede contener) una función, y que solo puede representar un conjunto limitado de funciones.

Como mencioné en la explicación del código, a veces solo puedo cuantificar un elemento en relación con otro porque ningún elemento en un grupo "unificado" tiene un valor exacto. Quiero poder derivar una representación de esa función, que en general será la composición de varias funciones proporcionadas (caminar hacia un ancestro común en el árbol de unión / búsqueda) y de varias funciones inversas (caminar de regreso a la otra articulo).

Caso simple - donde las "funciones" originales están limitadas a "funciones" de desplazamiento de enteros, quiero que el resultado compuesto sea una "función" de desplazamiento de enteros - agregue las compensaciones de componentes. Esa es una gran parte de por qué la función de composición debe estar en la clase, así como la función de aplicación.

Esto significa que no puedo proporcionar las operaciones pure, returno arrpara mis tipos, por lo que no puedo usar Applicative, Monado Arrow.

Este no es un fracaso de esos tipos, es una falta de coincidencia de abstracciones. La abstracción que quiero es de una simple función pura. No hay efectos secundarios, por ejemplo, y no es necesario crear una notación conveniente para secuenciar y componer las funciones que no sean un equivalente del estándar (.) Que se aplica a todas las funciones.

Yo podría instanciar Category. Estoy seguro de que todas mis cosas funcionales podrán proporcionar una identidad, aunque probablemente no la necesite. Pero como Categoryno es compatible con la aplicación, de todos modos aún necesitaría una clase derivada para agregar esa operación.

Bueno, no conozco ninguna idea horneada que se promocione a sí misma como representación de cosas "funcionales". Pero hay varios que se acercan

Categorias

Si tiene un concepto de función simple que tiene identidades y composición, entonces tiene una categoría.

class Category c where
  id :: c a a
  (.) :: c b c -> c a b -> c a c

La desventaja es que no se puede crear un buen ejemplo categoría con un conjunto de objetos ( a, by c). Puede crear una clase de categoría personalizada, supongo.

Flechas

Si sus funciones tienen una noción de productos y pueden inyectar funciones arbitrarias, entonces las flechas son para usted

 class Arrow a where
   arr :: (b -> c) -> a b c
   first :: a b c -> a (b, d) (c, d)
   second :: a b c -> a (d, b) (d, c)

ArrowApply tiene una noción de aplicación que parece importante para lo que quieres.

Solicitantes

Los solicitantes tienen su noción de aplicación, los he usado en un AST para representar la aplicación de funciones.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f b -> f c

Hay muchas otras ideas. Pero un tema común es construir una estructura de datos que represente su función, y luego pasarla a una función de interpretación.

Esto también cuántas mónadas libres funcionan. Sugeriría hurgar en estos si te sientes valiente, son una herramienta poderosa para las cosas que estás sugiriendo y esencialmente te permiten construir una estructura de datos usando la donotación y luego colapsarla en un cálculo de efectos secundarios con diferentes funciones . Pero la belleza es que estas funciones solo operan en la estructura de datos, y no son realmente conscientes de cómo lo hizo todo. Esto es lo que sugeriría para su ejemplo de intérprete.

Como señala, el principal problema con el uso de aplicativo aquí es que no hay una definición sensata para pure. Por lo tanto, Applyfue inventado. Al menos, así lo entiendo.

Desafortunadamente, no tengo ejemplos disponibles de instancias de Applyeso que tampoco lo son Applicative. Se afirma que esto es cierto IntMap, pero no tengo idea de por qué. Del mismo modo, no sé si su ejemplo, enteros compensados, admite una Applyinstancia.

Además de la mencionada Category, Arrowy Applicative:

También descubrí Data.Lambdapor Conal Elliott:

Algunas clases de funciones, que tienen una construcción tipo lambda

Parece interesante, por supuesto, pero difícil de entender sin ejemplos ...

Ejemplos

Se pueden encontrar ejemplos en la página wiki sobre valores tangibles (TV) que parecen ser una de las cosas que causaron la creación de la TypeComposebiblioteca; ver Entradas y salidas con valores de función .

La idea de la biblioteca de TV es mostrar los valores de Haskell (incluidas las funciones) de manera tangible.

Para seguir la regla de StackOverflow sobre no publicar lonks desnudos, copio algunos bits a continuación que deberían dar la idea de estas cosas:

El primer ejemplo dice:

apples, bananas :: CInput Int
apples  = iTitle "apples"  defaultIn
bananas = iTitle "bananas" defaultIn

shoppingO :: COutput (Int -> Int -> Int)
shoppingO = oTitle "shopping list" $
            oLambda apples (oLambda bananas total)

shopping :: CTV (Int -> Int -> Int)
shopping = tv shoppingO (+)

que da cuando se ejecuta como runIO shopping(ver más comentarios, GUI y más ejemplos):

shopping list: apples: 8
bananas: 5
total: 13