Ist es möglich, im Einzelfall eine "umgekehrte" Funktion höherer Ordnung zu definieren?

Question

Ich bin ein Haskell-Neuling. Ich versuche eine Minisprache innerhalb von Haskell zu erstellen und möchte, wenn möglich, eine höherwertige Funktion namens opp (kurz für "Gegenteil") haben, die eine Reihe vertrauter Funktionen in ihre offensichtlichen Gegensätze umwandelt. Zum Beispiel wäre opp succ die Funktion pred, opp head wäre last, und so weiter. Ich habe keine allgemeine Definition dessen, was es bedeutet, eine Funktion in ihr Gegenteil zu verwandeln: Ich möchte nur einige Schlüsselbeispiele auswählen und erklären, was ihre Gegensätze sind. Ich möchte also eine hochpolymorphe Funktion, die kaum definiert ist.

Die Schwierigkeit scheint zu sein, dass ich die Funktionen eher durch ihre Namen als durch ihre Essenzen (sozusagen) erkennen möchte. Eine Manifestation dieser Schwierigkeit besteht darin, dass, wenn ich schreibe

opp succ = pred

dann Haskell behandelt succ als Variable und deshalb gibt mir eine konstante Funktion, die immer den Wert nimmt pred. Was ich wirklich will, ist etwas mehr zu sagen, "Wenn Sie jemals die Zeichenfolge opp succ sehen, dann denken Sie darüber als ein anderer Name für pred." Aber nachdem ich eine Weile herumgesucht habe, kann ich nicht herausfinden, wie das geht (wenn es überhaupt möglich ist).

Um es zusammenzufassen, ich möchte eine Funktion

opp :: (a -> b) -> (a -> b)

sagen Dinge wie

opp succ = pred

opp pred = succ

opp head = last

definieren

opp last = head

und zu dieser Liste hinzufügen, wann immer mir danach ist. Natürlich kann ich das nicht so machen, aber gibt es eine nicht-schreckliche Art, den gleichen Effekt zu erzielen?

Answer 1

Es könnte möglich sein, eine Art Hash-Map basierend auf der Closures-Adresse auf Heap zu verwenden, um die Funktionen zu identifizieren. Dann könnten Sie eine solche inverse Tabelle erstellen. Leider würden Sie nicht wirklich bekommen, was Sie wollen, da Funktionen nur Werte sind und als solche werden sie immer dann erstellt, wenn der Compiler (oder die Laufzeit) sich dafür entscheidet.

z. wenn man sogar sagen, dass

opp head = last 

Sie könnten (auf der Compiler-Implementierung abhängig) erreichen nichts für

opp (λx.head x) 

In der Tat, Sie keine zuverlässige Identität auf Funktionswerte haben - daher denke ich, gibt es kein brauchbarer Weg, um das zu tun, was Sie vorhaben.

Answer 2

Wenn wir Ihre Frage in dieser Form neu formulieren das Problem kann Ihnen klar geworden:

opp x | x == succ = pred 
     | x == pred = succ 

Dies gibt Ihnen die Fehlermeldung, dass (a -> b) keine Eq Instanz hat, die es nicht, da die Gleichstellung von Funktionen haben kann, ist nicht definiert.

Eine Lösung wäre, einen separaten Datentyp zu definieren, auf den Sie eine Musteranpassung vornehmen können.

Answer 3

Ja können Sie, aber Sie benötigen RankNTypes, um eine nette Implementierung zu haben.

{-# LANGUAGE TypeOperators #-} 
{-# LANGUAGE RankNTypes #-} 
module Opposites where 

class Opposite f where 
    makeOpposite :: (a -> b) -> (a -> b) -> f a b 


data FunctionAndOpposite a b = FunctionAndOpposite (a -> b) (a -> b) 

instance Opposite (->) where 
    makeOpposite = const 

instance Opposite FunctionAndOpposite where 
    makeOpposite = FunctionAndOpposite 

opp :: FunctionAndOpposite a b -> a -> b 
opp (FunctionAndOpposite _ f) = f 

type a :<-> b = forall f. Opposite f => f a b 

succ' :: Enum a => a :<-> a 
succ' = makeOpposite succ pred 

pred' :: Enum a => a :<-> a 
pred' = makeOpposite pred succ 

head' :: [a] :<-> a 
head' = makeOpposite head last 

last' :: [a] :<-> a 
last' = makeOpposite last head 

Beispiel Nutzung:

> head' [1,2,3] 
1 
> opp head' [1,2,3] 
3 

Wie es

Zum einen arbeitet, gibt es die Opposite Klasse. Dies beschreibt nur eine f a b, die aus zwei Funktionen von (a -> b) (die normalen und entgegengesetzten Funktionen) aufgebaut werden kann.

Als nächstes wird ein Datentyp FunctionAndOpposite definiert. Dies speichert nur die zwei Funktionen. Jetzt sind sowohl die Standardfunktion als auch die Instanzen der Klasse Opposite. Die Funktionsinstanz verwirft nur die gegenteilige Funktion.

Jetzt kann die opp Funktion definiert werden. Dies nimmt nur die zweite Funktion aus einer FunctionAndOpposite.

Schließlich erhalten wir die Linie, die sie alle zusammen bringt:

type a :<-> b = forall f. Opposite f => f a b 

was dieses definiert ist eine Art Synonym, die a und b zwei Eingangstypen nimmt, gibt dann eine Art f a b, wo f jede Opposite sein kann (abhängig von was benötigt wird).

(die :<-> ist nur ein Phantasie Name für den Typ mit TypeOperators aktiviert).

Betrachten Sie den Code head' [1,2,3]. head' hat den Typ forall f. Opposite f => f [a] a. Da es jedoch als eine Funktionsanwendung verwendet wird (da es unmittelbar danach ein Argument hat), muss f-> sein. Daher wird die Funktionsimplementierung von Opposite verwendet, wobei das erste Argument an makeOpposite zurückgegeben wird, also head (großartig!).

Aber sagen wir mal opp head' [1,2,3] heißt. opp hat den Typ FunctionAndOpposite a b -> a -> b, also f muss FunctionAndOpposite sein. Daher wird die FunctionAndOpposite Instanz von Opposite aufgerufen, die den Datentyp unter Verwendung beider Argumente zu makeOpposite erstellt. opp zieht dann die zweite Funktion, die last ist.

---

Als beiseite, dies erfolgt eine ähnliche Technik in der für Isomorphismlens Bibliothek verwendet werden.Ein Isomorphismus ist im Grunde ein Paar von Funktionen, die sich gegenseitig invertieren. ZB (+2) und (-2), reverse und sich selbst. Dies ist im Allgemeinen wahrscheinlich ein nützlicheres Konzept, da Sie Operationen für einen Datentyp über eine Umwandlung ausführen können. Weitere Details finden Sie unter Control.Lens.Iso. Beachten Sie jedoch, dass Sie, um dies zu verstehen, die Objektivkonzepte verstehen müssen, was eine ziemlich große Aufgabe ist.