Wie gehen funktionale Sprachen mit Zufallszahlen um?

Was ich damit meine, ist, dass in fast jedem Tutorial, das ich über funktionale Sprachen gelesen habe, eine der großartigen Eigenschaften von Funktionen darin besteht, dass, wenn Sie eine Funktion mit denselben Parametern zweimal aufrufen, Sie immer mit dem enden gleiches Ergebnis.

Wie um alles in der Welt erstellen Sie dann eine Funktion, die einen Startwert als Parameter verwendet und dann eine Zufallszahl zurückgibt, die auf diesem Startwert basiert?

Ich meine, das scheint gegen eines der Dinge zu verstoßen, die an Funktionen so gut sind, oder? Oder fehlt mir hier etwas komplett?

Sie können keine reine Funktion namens erstellen random, die bei jedem Aufruf ein anderes Ergebnis liefert. Tatsächlich können Sie nicht einmal reine Funktionen "aufrufen". Sie wenden sie an. Sie verpassen also nichts, aber das bedeutet nicht, dass Zufallszahlen in der funktionalen Programmierung tabu sind. Lassen Sie mich demonstrieren, dass ich durchgehend die Haskell-Syntax verwende.

Ausgehend von einem zwingenden Hintergrund können Sie zunächst erwarten, dass der Zufallstyp wie folgt lautet:

random :: () -> Integer

Dies wurde jedoch bereits ausgeschlossen, da Zufall keine reine Funktion sein kann.

Betrachten Sie die Idee eines Wertes. Ein Wert ist eine unveränderliche Sache. Es ändert sich nie und jede Beobachtung, die Sie darüber machen können, ist für alle Zeiten konsistent.

Es ist klar, dass random keinen Integer-Wert erzeugen kann. Stattdessen wird eine ganzzahlige Zufallsvariable erzeugt. Der Typ könnte so aussehen:

random :: () -> Random Integer

Abgesehen davon, dass die Übergabe eines Arguments völlig unnötig ist, sind Funktionen rein, sodass eine random ()so gut ist wie die andere random (). Ich gebe ab jetzt zufällig diesen Typ:

random :: Random Integer

Das ist alles in Ordnung, aber nicht sehr nützlich. Sie können erwarten, Ausdrücke wie schreiben zu können random + 42, aber Sie können nicht, weil es nicht typecheck wird. Mit Zufallsvariablen kann man noch nichts anfangen.

Dies wirft eine interessante Frage auf. Welche Funktionen sollten existieren, um Zufallsvariablen zu manipulieren?

Diese Funktion kann nicht existieren:

bad :: Random a -> a

in irgendeiner nützlichen Weise, denn dann könnte man schreiben:

badRandom :: Integer
badRandom = bad random

Das führt zu einer Inkonsistenz. badRandom ist angeblich ein Wert, aber es ist auch eine Zufallszahl. ein Widerspruch.

Vielleicht sollten wir diese Funktion hinzufügen:

randomAdd :: Integer -> Random Integer -> Random Integer

Dies ist jedoch nur ein Sonderfall eines allgemeineren Musters. Sie sollten in der Lage sein, eine beliebige Funktion auf eine zufällige Sache anzuwenden, um andere zufällige Dinge zu erhalten, wie zum Beispiel:

randomMap :: (a -> b) -> Random a -> Random b

Anstatt zu schreiben random + 42, können wir jetzt schreiben randomMap (+42) random.

Wenn Sie nur randomMap hätten, könnten Sie keine Zufallsvariablen miteinander kombinieren. Sie konnten diese Funktion zum Beispiel nicht schreiben:

randomCombine :: Random a -> Random b -> Random (a, b)

Sie könnten versuchen, es so zu schreiben:

randomCombine a b = randomMap (\a' -> randomMap (\b' -> (a', b')) b) a

Aber es hat den falschen Typ. Anstatt mit einem zu enden Random (a, b), enden wir mit einemRandom (Random (a, b))

Dies kann durch Hinzufügen einer weiteren Funktion behoben werden:

randomJoin :: Random (Random a) -> Random a

Aber aus Gründen, die irgendwann klar werden könnten, werde ich das nicht tun. Stattdessen füge ich Folgendes hinzu:

randomBind :: Random a -> (a -> Random b) -> Random b

Es ist nicht sofort offensichtlich, dass dies das Problem tatsächlich löst, aber es tut:

randomCombine a b = randomBind a (\a' -> randomMap (\b' -> (a', b')) b)

