Warum gibt es keine Typenklasse für Funktionen?

17

In einem Lernproblem, mit dem ich herumgespielt habe, wurde mir klar, dass ich eine Typenklasse für Funktionen mit Operationen zum Anwenden, Komponieren usw. benötige. Gründe ...

  1. Es kann praktisch sein, eine Darstellung einer Funktion so zu behandeln, als wäre sie die Funktion selbst, sodass bei der impliziten Anwendung der Funktion ein Interpreter verwendet wird und beim Erstellen von Funktionen eine neue Beschreibung abgeleitet wird.

  2. Sobald Sie eine Typklasse für Funktionen haben, können Sie Typklassen für spezielle Arten von Funktionen ableiten - in meinem Fall möchte ich invertierbare Funktionen.

Zum Beispiel könnten Funktionen, die Ganzzahl-Offsets anwenden, durch ein ADT dargestellt werden, das eine Ganzzahl enthält. Das Anwenden dieser Funktionen bedeutet lediglich das Hinzufügen der Ganzzahl. Die Komposition wird durch Hinzufügen der umbrochenen ganzen Zahlen implementiert. Bei der Umkehrfunktion ist die Ganzzahl negiert. Die Identitätsfunktion umschließt Null. Die konstante Funktion kann nicht bereitgestellt werden, da keine geeignete Darstellung dafür vorhanden ist.

Natürlich muss es nicht so geschrieben werden, als ob es sich bei den Werten um echte Haskell-Funktionen handelt, aber als ich auf die Idee kam, dachte ich, dass eine solche Bibliothek bereits existieren muss und vielleicht sogar die Standardschreibweisen verwendet. Aber ich kann eine solche Typenklasse nicht in der Haskell-Bibliothek finden.

Ich habe das Modul Data.Function gefunden , aber es gibt keine Typenklasse - nur einige allgemeine Funktionen, die auch im Prelude verfügbar sind.

Also - warum gibt es keine Typenklasse für Funktionen? Ist es "nur weil es keine gibt" oder "weil es nicht so nützlich ist, wie du denkst"? Oder gibt es ein grundsätzliches Problem mit der Idee?

Das größtmögliche Problem, an das ich bisher gedacht habe, ist, dass die Funktionsanwendung für tatsächliche Funktionen vom Compiler möglicherweise speziell behandelt werden muss, um ein Schleifenproblem zu vermeiden. Um diese Funktion anzuwenden, muss die Funktion application function angewendet werden. und um das zu tun, muss ich die Funktion application function aufrufen, und um das zu tun ...

Weitere Hinweise

Beispielcode, um zu zeigen, was ich anstrebe ...

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

Die Anwendung beinhaltet eine Art Vereinheitlichung, bei der vereinheitlichte Werte nicht gleich sind, sondern über diese invertierbaren Funktionen in Beziehung gesetzt werden - Logik im Prolog-Stil, jedoch mit a = f(b)Einschränkungen anstatt a = b. Der größte Teil der Komposition ergibt sich aus der Optimierung einer Union-Find-Struktur. Die Notwendigkeit von Inversen sollte offensichtlich sein.

Wenn kein Element in einer einheitlichen Menge einen genauen Wert hat, kann ein bestimmtes Element nur relativ zu einem anderen Element in dieser einheitlichen Menge quantifiziert werden. Deshalb möchte ich keine "echten" Funktionen verwenden - diese relativen Werte berechnen. Ich könnte den gesamten Funktionsaspekt weglassen und nur absolute und relative Größen haben - ich benötige wahrscheinlich nur Zahlen / Vektoren und (+)- aber mein Astronaut in der inneren Architektur möchte, dass er Spaß hat.

Der einzige Weg, wie ich die Links wieder auseinander bringe, ist das Backtracking, und alles ist rein - das Auffinden von Gewerkschaften erfolgt mit Schlüsseln in einem IntMapals "Zeiger". Ich habe eine einfache Gewerkschaftsfunktion, aber da ich die umkehrbaren Funktionen noch nicht hinzugefügt habe, hat es keinen Sinn, sie hier aufzulisten.

