Pourquoi n'y a-t-il pas de classe de types pour les fonctions?

Dans un problème d'apprentissage avec lequel je me suis amusé, j'ai réalisé que j'avais besoin d'une classe de types pour les fonctions avec des opérations d'application, de composition, etc. Raisons ...

1. Il peut être pratique de traiter une représentation d'une fonction comme si c'était la fonction elle-même, de sorte que l'application de la fonction utilise implicitement un interpréteur et que la composition des fonctions dérive une nouvelle description.

2. Une fois que vous avez une classe de types pour les fonctions, vous pouvez avoir des classes de types dérivées pour des types spéciaux de fonctions - dans mon cas, je veux des fonctions inversibles.

Par exemple, les fonctions qui appliquent des décalages entiers peuvent être représentées par un ADT contenant un entier. Appliquer ces fonctions signifie simplement ajouter l'entier. La composition est implémentée en ajoutant les entiers enveloppés. La fonction inverse a l'entier nié. La fonction d'identité encapsule zéro. La fonction constante ne peut pas être fournie car il n'y a pas de représentation appropriée pour elle.

Bien sûr, il n'est pas nécessaire d'épeler les choses comme si les valeurs étaient de véritables fonctions Haskell, mais une fois que j'ai eu l'idée, j'ai pensé qu'une bibliothèque comme celle-ci devait déjà exister et peut-être même utiliser l'orthographe standard. Mais je ne trouve pas une telle classe de types dans la bibliothèque Haskell.

J'ai trouvé le module Data.Function , mais il n'y a pas de classe de types - juste quelques fonctions communes qui sont également disponibles à partir du Prelude.

Alors - pourquoi n'y a-t-il pas de classe de types pour les fonctions? Est-ce «simplement parce qu'il n'y en a pas» ou «parce que ce n'est pas aussi utile que vous le pensez»? Ou peut-être qu'il y a un problème fondamental avec l'idée?

Le plus gros problème possible auquel j'ai pensé jusqu'à présent est que l'application de fonction sur les fonctions réelles devrait probablement être placée dans un boîtier spécial par le compilateur pour éviter un problème de boucle - pour appliquer cette fonction, je dois appliquer la fonction d'application de fonction, et pour ce faire, je dois appeler la fonction application fonction, et pour ce faire ...

Plus d'indices

Exemple de code pour montrer ce que je vise ...

