Wie gehen funktionale Sprachen mit Zufallszahlen um?

68

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?

Elektrischer Kaffee
quelle

Antworten:

89

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.

dan_waterworth
quelle
6
+1 für ein gutes Beispiel für die praktische Verwendung von Applicative functors / Monads.
Jozefg
9
Nette Antwort, aber mit einigen Schritten geht es etwas zu schnell. Warum sollte bad :: Random a -> aman beispielsweise Inkonsistenzen einführen? Was ist daran schlecht? Bitte gehen Sie langsam in der Erklärung vor, insbesondere für die ersten Schritte :) Wenn Sie erklären könnten, warum die "nützlichen" Funktionen nützlich sind, könnte dies eine 1000-Punkte-Antwort sein! :)
Andres F.
@AndresF. Ok, ich werde es ein wenig überarbeiten.
Dan_waterworth
1
@AndresF. Ich habe meine Antwort überarbeitet, aber ich glaube nicht, dass ich ausreichend erklärt habe, wie Sie dies anwenden können, um später darauf zurückzukommen.
Dan_waterworth
3
Bemerkenswerte Antwort. Ich bin kein funktionaler Programmierer, aber ich verstehe die meisten Konzepte und habe mit Haskell "gespielt". Dies ist die Art der Antwort, die sowohl den Fragesteller informiert als auch andere dazu inspiriert, tiefer in das Thema einzutauchen und mehr darüber zu erfahren. Ich wünschte, ich könnte Ihnen bei meiner Gegenstimme ein paar zusätzliche Punkte über 10 geben.
RLH
10

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.

Kilian Foth
quelle
9
Ein echtes RNG kann überhaupt kein Computerprogramm sein, unabhängig davon, ob es rein (funktional) ist oder nicht. Wir alle kennen das von Neumann-Zitat über arithmetische Methoden zur Erzeugung von Zufallszahlen (diejenigen, die dies nicht tun, schlagen es nach - vorzugsweise das Ganze, nicht nur den ersten Satz). Sie müssen mit nicht deterministischer Hardware interagieren, was natürlich auch unrein ist. Aber das ist nur I / O, das in sehr unterschiedlichen Wans mehrmals mit Reinheit in Einklang gebracht wurde. Keine Sprache, die in irgendeiner Weise verwendbar ist, verbietet E / A vollständig - Sie könnten nicht einmal das Ergebnis des Programms sehen, wenn dies nicht der Fall wäre.
Was ist mit der Down-Abstimmung?
l0b0
6
Warum würde eine externe und wirklich zufällige Quelle die Funktionsweise des Systems beeinträchtigen? Es ist immer noch "der gleiche Eingang -> der gleiche Ausgang". Es sei denn, Sie betrachten die externe Quelle als Teil des Systems, aber dann wäre es nicht "extern", oder?
Andres F.
4
Dies hat nichts mit PRNG vs TRNG zu tun. Sie können keine nicht konstante Funktion vom Typ haben () -> Integer. Sie können einen rein funktionalen PRNG-Typ haben PRNG_State -> (PRNG_State, Integer), müssen ihn jedoch mit unreinen Mitteln initialisieren.
Gilles
4
@Brian Einverstanden, aber die Formulierung ("hakt es auf etwas wirklich zufälliges") deutet darauf hin, dass die zufällige Quelle außerhalb des Systems liegt. Daher bleibt das System selbst rein funktional; es ist die Eingabequelle, die nicht ist.
Andres F.
6

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.

Scott Whitlock
quelle
Ich sehe nicht , wie eine unendliche Liste von Zufallszahlen zu schaffen ist einfacher zu arbeiten als mit Funktionen wie: pseudoRandom :: Seed -> (Seed, Integer). Möglicherweise schreiben Sie sogar eine Funktion dieses Typs[Integer] -> ([Integer], Integer)
dan_waterworth
2
@ dan_waterworth eigentlich macht es sehr viel sinn. Eine ganze Zahl kann nicht als zufällig bezeichnet werden. Eine Liste von Nummern kann diesen Schutz haben. Die Wahrheit ist, dass ein Zufallsgenerator den Typ int -> [int] haben kann, dh eine Funktion, die einen Startwert nimmt und eine zufällige Liste von Ganzzahlen zurückgibt. Sicher, Sie können eine staatliche Monade haben, um die Notation von haskell's do zu erhalten. Aber als allgemeine Antwort auf die Frage halte ich das für sehr hilfreich.
Simon Bergot
5

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.

thorsten müller
quelle