Gründe, warum ich Applicative, Monad, Arrow usw. Nicht verwenden kann

Die Hauptoperationen, für die ich die Funktionsabstraktionsklasse benötige, sind Anwendung und Komposition. Das klingt vertraut - zum Beispiel der Applicative (<*>), Monad (>>=)und Arrow (>>>)sind all Zusammensetzung Funktionen. Die Typen, die in meinem Fall die Funktionsabstraktion implementieren, enthalten jedoch eine Datenstruktur, die eine Funktion darstellt, die jedoch keine Funktion ist (und nicht enthalten kann) und die nur einen begrenzten Satz von Funktionen darstellen kann.

Wie ich in der Erklärung des Codes erwähnt habe, kann ich manchmal nur ein Element relativ zu einem anderen quantifizieren, da kein Element in einem "einheitlichen" Cluster einen genauen Wert hat. Ich möchte in der Lage sein, eine Darstellung dieser Funktion abzuleiten, bei der es sich im Allgemeinen um die Zusammensetzung mehrerer bereitgestellter Funktionen (Heraufgehen auf einen gemeinsamen Vorfahren im Vereinigungs- / Suchbaum) und mehrerer umgekehrter Funktionen (Herabgehen auf den anderen) handelt Artikel).

Einfacher Fall - wo die ursprünglichen "Funktionen" auf Ganzzahloffset "Funktionen" beschränkt sind, möchte ich das zusammengesetzte Ergebnis als Ganzzahloffset "Funktion" - fügen Sie die Komponentenoffsets hinzu. Dies ist ein wesentlicher Grund, warum die Kompositionsfunktion sowohl in der Klasse als auch in der Anwendungsfunktion enthalten sein muss.

Dieses Mittel kann ich die Operationen nicht zur Verfügung stellen pure, returnoder arrfür meine Art, so dass ich nicht verwenden können Applicative, Monadoder Arrow.

Dies ist kein Misserfolg dieser Art - es ist ein Missverhältnis von Abstraktionen. Die Abstraktion, die ich will, ist eine einfache reine Funktion. Beispielsweise gibt es keine Nebenwirkungen, und es ist nicht erforderlich, eine praktische Notation für die Sequenzierung und Komposition der Funktionen zu erstellen, die nicht dem Standard (.) Entspricht, der für alle Funktionen gilt.

Ich könnte zum Beispiel Category. Ich bin zuversichtlich, dass alle meine Funktionen eine Identität liefern können, obwohl ich sie wahrscheinlich nicht brauche. Da Categorydie Anwendung jedoch nicht unterstützt wird, benötige ich trotzdem eine abgeleitete Klasse, um diese Operation hinzuzufügen.

Steve314
quelle
2
Nennen Sie mich verrückt, aber wenn ich an eine Typenklasse denke, wie Sie sie beschreiben, die zum Anwenden und Komponieren usw. gedacht ist, dann denke ich an anwendungsbezogene Funktoren, die Funktionen sind. Vielleicht ist das die Typenklasse, an die Sie denken?
Jimmy Hoffa
1
Ich denke nicht, dass Applicativedas ganz richtig ist - es erfordert, dass die Werte sowie die Funktionen umgebrochen werden, während ich nur die Funktionen umbrechen möchte und die umgebrochenen Funktionen wirklich Funktionen sind, während meine umgebrochenen Funktionen normalerweise nicht (in) sind Im allgemeinsten Fall handelt es sich um ASTs, die Funktionen beschreiben. Wo <*>hat Typ f (a -> b) -> f a -> f b, ich möchte einen Anwendungsoperator mit Typ g a b -> a -> bwo aund bspezifizieren die Domäne und Codomäne der umschlossenen Funktion, aber was in der Hülle ist, ist nicht (notwendigerweise) eine echte Funktion. Auf Pfeile - möglicherweise werde ich einen Blick darauf werfen.
Steve314
3
Wenn Sie umgekehrt wollen, würde das nicht eine Gruppe bedeuten?
jk.
1
@jk. Toller Punkt, zu erkennen, dass es viele Dinge zu lesen gibt, die über Umkehrungen von Funktionen zu lesen sind, die dazu führen können, dass das OP findet, wonach er sucht. Hier ist eine interessante Lektüre zum Thema. Aber eine Google for Haskell-Inverse-Funktion bietet eine Menge neugieriger Leseinhalte. Vielleicht will er nur Data.Group
Jimmy Hoffa
2
@ Steve314 Ich dachte Funktionen mit Komposition sind eine monoidale Kategorie. Sie sind ein Monoid, wenn Domäne und Codomäne immer gleich sind.
Tim Seguine

