Jak języki funkcjonalne obsługują liczby losowe?

68

Chodzi mi o to, że w prawie każdym samouczku, który przeczytałem o językach funkcjonalnych, jedną z wielkich rzeczy o funkcjach jest to, że jeśli wywołasz funkcję o tych samych parametrach dwa razy, zawsze skończysz na ten sam wynik.

Jak u licha wykonujesz funkcję, która przyjmuje ziarno jako parametr, a następnie zwraca losową liczbę na podstawie tego ziarna?

Wydaje mi się, że byłoby to sprzeczne z jedną z tak dobrych funkcji, prawda? A może coś mi tu brakuje?

Kawa elektryczna
źródło

Odpowiedzi:

89

Nie można utworzyć czystej funkcji o nazwie random, która da inny wynik przy każdym wywołaniu. W rzeczywistości nie można nawet „wywoływać” czystych funkcji. Stosujesz je. Więc niczego nie brakuje, ale to nie znaczy, że liczby losowe są w programowaniu funkcjonalnym niedostępne. Pozwólcie mi zademonstrować, będę używać składni Haskell przez cały czas.

Pochodząc z imperatywnego tła, możesz początkowo oczekiwać, że losowy będzie mieć taki typ:

random :: () -> Integer

Ale zostało to już wykluczone, ponieważ losowość nie może być czystą funkcją.

Rozważ pomysł wartości. Wartość jest niezmienną rzeczą. Nigdy się nie zmienia, a każda obserwacja, którą możesz zrobić, jest spójna przez cały czas.

Oczywiście losowe nie może wygenerować wartości całkowitej. Zamiast tego tworzy losową zmienną całkowitą. Jego typ może wyglądać następująco:

random :: () -> Random Integer

Tyle, że przekazywanie argumentów jest całkowicie niepotrzebne, funkcje są czyste, więc jeden random ()jest tak samo dobry jak drugi random (). Od tego momentu dam losowy ten typ:

random :: Random Integer

Co jest w porządku, ale niezbyt przydatne. Możesz spodziewać się, że będziesz w stanie pisać wyrażenia takie jak random + 42, ale nie możesz, bo to nie sprawdzi typu. Nie możesz jeszcze nic zrobić z losowymi zmiennymi.

Rodzi to interesujące pytanie. Jakie funkcje powinny istnieć, aby manipulować zmiennymi losowymi?

Ta funkcja nie może istnieć:

bad :: Random a -> a

w dowolny użyteczny sposób, ponieważ wtedy możesz napisać:

badRandom :: Integer
badRandom = bad random

Co wprowadza niespójność. badRandom jest podobno wartością, ale jest także liczbą losową; sprzeczność.

Może powinniśmy dodać tę funkcję:

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

Ale to tylko specjalny przypadek o bardziej ogólnym wzorze. Powinieneś być w stanie zastosować dowolną funkcję do losowej rzeczy, aby uzyskać inne losowe rzeczy, takie jak:

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

Zamiast pisać random + 42, możemy teraz pisać randomMap (+42) random.

Jeśli wszystko, co miałeś, to randomMap, nie byłbyś w stanie połączyć losowych zmiennych razem. Nie można na przykład napisać tej funkcji:

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

Możesz spróbować napisać to w ten sposób:

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

Ale ma zły typ. Zamiast skończyć na Random (a, b), kończymy naRandom (Random (a, b))

Można to naprawić, dodając inną funkcję:

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

Ale z powodów, które mogą w końcu stać się jasne, nie zamierzam tego robić. Zamiast tego dodam to:

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

Nie jest od razu oczywiste, że to faktycznie rozwiązuje problem, ale robi to:

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

W rzeczywistości możliwe jest napisanie randomBind w kategoriach randomJoin i randomMap. Możliwe jest również napisanie randomJoin pod względem randomBind. Ale zostawię robienie tego jako ćwiczenie.

Możemy to trochę uprościć. Pozwól mi zdefiniować tę funkcję:

randomUnit :: a -> Random a

randomUnit zamienia wartość w zmienną losową. Oznacza to, że możemy mieć losowe zmienne, które tak naprawdę nie są losowe. Zawsze tak było; mogliśmy zrobić randomMap (const 4) randomwcześniej. Powodem zdefiniowania randomUnit jest dobry pomysł, ponieważ teraz możemy zdefiniować randomMap w kategoriach randomUnit i randomBind:

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

Ok, teraz gdzieś idziemy. Mamy losowe zmienne, którymi możemy manipulować. Jednak:

  • Nie jest oczywiste, jak moglibyśmy faktycznie wdrożyć te funkcje,
  • To dość kłopotliwe.

Realizacja

Zajmę się pseudolosowymi liczbami. Możliwe jest zaimplementowanie tych funkcji dla rzeczywistych liczb losowych, ale ta odpowiedź jest już dość długa.

