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

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?

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.

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.

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.

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.