Antworten:

14

Nun, ich kenne keine Ideen, die sich selbst als "funktional" vermarkten. Aber es gibt einige, die sich annähern

Kategorien

Wenn Sie ein einfaches Funktionskonzept haben, das Identitäten und Zusammensetzung hat, dann haben Sie eine Kategorie.

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

Der Nachteil ist , dass Sie nicht eine schöne Kategorie Instanz mit einem Satz von Objekten erstellen können ( a, b, und c). Sie können eine benutzerdefinierte Kategorie erstellen, nehme ich an.

Pfeile

Wenn Ihre Funktionen eine Vorstellung von Produkten haben und beliebige Funktionen einfügen können, sind Pfeile für Sie

 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 hat einen Anwendungsbegriff, der wichtig für das ist, was Sie wollen.

Bewerber

Bewerber haben Ihren Begriff der Anwendung, ich habe sie in einem AST verwendet, um Funktionsanwendung darzustellen.

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

Es gibt viele andere Ideen. Ein übliches Thema ist es jedoch, eine Datenstruktur aufzubauen, die Ihre Funktion darstellt, und diese dann an eine Interpretationsfunktion zu übergeben.

So arbeiten auch wie viele freie Monaden. Wenn Sie sich mutig fühlen, empfehlen wir Ihnen, in diesen zu stöbern. Sie sind ein leistungsstarkes Werkzeug für das, was Sie vorschlagen, und ermöglichen es Ihnen, eine Datenstruktur mithilfe der doNotation aufzubauen und sie dann zu einer Nebeneffektberechnung mit verschiedenen Funktionen zusammenzufassen . Aber das Schöne ist, dass diese Funktionen nur auf die Datenstruktur angewendet werden und nicht wirklich wissen, wie Sie das alles gemacht haben. Dies ist, was ich für Ihr Beispiel eines Dolmetschers vorschlagen würde.

Daniel Gratzer
quelle
Kategorie scheint keine Anwendung zu haben - ($). Pfeile sehen auf den ersten Blick wie ein gewaltiger Overkill aus, ArrowApplyklingen aber dennoch vielversprechend - solange ich nichts liefern muss, kann es sein, dass es in Ordnung ist. +1 für den Moment, mit mehr Kontrolle zu tun.
Steve314
3
@ Steve314 Kategorien haben keine Anwendung, aber Monaden haben keine universelle Möglichkeit, sie auszuführen. Das bedeutet nicht, dass sie nicht nützlich sind
Daniel Gratzer
Es gibt einen gemeinsamen Grund , warum ich nicht verwenden können , Applicativeoder Arrow(oder Monad) - ich nicht eine normale Funktion (im Allgemeinen) wickeln können , da die Werte meiner Art repräsentieren eine Funktion , sondern sind vertreten durch Daten und unterstützt nicht beliebige Funktionen , wenn wenn es gab eine Möglichkeit zu übersetzen. Das heißt, ich kann nicht zur Verfügung stellen pure, arroder returnzum Beispiel. Übrigens - diese Klassen sind nützlich, aber ich kann sie nicht für diesen speziellen Zweck verwenden. Arrowist nicht "massiver Overkill" - das war ein falscher Eindruck, als ich das letzte Mal versuchte, die Zeitung zu lesen, als ich nicht bereit war, sie zu verstehen.
Steve314
@ Steve314 Die Idee, eine Monadenschnittstelle zum Aufbau von Daten bereitzustellen, ist das, wofür kostenlose Monaden verwendet werden. Probieren Sie sie aus
Daniel Gratzer,
Ich habe mir das Video von Haskell Exchange 2013 angesehen - Andres Löh erklärt es auf jeden Fall gut, obwohl ich es wahrscheinlich noch einmal ansehen, mit der Technik spielen usw. Ich bin mir nicht sicher, ob es hier gebraucht wird. Mein Ziel ist die Abstraktion einer Funktion mithilfe einer Darstellung, die keine Funktion ist (aber eine Interpreterfunktion hat). Ich benötige keine Abstraktion von Nebenwirkungen und keine saubere Notation für Sequenzierungsvorgänge. Sobald diese Funktionsabstraktion verwendet wird, werden Anwendungen und Kompositionen einzeln in einem Algorithmus in einer anderen Bibliothek ausgeführt.
Steve314
2

