2010-05-18 4 views
10

Die folgende einfache Funktion wendet eine gegebene monadische Funktion iterativ an, bis sie auf Nothing trifft. An diesem Punkt wird der letzte Nicht-Nothing-Wert zurückgegeben. Es tut, was ich brauche, und ich verstehe, wie es funktioniert.Vermeidung expliziter Rekursion in Haskell

lastJustM :: (Monad m) => (a -> m (Maybe a)) -> a -> m a 
lastJustM g x = g x >>= maybe (return x) (lastJustM g) 

Im Rahmen meiner Selbsterziehung in Haskell Ich versuche explizite Rekursion zu vermeiden (oder zumindest verstehen, wie man), wann immer ich kann. Es scheint, dass es in diesem Fall eine einfache, nicht explizit rekursive Lösung geben sollte, aber ich habe Probleme, es herauszufinden.

Ich möchte nicht etwas wie a monadic version von , da es teuer sein könnte, alle Pre-Nothing-Werte zu sammeln, und ich kümmere mich nicht um sie sowieso.

Ich überprüfte Hoogle nach der Unterschrift und nichts taucht auf. Das m (Maybe a) Bit lässt mich denken, dass ein Monade-Transformator hier nützlich sein könnte, aber ich habe nicht wirklich die Intuitionen, die ich (noch) mit den Details bekommen müsste.

Es ist wahrscheinlich entweder peinlich leicht, dies zu tun oder peinlich leicht zu sehen, warum es nicht getan werden kann oder sollte, aber dies wäre nicht das erste Mal, dass ich Selbstpeinlichkeit als pädagogische Strategie benutzt hätte.

Update: Ich könnte natürlich ein Prädikat bietet stattdessen Maybe verwenden: so etwas wie (a -> Bool) -> (a -> m a) -> a (den letzten Wert zurückgegeben wird, für die das Prädikat wahr ist), als auch nur funktionieren würde. Was mich interessiert, ist eine Möglichkeit, eine der beiden Versionen ohne explizite Rekursion zu schreiben, mit Standard-Kombinatoren.


Hintergrund: Hier ist ein vereinfachtes Ausführungsbeispiel für Kontext: Angenommen, wir in Irrfahrten in der Einheit Platz interessiert sind, aber wir kümmern sich nur um Punkte der Ausfahrt. Wir haben die folgenden Schritt Funktion:

randomStep :: (Floating a, Ord a, Random a) => 
       a -> (a, a) -> State StdGen (Maybe (a, a)) 
randomStep s (x, y) = do 
    (a, gen') <- randomR (0, 2 * pi) <$> get 
    put gen' 
    let (x', y') = (x + s * cos a, y + s * sin a) 
    if x' < 0 || x' > 1 || y' < 0 || y' > 1 
    then return Nothing 
    else return $ Just (x', y') 

So etwas wie evalState (lastJustM (randomStep 0.01) (0.5, 0.5)) <$> newStdGen wird uns einen neuen Datenpunkt.

+2

'lastJustM = fix (.. LiftM2 ap ((>> =)) (Flip (vielleicht zurück))..)'. (OK, ich habe mit "pointfree" betrogen.) – kennytm

+1

@KennyTM: Danke! Ich habe nicht einmal daran gedacht, "punktfrei" zu versuchen, weil ich keine Ahnung hatte, dass es in der Lage wäre, mit so etwas umzugehen. Jetzt muss ich nur herausfinden, wie es funktioniert. –

+1

Es gibt einen Algorithmus, um * alles * auf eine punktfreie Form zu reduzieren, wenn man eine Handvoll Kombinatoren benutzt; Dies ist, was 'pointfree' verwendet. Natürlich kann das Ergebnis nützlich sein oder auch nicht :) –

Antwort

9

Eine Menge von dem, was die explizite Rekursion vermeidet, ist das Zusammensetzen von eingebauten rekursiven Kombinatoren, die normalerweise mit sehr allgemeinen unbelasteten Werten arbeiten. Das Gleiche in einem Functor, Monad oder einem anderen angehobenen Typ funktioniert manchmal mit grundlegenden Hebeoperationen wie fmap, <*>, und so weiter. In einigen Fällen ist eine vorgelöste Version bereits vorhanden, wie bei mapM, zipWithM und so weiter. Andere Zeiten, wie mit takeWhile, Heben ist nicht trivial und keine eingebaute Version wird zur Verfügung gestellt.

Ihre Funktion hat tatsächlich Eigenschaften von etwas, das eine gehobene Version von Standard-Kombinatoren sein sollte. Also lassen Sie uns zuerst die Monade Streifen aus zu rekonstruieren die Funktion sind Sie implizit heben:

lastJust :: (a -> Maybe a) -> a -> a 

Das Wort „letzte“ hier gibt uns einen Hinweis; Nicht explizite Rekursion verwendet oft temporäre Listen als Kontrollstrukturen. Was Sie wollen, ist last auf die Liste angewendet, die durch Iteration der Funktion generiert wurde, bis Nothing.Mit einer leichten Verallgemeinerung des Typs, finden wir den Generator:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

So haben wir so etwas wie diese:

