(Inspiriert von meiner Antwort auf diese Frage .)
Betrachten Sie diesen Code (er soll das größte Element finden, das kleiner oder gleich einer bestimmten Eingabe ist):
data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)
closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing where
precise :: Maybe (Integer, v) -> TreeMap v -> Maybe (Integer, v)
precise closestSoFar Leaf = closestSoFar
precise closestSoFar (Node k v l r) = case i `compare` k of
LT -> precise closestSoFar l
EQ -> Just (k, v)
GT -> precise (Just (k, v)) r
Das ist nicht sehr faul. Sobald der GT
Fall eingegeben ist, wissen wir sicher, dass der endgültige Rückgabewert Just
eher etwas als sein wird Nothing
, aber der Wert Just
ist erst am Ende verfügbar. Ich möchte dies fauler machen, damit das Just
verfügbar ist, sobald der GT
Fall eingegeben wird. Mein Testfall dafür ist, dass ich eher Data.Maybe.isJust $ closestLess 5 (Node 3 () Leaf undefined)
bewerten True
als auf den Grund gehen möchte . Hier ist eine Möglichkeit, wie ich mir das vorstellen kann:
data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)
closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess _ Leaf = Nothing
closestLess i (Node k v l r) = case i `compare` k of
LT -> closestLess i l
EQ -> Just (k, v)
GT -> Just (precise (k, v) r)
where
precise :: (Integer, v) -> TreeMap v -> (Integer, v)
precise closestSoFar Leaf = closestSoFar
precise closestSoFar (Node k v l r) = case i `compare` k of
LT -> precise closestSoFar l
EQ -> (k, v)
GT -> precise (k, v) r
Jetzt wiederhole ich mich jedoch: Die Kernlogik ist jetzt in beiden closestLess
und in precise
. Wie kann ich das so schreiben, dass es faul ist, ohne mich zu wiederholen?
quelle
Ausgehend von meiner nicht faulen Implementierung habe ich mich zunächst umgestaltet
precise
, umJust
als Argument zu erhalten , und den Typ entsprechend verallgemeinert:Dann habe ich es geändert, um
wrap
früh zu tun und mich mitid
in demGT
Fall anzurufen :Dies funktioniert immer noch genauso wie zuvor, mit Ausnahme der zusätzlichen Faulheit.
quelle
id
s in der Mitte zwischenJust
und dem Finale(k,v)
vom Compiler eliminiert? wahrscheinlich nicht, Funktionen sollen undurchsichtig sein, und Sie könnten (typmöglich)first (1+)
anstelle vonid
allem verwenden, was der Compiler weiß. aber es ergibt einen kompakten Code ... natürlich ist mein Code das Enträtseln und Spezifizieren von Ihnen hier, mit der zusätzlichen Vereinfachung (der Eliminierung desid
s). auch sehr interessant, wie der allgemeinere Typ als Einschränkung dient, eine Beziehung zwischen den beteiligten Werten (allerdings nicht eng genug, mitfirst (1+)
erlaubt alswrap
).precise
wird bei zwei Typen verwendet, die direkt den beiden Spezialfunktionen entsprechen, die in der ausführlicheren Variante verwendet werden. schönes Zusammenspiel dort. Außerdem würde ich dieses CPS nicht nennen, eswrap
wird nicht als Fortsetzung verwendet, es wird nicht "innen" aufgebaut, es wird - durch Rekursion - außen gestapelt. Vielleicht , wenn es wurde als Fortsetzung verwendet wird , könnten Sie loszuwerden, die Fremd bekommenid
s ... btw können wir hier noch einmal sehen , dass alte Muster aus funktionellem Argumente als Indikator verwendet, was zu tun ist , zwischen den beiden Handlungs Schalten (Just
oderid
).Ich denke, die CPS-Version, die Sie mit sich selbst beantwortet haben, ist die beste, aber der Vollständigkeit halber hier noch ein paar Ideen. (EDIT: Buhrs Antwort ist jetzt die performanteste.)
Die erste Idee ist, den "
closestSoFar
" Akkumulator loszuwerden und stattdessen denGT
Fall die gesamte Logik der Auswahl des am weitesten rechts liegenden Werts als des Arguments behandeln zu lassen. In dieser Form kann derGT
Fall direkt Folgendes zurückgebenJust
:Dies ist einfacher, benötigt jedoch etwas mehr Platz auf dem Stapel, wenn Sie viele
GT
Fälle treffen . Technisch könnte man das sogarfromMaybe
in der Akkumulatorform verwenden (dh dasfromJust
implizite in luquis Antwort ersetzen ), aber das wäre ein redundanter, nicht erreichbarer Zweig.Die andere Idee, dass es wirklich zwei "Phasen" des Algorithmus gibt, eine vor und eine nach dem Drücken von a
GT
, also parametrisieren Sie ihn durch einen Booleschen Wert, um diese beiden Phasen darzustellen, und verwenden abhängige Typen, um die Invariante zu codieren, dass es immer eine geben wird Ergebnis in der zweiten Phase.quelle
Wie wäre es mit
?
quelle
Just
dennoch vollständig ist. Ich weiß, dass Ihre Lösung, wie sie geschrieben wurde, tatsächlich vollständig ist, aber es ist insofern spröde, als eine scheinbar sichere Modifikation dann zu einer Bodenbildung führen könnte.Just
wird.Nothing
Daher wird ein Test hinzugefügt, um sicherzustellen, dass es nicht jedes Mal wiederholt wird.Wir wissen nicht nur immer
Just
, nach seiner ersten Entdeckung, wir wissen es auch immerNothing
bis dahin. Das sind eigentlich zwei verschiedene "Logiken".Also gehen wir zuerst nach links, also machen Sie das deutlich:
Der Preis ist, dass wir höchstens einen Schritt höchstens einmal wiederholen.
quelle