Wie Sie hervorheben, besteht das Hauptproblem bei der Verwendung von Applicative darin, dass es keine sinnvolle Definition für gibt pure. Daher Applywurde erfunden. Zumindest verstehe ich das so.

Leider liegen mir keine Beispiele vor, von Applydenen nicht auch Beispiele vorliegen Applicative. Es wird behauptet, dass dies zutrifft IntMap, aber ich habe keine Ahnung warum. Ebenso weiß ich nicht, ob Ihr Beispiel - versetzte Ganzzahlen - eine ApplyInstanz zulässt .

user185657
quelle
Dies liest sich eher wie ein Kommentar, siehe Wie man antwortet
Mücke
Es tut uns leid. Dies ist mehr oder weniger meine allererste Antwort.
user185657
Wie schlagen Sie vor, die Antwort zu verbessern?
user185657
Sehen Sie bearbeiten ing , um Hilfe Leser sehen , wie Ihre Antwort Adressen die Frage gestellt : „Warum gibt es nicht ein für typeclass Funktionen? Ist es‚nur weil es nicht‘oder‚ist , weil es nicht so nützlich ist , wie Sie denken‘? Oder vielleicht gibt es ein grundsätzliches problem mit der idee? "
gnat
1
Ich hoffe, das ist besser
user185657
1

Zusätzlich zu den erwähnten Category, Arrowund Applicative:

Ich habe auch Data.Lambdavon Conal Elliott entdeckt:

Einige funktionsähnliche Klassen mit Lambda-ähnlicher Konstruktion

Sieht natürlich interessant aus, ist aber ohne Beispiele schwer zu verstehen ...

Beispiele

Beispiele finden Sie auf der Wiki-Seite über materielle Werte (TV) , die eines der Dinge zu sein scheinen, die zur Schaffung einer TypeComposeBibliothek geführt haben. siehe Eingänge und funktionswerte Ausgänge .

Die Idee der TV-Bibliothek ist es, Haskell-Werte (einschließlich Funktionen) auf greifbare Weise anzuzeigen.

Um der StackOverflow-Regel zu folgen, dass keine nackten Lonks veröffentlicht werden sollen, kopiere ich einige Bits, die die Idee zu diesen Dingen vermitteln sollen:

Das erste Beispiel lautet:

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

Das gibt, wenn ausgeführt als runIO shopping(siehe dort für weitere Kommentare, GUIs und weitere Beispiele):

shopping list: apples: 8
bananas: 5
total: 13
imz - Ivan Zakharyaschev
quelle
Wie geht das auf die gestellte Frage ein? siehe Wie man antwortet
Mücke
@gnat Ich dachte, dass die Definitionen in Data.LambdaKlassen für funktionsähnliche Dinge geben (nach denen gefragt wurde) ... Ich war mir nicht sicher, wie diese Dinge verwendet werden sollen. Ich habe das ein bisschen erforscht. Wahrscheinlich bieten sie jedoch keine Abstraktion für Funktionsanwendungen.
imz - Ivan Zakharyaschev