Wie kann Nicht-Determinismus mit einer List-Monade modelliert werden?

Question

Kann jemand erklären (besser mit einem Beispiel in einfachem Englisch), was eine Listenmonade tun kann, um nicht-deterministische Berechnungen zu modellieren? Nämlich was das Problem ist und welche Lösung eine List Monad bieten kann.

Answer 1

Wenn wir sagen, dass es nicht deterministisch ist, bedeutet dies, dass es mehr als nur Werte hat.

Das Learn You A Haskell Buch schön erklärt dies:

Ein Wert wie 5 deterministisch ist. Es hat nur ein Ergebnis und wir wissen genau was es ist. Auf der anderen Seite enthält ein Wert wie [3,8,9] mehrere Ergebnisse, so dass wir es als einen Wert sehen können, der eigentlich viele Werte gleichzeitig ist. Mit Listen als applicative functors präsentiert diese Nicht-Determinismus schön:

ghci> (*) <$> [1,2,3] <*> [10,100,1000] 
[10,100,1000,20,200,2000,30,300,3000] 

Alle möglichen Kombinationen von Elementen aus der linken Liste mit Elementen aus der rechten Liste multipliziert werden in der resultierenden Liste enthalten sind. Wenn wir uns mit Nicht-Determinismus befassen, gibt es viele Möglichkeiten, die wir machen können, also probieren wir alle aus, und das Ergebnis ist ein nicht-deterministischer Wert, nur hat es viel mehr Ergebnisse.

Liste Monade Modelle nicht deterministisch schön. Es ist Beispiel ist wie folgt:

instance Monad [] where 
    return x = [x] 
    xs >>= f = concat (map f xs) 
    fail _ = [] 

Also, wenn Sie einen nicht-deterministischen Wert füttern wird es einen anderen Satz von nicht-deterministischen Wert erzeugen:

ghci> [3,4,5] >>= \x -> [x, x * 2] 
[3,6,4,8,5,10] 

Answer 2

Die Liste Monade obwohl zu vertreten "sein kann alle möglichen Ergebnisse aus einer nicht-deterministischen Berechnung ". Zum Beispiel kann die Funktion

f x = [x, x + 1, x + 2] 

kann als nichtdeterministischen Berechnung interpretiert werden, dass x und gibt einen von x, x+1 und x+2 nimmt.

Die Funktion

g x = [2 * x, 3 * x] 

kann als nichtdeterministischen Berechnung interpretiert werden, dass x und gibt entweder 2 * x oder 3 * x nimmt. Die "Zusammensetzung" dieser zwei nicht-deterministischen Berechnungen sollte eine andere nicht-deterministische Berechnung sein, die x annimmt, sie in eine von x, x + 1 oder x + 2 umwandelt und sie dann entweder verdoppelt oder verdreifacht. So in Bezug auf die Listen sollte das Ergebnis

Jetzt

g =<< f x = [2 * x, 3 * x, 2 * (x + 1), 3 * (x + 1), 2 * (x + 2), 3 * (x + 2)] 

so in der Tat diese Modelle nicht-Determinismus eine Liste aller sechs Möglichkeiten, wie wir erwartet hatten.

(Es gibt einige Ungeschicklichkeit Listen für Nicht-Determinismus zu verwenden, da sie eine Reihenfolge der Elemente auch. A „Monade“ wahrscheinlich eine natürliche Art und Weise wäre nicht-Determinismus zu modellieren. Listen sicherlich genug enthalten Informationen nicht-Determinismus modellieren, aber die Reihenfolge bedeutet, dass wir mehr Informationen als nötig haben)

EDIT:. in der Tat, was ich geschrieben habe nur wirklich so weit wie mit der Liste applicative Instanz geht. Um etwas, das eine Berechnung voll wollen Sie die Vorteile des monadischen Schnittstelle nimmt, die eine Reihe von Ergebnissen zurückgibt, der an seinem Eingang hängt zum Beispiel

g 0 = [1000, 1001] 
g x = [2 * x, 3 * x, 4 * x] 

obwohl zugegebenermaßen dies ein völlig willkürliches und unmotiviert Beispiel ist!

Answer 3

Also ist es wichtig klar zu definieren, was "Nicht-Determinismus" hier bedeutet, da es nicht ganz dasselbe ist, wie es zB in einem nicht-deterministischen Algorithmus wahrgenommen werden könnte. Der hier erfasste Sinn ist, dass die Berechnung Verzweigungen - es gibt möglicherweise mehrere Zustände, zu denen das System an einem bestimmten Punkt verschieben kann.

Listen modellieren dies, weil sie einfach mehrere Elemente enthalten. Darüber hinaus bieten uns monadische Übersichten die Möglichkeit, nicht-deterministische Ergebnisse zu erstellen - das heißt, alle Zweige gleichzeitig zu modellieren.

Answer 4

Hier ist ein Beispiel für Münzwurf. Das Problem ist, wie folgt:

Sie haben zwei Münzen, Biased und Messe markiert. Die Biased Münze hat zwei Köpfe, und die Fair Münze hat einen Kopf und einen Schwanz. Wählen Sie eine dieser Münzen zufällig, werfen Sie sie und beobachten Sie das Ergebnis. Wenn das Ergebnis ein Kopf ist, wie groß ist die Wahrscheinlichkeit, dass Sie die Biased Münze ausgewählt haben?

Wir können dies in Haskell wie folgt modellieren. Zuerst müssen Sie die Art der Münze und ihre Gesichter

data CoinType = Fair | Biased deriving (Show) 

data Coin = Head | Tail deriving (Eq,Show) 

Wir wissen, dass eine faire Münze zu werfen entweder kommen können Head oder Tail während die voreingenommen Münze immer Head kommt. Wir modellieren dies mit einer Liste möglicher Alternativen (wobei implizit jede Möglichkeit gleich wahrscheinlich ist).

toss Fair = [Head, Tail] 
toss Biased = [Head, Head] 

Wir brauchen auch eine Funktion, die die Messe oder voreingenommen Münze zufällig

pick = [Fair, Biased] 

Dann holt wir es alle zusammen wie dieser Mitteilung

experiment = do 
    coin <- pick   -- Pick a coin at random 
    result <- toss coin -- Toss it, to get a result 
    guard (result == Head) -- We only care about results that come up Heads 
    return coin   -- Return which coin was used in this case 

, dass, obwohl der Code liest sich wie Wir führen das Experiment nur einmal durch, aber die Listen-Monade modelliert Nichtdeterminismus und folgt tatsächlich allen möglichen Pfaden.Daher ist das Ergebnis

>> experiment 
[Biased, Biased, Fair] 

Da alle Möglichkeiten gleich wahrscheinlich sind, können wir schließen, dass es eine 2/3 Chance, dass wir die voreingenommene Münze haben, und nur eine 1/3 Chance, dass wir die faire Münze haben .