MonadFix Beispiel für []

Question

Die Instanz ist definiert als

instance MonadFix [] where 
    mfix f = case fix (f . head) of 
      [] -> [] 
      (x:_) -> x : mfix (tail . f) 

Aber ich bin es nicht die intuitive Bedeutung dahinter in Bezug auf die [] Monade als nicht-deterministische Berechnungen gesehen zu erfassen. In mfix f Funktion f muss nicht streng in seinem Argument sein, so kann es das Argument nicht untersuchen. Und entsprechend der Definition kann es auch nicht das Argument irgendwo in seiner Ausgabe verwenden, sonst wird es irgendwann fix (f . head) und divergieren. Also gibt es irgendeine Verwendung (oder gutes Beispiel) für mfix für Listen, außer mfix (const someList)?

Answer 1

Es ist wahrscheinlich am einfachsten, es so zu sagen. Die Funktionen f für die mfix f ist vollständig definiert sind diejenigen, für die das Rückgrat von f x hängt nicht von x, so können sie

f x = [f1 x, ..., fn x] 

für einige n (möglicherweise unendlich) und einige f1 in Form geschrieben werden. .., fn. Dann

mfix f = [fix f1, ..., fix fn] 

(natürlich dafür wirklich total definiert werden, muss jeder fix fi auch definiert werden).

---

mfix kann als nichtdeterministisch geben Sie den Fixpunkt einer nichtdeterministische Funktion betrachtet werden. Die ziemlich starke Einschränkung besteht darin, dass die Form der nichtdeterministischen Berechnung in keiner Weise von der Eingabe abhängen kann. Wir scheinen eine gewisse Einschränkung der Berechnung zu benötigen, um zu beginnen, aber Sie könnten hoffen, zumindest einen Zweig der Berechnung bedingt abbrechen zu können (sagen wir, wenn eine Zwischenrechnung negativ ist). Ich habe immer gedacht, dass es möglich sein sollte, mfix auf diese Weise zu verwenden, indem man eine andere Nicht-Determinismus-Monade verwendet, deren Wahloperation nicht assoziativ ist, aber niemals die Details ausgearbeitet hat.

Answer 2

All fix Varianten haben ein Problem, wenn man sie tatsächlich mit einer strikten Funktion verwenden, aber das ist im Allgemeinen kein Problem in dem realen Anwendungsfall^{& Dolch;}: a ist grundsätzlich immer ein Funktionstyp, und jedes Lambda ist bereits in NF.

So, wie für einen konkreten Einsatz ... na ja, hier ist zumindest etwas, das konvergiert:

f :: (Int -> Int) -> [Int -> Int]

f f' = [\x -> if x>0 then f' (x-1) * i else 1 | i<-[0..]]

f im Grunde ein erzeugt Liste der Leistungsfunktionen.

GHCi> take 20 $ mfix f <*> [1,2] [0,0,1,1,2,4,3,9,4,16,5,25,6,36,7,49,8,64,9,81]

Was dies tatsächlich nützlich ist, denn ich bin nicht sicher, aber es recht interessant Verhalten hat.

Ich habe gerade festgestellt, dass dies ein schlechtes Beispiel ist, da es tatsächlich einem einzigen fix (f . head) entspricht. Hm ...

---

^{& dolch;} _{Sie scheinen recht zu haben: es ist ein Problem im Fall von a -> [a], weil es keinen offensichtlichen Weg gibt, die Listenstruktur abhängig von dem Argument zu machen, ohne streng zu werden.}