Tatsächlich ist es möglich, randomBind in Form von randomJoin und randomMap zu schreiben. Es ist auch möglich, randomJoin in Bezug auf randomBind zu schreiben. Aber ich lasse dies als Übung.

Wir könnten das ein wenig vereinfachen. Erlauben Sie mir, diese Funktion zu definieren:

randomUnit :: a -> Random a

randomUnit wandelt einen Wert in eine Zufallsvariable um. Dies bedeutet, dass wir zufällige Variablen haben können, die eigentlich nicht zufällig sind. Dies war jedoch immer der Fall; wir hätten es schon tun können randomMap (const 4) random. Der Grund für die Definition von randomUnit ist, dass wir jetzt randomMap in Bezug auf randomUnit und randomBind definieren können:

randomMap :: (a -> b) -> Random a -> Random b
randomMap f x = randomBind x (randomUnit . f)

Ok, jetzt kommen wir voran. Wir haben zufällige Variablen, die wir manipulieren können. Jedoch:

• Es ist nicht offensichtlich, wie wir diese Funktionen tatsächlich implementieren könnten,
• Es ist ziemlich umständlich.

Implementierung

Ich werde Pseudozufallszahlen angehen. Es ist möglich, diese Funktionen für echte Zufallszahlen zu implementieren, aber diese Antwort wird bereits ziemlich lang.

Im Wesentlichen wird dies so funktionieren, dass wir überall einen Startwert weitergeben werden. Wann immer wir einen neuen Zufallswert erzeugen, erzeugen wir einen neuen Startwert. Am Ende, wenn wir mit der Erstellung einer Zufallsvariablen fertig sind, wollen wir sie mit dieser Funktion abtasten:

runRandom :: Seed -> Random a -> a

Ich werde den Zufallstyp folgendermaßen definieren:

data Random a = Random (Seed -> (Seed, a))

Dann müssen wir nur noch Implementierungen von randomUnit, randomBind, runRandom und random bereitstellen, was ziemlich einfach ist:

randomUnit :: a -> Random a
randomUnit x = Random (\seed -> (seed, x))

