Verwendung von List Monad vs fmap

Question

Gibt es irgendwelche praktischen Anwendungen der Liste Monade, die nicht nur auf eine fmap rollen würde? Wann würden Sie bind fmap mit der Liste monad verwenden?

Wie zum Beispiel können Sie [1,2,3] >>= return . (+ 1) tun, aber das ist das gleiche wie (+1) <$> [1,2,3] - wann würden Sie Bindung ohne eine Rückkehr auf der Liste verwenden?

Answer 1

Die Verwendung von bind mit return entspricht der Verwendung von fmap. Tatsächlich

fmap f m = m >>= return . f 

Die Verwendung von binden, die nicht mit fmap reproduziert werden kann, sind genau diejenigen, die nicht über diese Verwendung Rückkehr beinhalten. Um nur ein (hoffentlich) interessantes Beispiel für Listen zu geben, lassen Sie uns über L-Systems sprechen.

L-Systeme von Aristid Linden 1968. Als Ersetzungssysteme erstellt wurden, beginnen sie mit einem einfachen Objekt und wiederholt ersetzen Teile davon einen Satz von Umschreibregeln oder Produktionen mit. Sie können verwendet werden, um Fraktale und andere selbstähnliche Bilder zu erzeugen. Ein kontextfreies, deterministisches L-System (oder D0L) wird durch das Dreifache eines Alphabets, eines Axioms und einer Sammlung von Produktionsregeln definiert.

Für unser Alphabet, werden wir eine Art definieren:

data AB = A | B deriving Show 

für unser Axiom oder Zustand beginnen, werden wir das Wort [A, B] verwenden.

Für unsere Regeln benötigen wir eine Karte von einem einzelnen Buchstaben zu einer Folge von Buchstaben. Dies ist eine Funktion des Typs AB -> [AB]. Verwenden wir diese Regel:

myRule :: AB -> [AB] 
myRule A = [A, B] 
myRule B = [A] 

Um die Regel anzuwenden, müssen wir jeden Buchstaben mit seiner Produktionsregel neu schreiben. Wir müssen dies für alle Buchstaben gleichzeitig tun. Günstig, das ist genau das, was >>= tut für Listen:

apply rule axiom = axiom >>= rule 

Jetzt wollen wir unsere Regel zu unserem Axiom gelten, den ersten Schritt in der L-Systems zu erzeugen:

> apply myRule myAxiom 
> [A, B, A] 

Dies ist Linden der original L-System, verwendet für die Modellierung von Algen. Wir können laufen, es zu sehen Fortschritte:

> mapM_ print . take 7 $ iterate (>>= myRule) myAxiom 
[A,B] 
[A,B,A] 
[A,B,A,A,B] 
[A,B,A,A,B,A,B,A] 
[A,B,A,A,B,A,B,A,A,B,A,A,B] 
[A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A] 
[A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B] 

Im Allgemeinen binden für Listen ist concatMap, und verwenden Sie es genau, wenn Sie Zuordnung mit Verkettung kombinieren möchten.Eine andere Interpretation ist, dass Listen eine nicht-deterministische Wahl darstellen und Funktionen binden, indem sie jede Möglichkeit einmal aus der Liste auswählen. Zum Beispiel Würfel:

do 
    d1 <- [1..6] 
    d2 <- [1..6] 
    return (d1, d2) 

Dies gibt alle möglichen Arten von 2W6 rollen.

Answer 2

factors :: Int -> [Int] 
factors n = do 
    q <- [1..n] 
    filter ((==n) . (*q)) [1..n] 

... oder, in entzuckert Notation,

factors n = [1..n] >>= ($[1..n]) . filter . fmap (==n) . (*) 

Das ist natürlich kaum effizient, aber es funktioniert:

*Main> factors 17 
[17,1] 
*Main> factors 24 
[24,12,8,6,4,3,2,1] 
*Main> factors 34 
[34,17,2,1] 

Für Operationen, die die sind nicht so einfach, wie * , also könnte man einen Brute-Force-Ansatz nicht vermeiden, das könnte tatsächlich eine gute Lösung sein.

Answer 3

Für eine Sache ist concatMap nur . Und concat ist nur join. Ich habe beide häufig in echtem Code verwendet.

Eine andere Sache, die Sie tun können, ist, eine Liste von Funktionen auf einen Wert anzuwenden.

λ:> applyList = sequence 
λ:> applyList [(2*), (3+)] 4 
[8,7] 

Sie können auch eine Liste aller Teilmengen einer Liste erzeugen

λ:> import Control.Monad 
λ:> allSubsets = filterM (const [True, False]) 
λ:> allSubsets "ego" 
["ego","eg","eo","e","go","g","o",""] 

Oder sogar alle Strings aufzuzählen, die aus einem Alphabet gebildet werden kann

λ:> import Data.List 
λ:> import Control.Monad 
λ:> allStrings = sequence <=< (inits . repeat) 
λ:> take 100 $ allStrings ['a'..'z'] 
["","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","aa","ab","ac","ad","ae","af","ag","ah","ai","aj","ak","al","am","an","ao","ap","aq","ar","as","at","au","av","aw","ax","ay","az","ba","bb","bc","bd","be","bf","bg","bh","bi","bj","bk","bl","bm","bn","bo","bp","bq","br","bs","bt","bu","bv","bw","bx","by","bz","ca","cb","cc","cd","ce","cf","cg","ch","ci","cj","ck","cl","cm","cn","co","cp","cq","cr","cs","ct","cu"] 

Vielleicht praktisch mehr, Sie kann die Anwendungsinstanz verwenden, um zwei Listen miteinander zu kombinieren

λ:> zipWith' f xs ys = f <$> xs <*> ys 
λ:> zipWith' (+) [1..3] [5..8] 
[6,7,8,9,7,8,9,10,8,9,10,11]