How and when to use State functor and State applicative?

I've seen the Maybe and Either functor (and applicative) used in code and that made sense, but I have a hard time coming up with an example of the State functor and applicative. Maybe they are not very useful and only exist because the State monad requires a functor and an applicative? There are plenty of explanations of their implementations out there but not any examples when they are used in code, so I'm looking for illustrations of how they might be useful on their own.

Solution

I can think of a couple of examples off the top of my head.

First, one common use for State is to manage a counter for the purpose of making some set of "identifiers" unique. So, the state itself is an Int, and the main primitive state operation is to retrieve the current value of the counter and increment it:

-- the state
type S = Int

newInt :: State S Int
newInt = state (\s -> (s, s+1))

The functor instance is then a succinct way of using the same counter for different types of identifiers, such as term- and type-level variables in some language:

type Prefix = String
data Var = Var Prefix Int
data TypeVar = TypeVar Prefix Int

where you generate fresh identifiers like so:

newVar :: Prefix -> State S Var
newVar s = Var s <$> newInt

newTypeVar :: Prefix -> State S TypeVar
newTypeVar s = TypeVar s <$> newInt

The applicative instance is helpful for writing expressions constructed from such unique identifiers. For example, I've used this approach pretty frequently when writing type checkers, which will often construct types with fresh variables, like so:

typeCheckAFunction = ...
    let freshFunctionType = ArrowType <$> newTypeVar <*> newTypeVar
    ...

Here, freshFunctionType is a new a -> b style type with fresh type variables a and b that can be passed along to a unification step.

Second, another use of State is to manage a seed for random number generation. For example, if you want a low-quality but ultra-fast LCG generator for something, you can write:

lcg :: Word32 -> Word32
lcg x = (a * x + c)
  where a = 1664525
        c = 1013904223

-- monad for random numbers
type L = State Word32

randWord32 :: L Word32
randWord32 = state $ \s -> let s' = lcg s in (s', s')

The functor instance can be used to modify the Word32 output using a pure conversion function:

randUniform :: L Double
randUniform = toUnit <$> randWord32
  where toUnit w = fromIntegral w / fromIntegral (maxBound `asTypeOf` w)

while the applicative instance can be used to write primitives that depend on multiple Word32 outputs:

randUniform2 :: L (Double, Double)
randUniform2 = (,) <$> randUniform  <*> randUniform

and expressions that use your random numbers in a reasonably natural way:

-- area of a random triangle, say
a = areaOf <$> (Triangle <$> randUniform2 <*> randUniform2 <$> randUniform2)