dup x = (x, x) 
lastJust f x = last $ unfoldr (fmap dup . f) x 

Leider wir an dieser Stelle Art stecken sind, weil (mein Wissen) Es gibt keine monadische Entfaltung und das Heben ist wie takeWhile nicht trivial. Eine andere Sache, die Sinn machen könnte, ist eine allgemeinere Entfaltung mit einer Signatur wie (MonadMaybe m) => (b -> m (a, b)) -> b -> m [a] und einem begleitenden MaybeT Transformer, aber das gibt es auch nicht in den Standardbibliotheken, und Monadtransformatoren sind irgendwie eine Grube der Verzweiflung. Ein dritter Ansatz könnte darin bestehen, einen Weg zu finden, um sowohl Maybe als auch die unbekannte Monade als MonadPlus oder etwas Ähnliches zu verallgemeinern.

Natürlich kann es andere Ansätze mit einer anderen Struktur geben, aber ich vermute, dass Sie ähnliche Unbehaglichkeit mit jeder Funktion finden, die rekursiv in eine Monade "gehen" muss, zB führt jeder Schritt konzeptionell einen anderen ein Schicht, die mit >>=, join usw.

Zusammengefasst beseitigt werden müssen: ohne explizite Rekursion, eine rekursive combinator mit (etwas Geschmack von unfoldM) Auf dem ersten Inspektion Ihrer Funktion als geschrieben wird am besten zum Ausdruck, der nicht existiert. Sie können den Kombinator entweder selbst schreiben (wie es die Leute mit takeWhileM gemacht haben), auf Hackage nach monadischen rekursiven Kombinatoren suchen oder Ihren Code einfach so lassen, wie er ist.

+0

Schöne Antwort, aber ich finde die rekursive Version schrecklich durchsichtig.Glaubst du wirklich, dass es verbessert werden würde, indem man stattdessen einen monadischen Entfaltungs-Kombinator benutzt? –

+1

@Norman Ramsey: Vielleicht (kein Wortspiel beabsichtigt), nehme ich an. Ich mag Standardkombinatoren, wenn sie die semantische Struktur offensichtlicher machen, in diesem Fall, dass sie implizit eine Liste von Ergebnissen erzeugt und zusammenbricht (ein Hylomorphismus, wenn ich mich an die Terminologie richtig erinnere?). Aus dem gleichen Grund möchte ich in Monaden usw. codieren, indem ich die zugrunde liegende Logik z. B. '<$>' und '<*>' anstelle von komplexen, imperativ wirkenden 'do'-Blöcken hebe. In diesem Fall ist die Funktion so einfach wie sie ist und der notwendige Kombinator existiert nicht, also würde ich wahrscheinlich selbst nicht stören. –

+0

@Norman Ramsey: Auf der anderen Seite kann es nur ein Zeichen dafür sein, dass ich die Category Theory-Lehrbücher streichen und aufhören muss, überall Corcursion zu bemerken ... –

3

Ich will nicht so etwas wie eine monadische Version von takeWhile, da es teuer sein könnte, alle Pre-Nichts-Werte zu sammeln, und ich über sie sowieso nicht.

Monadic-Listen takeWhile sammelt nicht alle vorge Nichts Werte, wenn Sie ausdrücklich das tun wollen. Dies wäre die takeWhile aus der "List" package, in this answer zu der Frage verwendet, die Sie verknüpft haben.

Was die Funktion, die Sie implementieren möchten:

{-# LANGUAGE ScopedTypeVariables #-} 

import Control.Monad.ListT (ListT) -- from "List" package on hackage 
import Data.List.Class (takeWhile, iterateM, lastL) 
import Prelude hiding (takeWhile) 

thingM :: forall a m. Monad m => (a -> Bool) -> (a -> m a) -> m a -> m a 
thingM pred stepM startM = 
    lastL $ takeWhile pred list 
    where 
     list :: ListT m a 
     list = iterateM stepM startM 
+0

Ich bin daran interessiert, mehr über monadische Listen zu erfahren - ich verstehe immer noch nicht genau, wie sie es vermeiden, die Werte zu sammeln, zum Beispiel. Ich hatte noch keine Gelegenheit, die "ListT done right" -Seite im Wiki zu bearbeiten, aber hast du irgendwelche Vorschläge für andere Startpunkte, die ich wahrscheinlich nicht von Googling "list haskell", "monadisch" finden würde Listen "usw.? –

+1

@Travis Brown: Ich bin mir nicht sicher, was Sie meinen, indem Sie hier die Werte sammeln. Wenn Listenelemente so schnell verworfen werden, wie sie erstellt wurden, wird die vollständige Liste niemals auf einmal erstellt. Das ist, was ich oben meinte, dass Listen eine "Kontrollstruktur" sind - das Falten einer Liste ist im Grunde Rekursion mit dem Call-Stack, der "im Voraus" angegeben wurde, oft träge. –

+0

@camccann: Ich glaube, ich verwirre mich nur darüber, wie die Monade und die Faulheit hier interagieren. Ich werde den Mund halten, bis ich eine Chance habe, mehr zu lesen und nachzudenken. Danke für deine Antworten. –