Bagaimana bahasa fungsional menangani angka acak?

Maksud saya tentang itu adalah bahwa di hampir setiap tutorial yang saya baca tentang bahasa fungsional, adalah bahwa salah satu hal hebat tentang fungsi, adalah bahwa jika Anda memanggil suatu fungsi dengan parameter yang sama dua kali, Anda akan selalu berakhir dengan hasil yang sama.

Bagaimana Anda bisa membuat fungsi yang menggunakan seed sebagai parameter, dan kemudian mengembalikan nomor acak berdasarkan seed itu?

Maksud saya ini tampaknya bertentangan dengan salah satu hal yang begitu baik tentang fungsi, bukan? Atau apakah saya benar-benar kehilangan sesuatu di sini?

Anda tidak dapat membuat fungsi murni yang disebut randomyang akan memberikan hasil yang berbeda setiap kali dipanggil. Bahkan, Anda bahkan tidak bisa "memanggil" fungsi murni. Anda menerapkannya. Jadi Anda tidak melewatkan apa pun, tetapi ini tidak berarti bahwa angka acak terlarang dalam pemrograman fungsional. Izinkan saya menunjukkan, saya akan menggunakan seluruh sintaksis Haskell.

Berasal dari latar belakang imperatif, Anda mungkin awalnya berharap memiliki tipe seperti ini:

random :: () -> Integer

Tapi ini sudah dikesampingkan karena acak tidak bisa menjadi fungsi murni.

Pertimbangkan gagasan tentang suatu nilai. Nilai adalah hal yang tidak dapat diubah. Itu tidak pernah berubah dan setiap pengamatan yang dapat Anda lakukan konsisten untuk selamanya.

Jelas, acak tidak dapat menghasilkan nilai Integer. Sebaliknya, ini menghasilkan variabel acak Integer. Jenisnya mungkin terlihat seperti ini:

random :: () -> Random Integer

Kecuali bahwa menyampaikan argumen sama sekali tidak perlu, fungsinya murni, jadi satu random ()sama baiknya dengan yang lain random (). Saya akan berikan secara acak, mulai dari sini, jenis ini:

random :: Random Integer

Semua baik-baik saja, tetapi tidak terlalu berguna. Anda mungkin berharap dapat menulis ekspresi seperti random + 42, tetapi Anda tidak bisa, karena itu tidak akan mengetik centang. Anda belum dapat melakukan apa pun dengan variabel acak.

Ini menimbulkan pertanyaan menarik. Fungsi apa yang harus ada untuk memanipulasi variabel acak?

Fungsi ini tidak bisa ada:

bad :: Random a -> a

dengan cara apa pun yang bermanfaat, karena Anda dapat menulis:

badRandom :: Integer
badRandom = bad random

Yang memperkenalkan inkonsistensi. badRandom seharusnya merupakan nilai, tetapi juga merupakan angka acak; sebuah kontradiksi.

Mungkin kita harus menambahkan fungsi ini:

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

Tapi ini hanya kasus khusus dari pola yang lebih umum. Anda harus dapat menerapkan fungsi apa pun ke hal acak untuk mendapatkan hal-hal acak lainnya seperti:

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

Alih-alih menulis random + 42, kita sekarang dapat menulis randomMap (+42) random.

Jika yang Anda miliki adalah randomMap, Anda tidak akan dapat menggabungkan variabel acak menjadi satu. Misalnya, Anda tidak dapat menulis fungsi ini:

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

Anda dapat mencoba menulisnya seperti ini:

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

Tetapi memiliki tipe yang salah. Alih-alih berakhir dengan Random (a, b), kita berakhir dengan aRandom (Random (a, b))

Ini dapat diperbaiki dengan menambahkan fungsi lain:

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

Tapi, untuk alasan yang akhirnya menjadi jelas, saya tidak akan melakukan itu. Alih-alih, saya akan menambahkan ini:

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

Tidak segera jelas bahwa ini sebenarnya memecahkan masalah, tetapi memang:

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

Bahkan, dimungkinkan untuk menulis RandomBind dalam hal randomJoin dan randomMap. Dimungkinkan juga untuk menulis randomJoin dalam hal randomBind. Tapi, saya akan meninggalkan melakukan ini sebagai latihan.

Kita bisa menyederhanakan ini sedikit. Izinkan saya mendefinisikan fungsi ini:

randomUnit :: a -> Random a

randomUnit mengubah nilai menjadi variabel acak. Ini artinya kita dapat memiliki variabel acak yang sebenarnya bukan acak. Namun, ini selalu terjadi; kita bisa melakukannya randomMap (const 4) randomsebelumnya. Alasan mendefinisikan randomUnit adalah ide yang bagus adalah bahwa sekarang kita dapat mendefinisikan randomMap dalam hal randomUnit dan randomBind:

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

Ok, sekarang kita sudah sampai di suatu tempat. Kami memiliki variabel acak yang dapat kami manipulasi. Namun:

• Tidak jelas bagaimana kita sebenarnya mengimplementasikan fungsi-fungsi ini,
• Cukup merepotkan.

Penerapan

Saya akan menangani nomor acak palsu. Mungkin saja menerapkan fungsi-fungsi ini untuk angka acak nyata, tetapi jawaban ini sudah cukup lama.

Pada dasarnya, cara ini akan bekerja adalah bahwa kita akan memberikan nilai unggulan di mana-mana. Setiap kali kami menghasilkan nilai acak baru, kami akan menghasilkan benih baru. Pada akhirnya, ketika kita selesai membangun variabel acak, kita ingin mengambil sampel darinya menggunakan fungsi ini:

runRandom :: Seed -> Random a -> a