Zasadniczo sposób, w jaki to ma działać, polega na tym, że wszędzie będziemy przekazywać wartość zalążkową. Za każdym razem, gdy generujemy nową losową wartość, wytwarzamy nowe ziarno. Na koniec, kiedy skończymy konstruować zmienną losową, będziemy chcieli z niej próbkować za pomocą tej funkcji:

runRandom :: Seed -> Random a -> a

Zdefiniuję typ Losowy w ten sposób:

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

Następnie musimy jedynie wprowadzić implementacje randomUnit, randomBind, runRandom i random, co jest dość proste:

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

Przypadkowo zakładam, że istnieje już funkcja tego typu:

psuedoRandom :: Seed -> (Seed, Integer)

W takim przypadku losowość jest sprawiedliwa Random psuedoRandom.

Sprawia, że ​​rzeczy stają się mniej kłopotliwe

Haskell ma cukier syntaktyczny, dzięki czemu takie rzeczy są ładniejsze dla oczu. Nazywa się to notowaniem i aby użyć go wszystko, co trzeba, należy utworzyć instancję Monady dla Random.

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

Gotowy. randomCombinez przeszłości można teraz napisać:

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

Gdybym to robił dla siebie, poszedłbym nawet o krok dalej i stworzyłby przykład aplikacji. (Nie martw się, jeśli nie ma to sensu).

instance Functor Random where
  fmap = liftM

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

Następnie można napisać randomCombine:

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

Teraz, gdy mamy już te instancje, możemy użyć >>=zamiast randomBind, łączyć zamiast randomJoin, fmap zamiast randomMap, return zamiast randomUnit. Otrzymujemy również cały zestaw funkcji za darmo.

Czy warto? Można argumentować, że dotarcie do tego etapu, w którym praca z liczbami losowymi nie jest całkowicie przerażające, było dość trudne i długotrwałe. Co otrzymaliśmy w zamian za ten wysiłek?

Najbardziej natychmiastową nagrodą jest to, że możemy teraz dokładnie zobaczyć, które części naszego programu zależą od losowości, a które są całkowicie deterministyczne. Z mojego doświadczenia, wymuszanie ścisłej separacji bardzo upraszcza rzeczy.

Do tej pory zakładaliśmy, że chcemy tylko jednej próbki z każdej generowanej zmiennej losowej, ale jeśli okaże się, że w przyszłości chcielibyśmy zobaczyć więcej rozkładu, jest to trywialne. Możesz po prostu używać runRandom wiele razy na tej samej losowej zmiennej z różnymi nasionami. Jest to oczywiście możliwe w imperatywnych językach, ale w tym przypadku możemy być pewni, że nie będziemy wykonywać nieprzewidzianych operacji we / wy za każdym razem, gdy próbkujemy zmienną losową i nie musimy uważać na inicjalizację stanu.

dan_waterworth
źródło
6
+1 za dobry przykład praktycznych zastosowań funktorów aplikacyjnych / monad.
jozefg
9
Dobra odpowiedź, ale niektóre kroki idą trochę za szybko. Na przykład dlaczego bad :: Random a -> awprowadzać niespójności? Co w tym złego? Powoli postępuj w wyjaśnieniu, szczególnie w przypadku pierwszych kroków :) Jeśli możesz wyjaśnić, dlaczego przydatne są „przydatne” funkcje, może to być odpowiedź 1000 punktów! :)
Andres F.
@AndresF. Ok, trochę to poprawię.
dan_waterworth
1
@AndresF. Poprawiłem swoją odpowiedź, ale nie sądzę, że wystarczająco wyjaśniłem, w jaki sposób możesz wykorzystać tę praktykę, więc mogę do niej wrócić później.
dan_waterworth
3
Niezwykła odpowiedź. Nie jestem programistą funkcjonalnym, ale rozumiem większość pojęć i „grałem” z Haskellem. Jest to rodzaj odpowiedzi, która zarówno informuje pytającego, jak i inspiruje innych do głębszego kopania i zdobywania dodatkowych informacji na ten temat. Chciałbym dać państwu kilka dodatkowych punktów powyżej 10 z mojego głosowania w górę.
RLH
10

Nie mylisz się Jeśli podasz RNG ten sam materiał siewny dwa razy, wówczas pierwsza zwracana liczba pseudolosowa będzie taka sama. Nie ma to nic wspólnego z programowaniem funkcjonalnym vs. programowaniem efektów ubocznych; definicji z nasion jest specyficzny wejściowego powoduje określone wyjście dobrze rozłożonych lecz zdecydowanie nielosowych wartości. Dlatego nazywa się to pseudolosowym i często dobrze jest mieć np. Pisanie przewidywalnych testów jednostkowych, aby niezawodnie porównywać różne metody optymalizacji tego samego problemu itp.

