Nondeterminism with Referential Transparency in Functional Programming Languages

0readme.md

The one using a proper PRNG is more typical.

The other one is more like the paper intended, I think, which is to literally run a side-effect on every call to choice (lazy I/O), which is what this does (modulo buffered reads).

other one.hs

import System.IO.Unsafe
import qualified Data.ByteString.Lazy as L
import Data.Char

interleave t xs ys =
  choice t
    (case xs of
      [] -> ys
      (a:xs') -> a : interleave (right t) xs' ys)
    (case ys of
      [] -> xs
      (b:ys') -> b : interleave (right t) xs ys')

right = tail

choice (a:_) x y = if a then x else y

main = do
  t <- mkRandoms
  print $ interleave t [1,2,3,4,5] [6,7,8,9,10]

mkRandoms = do
  l <- L.readFile "/dev/random"
  pure $ map even $ L.unpack l

proper PRNG.hs

import System.Random

interleave t xs ys =
  choice t
    (case xs of
      [] -> ys
      (a:xs') -> a : interleave (right t) xs' ys)
    (case ys of
      [] -> xs
      (b:ys') -> b : interleave (right t) xs ys')

right = tail

choice (a:_) x y = if a then x else y 

main = do
  g <- getStdGen
  let t = randoms g
  print $ interleave t [1,2,3,4,5] [6,7,8,9,10]