randomBind :: Random a -> (a -> Random b) -> Random b
randomBind (Random f) g =
  Random (\seed ->
    let (seed', x) = f seed
        Random g' = g x in
          g' seed')

runRandom :: Seed -> Random a -> a
runRandom seed (Random f) = (snd . f) seed

Zufällig gehe ich davon aus, dass es bereits eine Funktion vom Typ gibt:

psuedoRandom :: Seed -> (Seed, Integer)

In diesem Fall ist der Zufall gerecht Random psuedoRandom.

Dinge weniger umständlich machen

Haskell hat syntaktischen Zucker, um Dinge wie diesen auf den Augen schöner zu machen. Es heißt Do-Notation und um alles zu nutzen, müssen wir eine Instanz von Monad for Random erstellen.

instance Monad Random where
  return = randomUnit
  (>>=) = randomBind

Getan. randomCombinevon vorher konnte nun geschrieben werden:

randomCombine :: Random a -> Random b -> Random (a, b)
randomCombine a b = do
  a' <- a
  b' <- b
  return (a', b')

Wenn ich dies für mich tun würde, würde ich sogar noch einen Schritt weiter gehen und eine Instanz von Applicative erstellen. (Mach dir keine Sorgen, wenn dies keinen Sinn ergibt).

instance Functor Random where
  fmap = liftM

instance Applicative Random where
  pure = return
  (<*>) = ap

Dann könnte randomCombine geschrieben werden:

randomCombine :: Random a -> Random b -> Random (a, b)
randomCombine a b = (,) <$> a <*> b

>>=Nachdem wir diese Instanzen haben, können wir anstelle von randomBind join anstelle von randomJoin fmap anstelle von randomMap return anstelle von randomUnit verwenden. Wir bekommen auch eine ganze Reihe von Funktionen kostenlos.

Ist es das wert? Man könnte argumentieren, dass es ziemlich schwierig und langwierig war, bis zu diesem Punkt zu gelangen, an dem das Arbeiten mit Zufallszahlen nicht völlig horrend ist. Was haben wir dafür bekommen?

Die unmittelbarste Belohnung ist, dass wir jetzt genau sehen können, welche Teile unseres Programms von der Zufälligkeit abhängen und welche Teile vollständig deterministisch sind. Nach meiner Erfahrung vereinfacht das Erzwingen einer strengen Trennung die Dinge ungemein.

Bisher haben wir angenommen, dass wir nur eine einzige Stichprobe aus jeder Zufallsvariablen benötigen, die wir generieren. Wenn sich jedoch herausstellt, dass wir in Zukunft mehr von der Verteilung sehen möchten, ist dies trivial. Sie können runRandom einfach häufig für dieselbe Zufallsvariable mit verschiedenen Startwerten verwenden. Dies ist natürlich in imperativen Sprachen möglich, aber in diesem Fall können wir sicher sein, dass wir nicht jedes Mal, wenn wir eine Zufallsvariable abtasten, eine unerwartete E / A ausführen und wir müssen nicht vorsichtig mit der Initialisierung des Status sein.

Du liegst nicht falsch. Wenn Sie einem RNG zweimal denselben Startwert geben, ist die erste zurückgegebene Pseudozufallszahl dieselbe. Dies hat nichts mit funktionaler oder Nebenwirkungsprogrammierung zu tun. Die Definition eines Seeds ist, dass eine bestimmte Eingabe eine bestimmte Ausgabe gut verteilter, aber entschieden nicht zufälliger Werte verursacht. Das ist der Grund, warum es Pseudozufall genannt wird. Oft ist es eine gute Sache, z. B. vorhersagbare Komponententests zu schreiben, verschiedene Optimierungsmethoden für dasselbe Problem zuverlässig zu vergleichen usw.

Wenn Sie tatsächlich Nicht-Pseudo-Zufallszahlen von einem Computer wollen, müssen Sie sie an etwas wirklich Zufälliges anschließen, wie z. B. eine Partikelverfallsquelle, unvorhersehbare Ereignisse innerhalb des Netzwerks, in dem sich der Computer befindet usw. Richtig und normalerweise teuer, auch wenn es funktioniert, aber es ist die einzige Möglichkeit, keine Pseudozufallswerte zu erhalten (normalerweise basieren die Werte, die Sie aus Ihrer Programmiersprache erhalten, auf einem Startwert , auch wenn Sie keinen explizit angegeben haben.)

Dies und nur dies würde die Funktionsweise eines Systems beeinträchtigen. Da Nicht-Pseudo-Zufallsgeneratoren selten sind, kommt dies nicht oft vor, aber ja, wenn Sie wirklich eine Methode haben, die echte Zufallszahlen generiert, kann zumindest dieses kleine Stück Ihrer Programmiersprache nicht zu 100% funktionsfähig sein. Ob eine Sprache eine Ausnahme machen würde oder nicht, hängt nur davon ab, wie pragmatisch der Sprachimplementierer ist.

Eine Möglichkeit besteht darin, es sich als eine unendliche Folge von Zufallszahlen vorzustellen:

IEnumerable<int> randomNumberGenerator = new RandomNumberGenerator(seed);

Das heißt, stellen Sie es sich einfach als eine bodenlose Datenstruktur vor, wie eine, Stackbei der Sie nur anrufen können Pop, die Sie jedoch für immer aufrufen können. Wie bei einem normalen unveränderlichen Stapel ergibt das Abnehmen eines Stapels einen anderen Stapel.

Ein unveränderlicher Zufallszahlengenerator (mit verzögerter Auswertung) könnte also so aussehen:

class RandomNumberGenerator
{
    private readonly int nextSeed;
    private RandomNumberGenerator next;

    public RandomNumberGenerator(int seed)
    {
        this.nextSeed = this.generateNewSeed(seed);
        this.RandomNumber = this.generateRandomNumberBasedOnSeed(seed);
    }

    public int RandomNumber { get; private set; }

    public RandomNumberGenerator Next
    {
        get
        {
            if(this.next == null) this.next = new RandomNumberGenerator(this.nextSeed);
            return this.next;
        }
    }

    private static int generateNewSeed(int seed)
    {
        //...
    }

    private static int generateRandomNumberBasedOnSeed(int seed)
    {
        //...
    }
}

Das ist funktional.

Dies gilt auch für nicht funktionierende Sprachen. Ignorieren Sie hier das etwas andere Problem der wirklich zufälligen Zahlen.

Ein Zufallszahlengenerator nimmt immer einen Startwert und gibt für denselben Startwert dieselbe Folge von Zufallszahlen zurück (sehr hilfreich, wenn Sie ein Programm testen müssen, das Zufallszahlen verwendet). Grundsätzlich beginnt es mit dem von Ihnen ausgewählten Startwert und verwendet dann das letzte Ergebnis als Startwert für die nächste Iteration. Die meisten Implementierungen sind also "reine" Funktionen, wie Sie sie beschreiben: Nehmen Sie einen Wert und geben Sie für denselben Wert immer dasselbe Ergebnis zurück.