Saya akan mendefinisikan tipe acak seperti ini:

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

Kemudian, kita hanya perlu menyediakan implementasi dari randomUnit, randomBind, runRandom dan random yang cukup mudah:

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

Secara acak, saya akan menganggap sudah ada fungsi dari tipe:

psuedoRandom :: Seed -> (Seed, Integer)

Dalam hal ini acak adalah adil Random psuedoRandom.

Membuat hal-hal menjadi kurang rumit

Haskell memiliki gula sintaksis untuk membuat hal-hal seperti ini lebih bagus di mata. Ini disebut notasi dan untuk menggunakannya, kita harus membuat instance Monad untuk Acak.

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

Selesai. randomCombinedari sebelumnya sekarang dapat ditulis:

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

Jika saya melakukan ini untuk diri saya sendiri, saya bahkan akan melangkah lebih jauh dari ini dan membuat contoh dari Applicative. (Jangan khawatir jika ini tidak masuk akal).

instance Functor Random where
  fmap = liftM

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

Maka randomCombine dapat ditulis:

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

Sekarang kita memiliki contoh-contoh ini, kita dapat menggunakan >>=alih-alih randomBind, bergabung bukan randomJoin, fmap bukan randomMap, kembali bukan randomUnit. Kami juga mendapatkan seluruh fungsi secara gratis.

Apakah itu layak? Anda bisa berargumen, bahwa sampai ke tahap ini, di mana bekerja dengan angka acak tidak sepenuhnya menghebohkan itu cukup sulit dan bertele-tele. Apa yang kita dapatkan sebagai imbalan atas upaya ini?

Hadiah yang paling langsung adalah bahwa kita sekarang dapat melihat bagian mana dari program kita yang bergantung pada keacakan dan bagian mana yang sepenuhnya deterministik. Dalam pengalaman saya, memaksakan pemisahan yang ketat seperti ini sangat menyederhanakan hal-hal.

Kami berasumsi sejauh ini bahwa kami hanya ingin sampel tunggal dari setiap variabel acak yang kami hasilkan, tetapi jika ternyata di masa depan kami benar-benar ingin melihat lebih banyak dari distribusi, ini sepele. Anda bisa menggunakan runRandom berkali-kali pada variabel acak yang sama dengan seed yang berbeda. Ini, tentu saja, mungkin dalam bahasa imperatif, tetapi dalam kasus ini, kita dapat yakin bahwa kita tidak akan melakukan IO yang tidak diantisipasi setiap kali kita mengambil sampel variabel acak dan kita tidak perlu berhati-hati dalam menginisialisasi keadaan.

Kamu tidak salah. Jika Anda memberikan seed yang sama ke RNG dua kali, maka nomor pseudo-acak pertama yang dikembalikan akan sama. Ini tidak ada hubungannya dengan pemrograman fungsional vs efek samping; yang definisi dari benih adalah bahwa input tertentu menyebabkan output spesifik nilai-nilai baik-didistribusikan tapi jelas non-acak. Itu sebabnya ini disebut pseudo-random, dan sering kali merupakan hal yang baik untuk dimiliki, misalnya menulis unit test yang dapat diprediksi, untuk secara andal membandingkan berbagai metode optimasi pada masalah yang sama, dll.

Jika Anda benar-benar menginginkan nomor non-pseudo-acak dari komputer, Anda harus menghubungkannya ke sesuatu yang benar-benar acak, seperti sumber peluruhan partikel, peristiwa tak terduga yang terjadi dalam jaringan di mana komputer itu aktif, dll. Ini sulit untuk mendapatkan yang benar dan biasanya mahal meskipun itu berfungsi, tetapi itu adalah satu-satunya cara untuk tidak mendapatkan nilai pseudo-acak (biasanya nilai yang Anda terima dari bahasa pemrograman Anda didasarkan pada beberapa seed, bahkan jika Anda tidak secara eksplisit menyediakannya.)

Ini, dan hanya ini, yang akan mengkompromikan sifat fungsional suatu sistem. Karena generator non-pseudo-acak jarang, ini tidak sering muncul, tetapi ya, jika Anda benar-benar memiliki metode menghasilkan angka acak yang benar, maka setidaknya sedikit bahasa pemrograman Anda tidak dapat 100% berfungsi murni. Apakah suatu bahasa akan membuat pengecualian untuk itu atau tidak hanyalah pertanyaan tentang seberapa pragmatisnya pelaksana bahasa.

Salah satu caranya adalah dengan menganggapnya sebagai urutan tak terhingga dari angka acak:

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

Artinya, anggap saja sebagai struktur data tanpa dasar, seperti Stacktempat Anda hanya bisa menelepon Pop, tetapi Anda bisa menyebutnya selamanya. Seperti tumpukan normal yang tidak dapat diubah, melepaskan salah satu dari atas memberi Anda tumpukan lain (berbeda).

Jadi generator angka acak yang tidak berubah (dengan evaluasi malas) mungkin terlihat seperti:

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

Itu fungsional.

Itu sama untuk bahasa yang tidak fungsional. Mengabaikan masalah sedikit terpisah dari angka yang benar-benar acak di sini.

Generator angka acak selalu mengambil nilai seed dan untuk seed yang sama mengembalikan urutan angka acak yang sama (sangat membantu jika Anda perlu menguji program yang menggunakan angka acak). Pada dasarnya ini dimulai dengan seed yang Anda pilih dan kemudian menggunakan hasil terakhir sebagai seed untuk iterasi berikutnya. Jadi sebagian besar implementasi adalah fungsi "murni" seperti yang Anda gambarkan: Ambil nilai dan untuk nilai yang sama selalu kembalikan hasil yang sama.