How do I use the Supply monad to create a function that generates globally unique names?

Question

Background:

I'm doing a code translation project that requires me to generate variable names. None of the names I generate should be duplicates of each other.

I'm really frustrated since this would be stupidly simple and elegant with a Python generator function.

What I've tried:

The way I was doing it before was to pass a counter variable down through recursive calls to my translate code, and pass the (possibly incremented) counter back up in the return value of basically every function.

This was really messy: it added an extra parameter to keep track of to each of these functions; and worse still it forced me to work with messy tuple return values where I would otherwise have a simple unary return value.

I've never really gotten proficient with monads in my short time with Haskell, but I had an inkling that I could use a wrapper on the State monad to simulate a global counter variable. After 3 days of messing around trying to grok monads and make one of my own, then trying to alter someone else's monads to generate the values I needed, I've finally resigned myself to straight-up using someone else's high-level monad (perhaps with a few alterations.)

My problem now:

I've identified the MonadSupply and MonadUnique modules as a couple which likely provide the simple kind of interface I need. Unfortunately I can't figure out how to use them.

In particular the MonadSupply module documentation provides this nice example use case:

runSupplyVars x = runSupply x vars
    where vars = [replicate k ['a'..'z'] | k <- [1..]] >>= sequence

Looks like what I want! Once I got the module to compile I checked the type of this function in the interpreter:

> :t runSupplyVars
runSupplyVars :: Supply [Char] a -> Identity (a, [[Char]])

I've tried passing lots (hours worth) of different things to this function, with no success. I also tried passing the function to some various other functions to see if they would provide the parameters I needed implicitly. No luck so far.

The Questions:

Could someone please provide an example use case of this runSupplyVars function?

Would it be possible to do what I'm thinking with it? I want to have a function I can call from anywhere in the program, which will provide me with a different variable name or integer on each call.

Answer 1

To actually use the Supply monad you should structure your code with do notation and call the supply function when you actually need a name.

For example, this will produce a new variable name prefixed with var_, just to show how you might get something from the supply and use it:

newVar :: Supply [Char] [Char]
newVar = do
    name <- supply
    return ("var"_++name)

You'll need to structure your whole program around the Supply monad and then only call runSupplyVars once at the top-level, otherwise different parts of the program will have independent supplies and so might reuse the same variable name.

Finally, you'll need runIdentity from Control.Monad.Identity to unpack the result of runSupplyVars into the underlying tuple of type (a, [[Char]]), and then throw away the second value which is just the (infinite) list of unused names. You might be better off redefining runSupplyVars to do this for you:

import Control.Monad.Identity

[...]

runSupplyVars :: Supply [Char] a -> a
runSupplyVars x = fst (runIdentity (runSupply x vars))
    where vars = [replicate k ['a'..'z'] | k <- [1..]] >>= sequence

Here's a more complete example putting it all together. Note the different monads with which do notation is used - IO for the main function, and Supply [Char] for realProgram and probably most of the rest of the code in a bigger version:

import MonadSupply
import Control.Monad.Identity

main :: IO ()
main = do
    let result = runSupplyVars realProgram
    print result

realProgram :: Supply [Char] Int
realProgram = do
    x <- newVar
    return 0

newVar :: Supply [Char] [Char]
newVar = do
    name <- supply
    return ("var_"++name)

runSupplyVars :: Supply [Char] a -> a
runSupplyVars x = fst (runIdentity (runSupply x vars))
    where vars = [replicate k ['a'..'z'] | k <- [1..]] >>= sequence