Jeśli naprawdę chcesz liczb niepseudolosowych z komputera, musisz podłączyć je do czegoś naprawdę losowego, takiego jak źródło rozpadu cząstek, nieprzewidywalne zdarzenia występujące w sieci, w której znajduje się komputer itp. Trudno to być poprawnym i zwykle drogim, nawet jeśli działa, ale jest to jedyny sposób, aby nie uzyskać pseudolosowych wartości (zwykle wartości, które otrzymujesz z twojego języka programowania, są oparte na pewnym ziarnie, nawet jeśli nie podałeś go wyraźnie).

To i tylko to zagroziłoby funkcjonalnej naturze systemu. Ponieważ generatory niepseudolosowe są rzadkie, nie pojawia się to często, ale tak, jeśli naprawdę masz metodę generowania prawdziwych liczb losowych, to przynajmniej odrobina twojego języka programowania nie może być w 100% czysta funkcjonalna. To, czy język byłby dla niego wyjątkiem, jest tylko pytaniem o to, jak pragmatyczny jest implementator języka.

Kilian Foth
źródło
9
Prawdziwy RNG nie może być wcale programem komputerowym, niezależnie od tego, czy jest czysty (funkcjonalnie), czy nie. Wszyscy znamy cytat von Neumanna o arytmetycznych metodach tworzenia losowych cyfr (ci, którzy tego nie robią, spójrz na to - najlepiej cała rzecz, nie tylko pierwsze zdanie). Będziesz musiał wchodzić w interakcje z jakimś niedeterministycznym sprzętem, co oczywiście jest również nieczyste. Ale to tylko I / O, które kilkakrotnie pogodziło się z czystością na bardzo różnych planach. Żaden język, który jest w jakikolwiek sposób użyteczny, całkowicie nie zezwala na operacje wejścia / wyjścia - w przeciwnym razie nie można było zobaczyć wyniku programu.
O co chodzi z głosowaniem w dół?
l0b0
6
Dlaczego zewnętrzne i naprawdę losowe źródło naraziłoby funkcjonalną naturę systemu? To wciąż „to samo wejście -> to samo wyjście”. Chyba że uważasz zewnętrzne źródło za część systemu, ale nie byłoby to „zewnętrzne”, prawda?
Andres F.,
4
Nie ma to nic wspólnego z PRNG a TRNG. Nie możesz mieć nie stałej funkcji typu () -> Integer. Możesz mieć czysto funkcjonalny PRNG typu PRNG_State -> (PRNG_State, Integer), ale będziesz musiał zainicjować go za pomocą nieczystych środków).
Gilles
4
@Brian zgodził się, ale sformułowanie („podłącz to do czegoś naprawdę losowego”) sugeruje, że losowe źródło jest zewnętrzne względem systemu. Dlatego sam system pozostaje czysto funkcjonalny; jest to źródło wejściowe, które nie jest.
Andres F.,
6

Jednym ze sposobów jest myślenie o tym jako o nieskończonej sekwencji liczb losowych:

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

To znaczy, pomyśl o tym jak o strukturze danych bez dna, jak o Stackmiejscu, w którym możesz tylko dzwonić Pop, ale możesz to nazwać na zawsze. Jak normalny niezmienny stos, zdjęcie jednego z wierzchu daje inny (inny) stos.

Tak więc niezmienny (z leniwą oceną) generator liczb losowych może wyglądać następująco:

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)
    {
        //...
    }
}

To funkcjonalne.

Scott Whitlock
źródło
Nie widzę, w jaki sposób tworzyć nieskończoną listę liczb losowych jest łatwiej pracować niż funkcji, takich jak: pseudoRandom :: Seed -> (Seed, Integer). Możesz nawet napisać funkcję tego typu[Integer] -> ([Integer], Integer)
dan_waterworth
2
@dan_waterworth faktycznie ma to sens. Nie można powiedzieć, że liczba całkowita jest losowa. Lista liczb może mieć tego protperty. Tak więc prawda jest taka, że ​​generator losowy może mieć typ int -> [int], tj. Funkcję, która pobiera ziarno i zwraca losową listę liczb całkowitych. Jasne, możesz mieć wokół tego monadę stanu, aby uzyskać notację haskell. Ale jako ogólna odpowiedź na pytanie, myślę, że jest to naprawdę pomocne.
Simon Bergot
5

To samo dotyczy języków niefunkcjonalnych. Ignorując tutaj nieco odrębny problem naprawdę losowych liczb.

Generator liczb losowych zawsze przyjmuje wartość początkową i dla tego samego ziarna zwraca tę samą sekwencję liczb losowych (bardzo pomocne, jeśli trzeba przetestować program, który używa liczb losowych). Zasadniczo zaczyna się od wybranego ziarna, a następnie wykorzystuje ostatni wynik jako ziarno do następnej iteracji. Dlatego większość implementacji to „czyste” funkcje, gdy je opisujesz: weź wartość i dla tej samej wartości zawsze zwracaj ten sam wynik.

Thorsten Müller
źródło