{-# 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)

L'application implique une sorte d'unification où les valeurs unifiées ne sont pas égales, mais sont liées via ces fonctions inversibles - logique de style Prolog mais avec des a = f(b)contraintes plutôt que a = b. La majeure partie de la composition résultera de l'optimisation d'une structure de recherche d'union. Le besoin d'inverses devrait être évident.

Si aucun élément d'un ensemble unifié n'a une valeur exacte, un élément particulier ne peut être quantifié que par rapport à un autre élément de cet ensemble unifié. C'est pourquoi je ne veux pas utiliser de "vraies" fonctions - calculer ces valeurs relatives. Je pourrais supprimer tout l'aspect fonctionnel et avoir juste des quantités absolues et relatives - je n'ai probablement besoin que de nombres / vecteurs et (+)- mais mon astronaute d'architecture intérieure veut son plaisir.

La seule façon de briser à nouveau les liens est de revenir en arrière, et tout est pur - la recherche d'union se fera à l'aide de clés en tant IntMapque "pointeurs". J'ai un simple travail de recherche d'union, mais comme je n'ai pas encore ajouté les fonctions inversibles, il est inutile de le lister ici.

Raisons pour lesquelles je ne peux pas utiliser Applicative, Monad, Arrow, etc.

Les principales opérations que j'ai besoin de la classe d'abstraction de fonctions à fournir sont l'application et la composition. Familiers que les sons - par exemple le Applicative (<*>), Monad (>>=)et Arrow (>>>)sont toutes les fonctions de composition. Cependant, les types qui implémentent l'abstraction de fonction dans mon cas contiendront une structure de données qui représente une fonction, mais qui n'est pas (et ne peut pas contenir) une fonction, et qui ne peut représenter qu'un ensemble limité de fonctions.

Comme je l'ai mentionné dans l'explication du code, parfois je ne peux quantifier qu'un élément par rapport à un autre car aucun élément dans un cluster "unifié" n'a une valeur exacte. Je veux pouvoir dériver une représentation de cette fonction, qui sera en général la composition de plusieurs fonctions fournies (remonter vers un ancêtre commun dans l'arbre d'union / trouver) et de plusieurs fonctions inverses (redescendre vers l'autre article).

Cas simple - où les "fonctions" originales sont limitées aux "fonctions" à décalage entier, je veux que le résultat composé soit une "fonction" à décalage entier - ajoutez les décalages des composants. C'est une grande partie de la raison pour laquelle la fonction de composition doit être dans la classe ainsi que la fonction d'application.

Cela signifie que je ne peux pas fournir les opérations pure, returnou arrpour mes types, donc je ne peux pas utiliser Applicative, Monadou Arrow.

Ce n'est pas un échec de ces types - c'est un décalage d'abstractions. L'abstraction que je veux est d'une simple fonction pure. Il n'y a pas d'effet secondaire, par exemple, et pas besoin de construire une notation pratique pour séquencer et composer les fonctions autres qu'un équivalent de la norme (.) Qui s'applique à toutes les fonctions.

Je pourrais par exemple Category. Je suis convaincu que toutes mes choses fonctionnelles pourront fournir une identité, même si je n'en ai probablement pas besoin. Mais comme Categoryne prend pas en charge l'application, j'aurais quand même besoin d'une classe dérivée pour ajouter cette opération.

Eh bien, je ne connais aucune idée cuite qui se présente comme représentant des choses "fonctionnelles". Mais il y en a plusieurs qui se rapprochent

Les catégories

Si vous avez un concept de fonction simple qui a des identités et une composition, vous avez une catégorie.

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

L'inconvénient est que vous ne pouvez pas créer une belle instance de catégorie avec un ensemble d'objets ( a, bet c). Vous pouvez créer une classe de catégorie personnalisée, je suppose.

Flèches

Si vos fonctions ont une notion de produits et peuvent injecter des fonctions arbitraires, alors les flèches sont pour vous

 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 a une notion d'application qui semble importante pour ce que vous voulez.

Candidats

Les candidats ont votre notion d'application, je les ai utilisés dans un AST pour représenter une application de fonction.

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

Il existe de nombreuses autres idées. Mais un thème commun est de construire une structure de données représentant votre fonction et de la transmettre à une fonction d'interprétation.

C'est aussi le nombre de monades gratuites qui fonctionnent. Je suggérerais de les fouiller si vous vous sentez courageux, ils sont un outil puissant pour les choses que vous proposez et vous permettent essentiellement de construire une structure de données à l'aide de la donotation, puis de la réduire en un calcul à effet secondaire avec différentes fonctions . Mais la beauté est que ces fonctions fonctionnent uniquement sur la structure de données, et ne sont pas vraiment au courant de la façon dont vous avez fait tout cela. C'est ce que je suggérerais pour votre exemple d'interprète.

Comme vous le faites remarquer, le principal problème avec l'utilisation d'Applatif ici est qu'il n'y a pas de définition sensée pour pure. Par conséquent, a Applyété inventé. C'est du moins ce que je comprends.

Malheureusement, je n'ai pas d'exemples en main Applyqui ne le soient pas également Applicative. On prétend que cela est vrai IntMap, mais je ne sais pas pourquoi. De même, je ne sais pas si votre exemple - les entiers de décalage - admet une Applyinstance.

En plus du mentionné Category, Arrowet Applicative:

J'ai également découvert Data.Lambdapar Conal Elliott:

Certaines classes fonctionnelles, ayant une construction de type lambda

Semble intéressant, bien sûr, mais difficile à comprendre sans exemples ...

Exemples

Des exemples peuvent être trouvés dans la page wiki sur les valeurs tangibles (TV) qui semblent être l'une des causes de la création de la TypeComposebibliothèque; voir Entrées et sorties fonctionnelles .

L'idée de la bibliothèque TV est d'afficher les valeurs Haskell (y compris les fonctions) de manière tangible.

Pour suivre la règle StackOverflow de ne pas publier de lonks nus, je copie quelques bits ci-dessous qui devraient donner l'idée de ces choses:

Le premier exemple se lit comme suit:

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 (+)

ce qui donne lorsqu'il est exécuté en tant que runIO shopping(voir ici pour plus de commentaires, d'interfaces graphiques et plus d'exemples):

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