Fresh name generation in Haskell.

Fresh.hs

import Control.Monad.State

-- `Linear a b` reperesents `\x -> a * x + b`.
data Linear = Linear !Int !Int

-- Represents `\x -> x`.
idLinear :: Linear
idLinear = Linear 1 0

-- Interprets the `Linear` value.
runLinear :: Linear -> Int -> Int
runLinear (Linear a b) x = a * x + b

-- `nextLinear a` represents `runLinear a . (+1)`.
nextLinear :: Linear -> Linear
nextLinear (Linear a b) = Linear a (a + b)

-- `evenLinear a` represents `runLinear a . (*2)`.
evenLinear :: Linear -> Linear
evenLinear (Linear a b) = Linear (2 * a) b

-- `oddLinear a` represents `runLinear a . (+1) . (*2)`.
oddLinear :: Linear -> Linear
oddLinear = evenLinear . nextLinear

data Id = Id !Int deriving (Show, Eq)
newtype Gen = Gen Linear

initial :: Gen
initial = Gen idLinear

split :: Gen -> (Gen, Gen)
split (Gen x) = (Gen (evenLinear x), Gen (oddLinear x))

gen :: Gen -> (Id, Gen)
gen (Gen x) = (Id (runLinear x 0), Gen (nextLinear x))

type Fresh a = State Gen a

fresh :: Fresh Id
fresh = do (id, gen') <- gets gen
           modify (const gen')
           return id
           
parallel :: Fresh a -> Fresh b -> Fresh (a, b)
parallel a b = do (g0, g1) <- gets split
                  let (g2, g3) = split g0
                      (x, _)   = runState a g2
                      (y, _)   = runState b g3
                  modify (const g1)
                  return (x, y)