Type inference F# - how to generate fresh variables?

Question

i'm trying to develop the algorithm W in f# for type inference, but i would like to understand how to write the function for generating fresh variables properly.

Actually my function is

let counter = ref -1

let generate_fresh_variable () : string =
    let list_variables = ['a' .. 'z'] |> List.map string
    counter.Value <- !counter + 1
    list_variables.Item(!counter)

but i'm not satisfy with this solution, someone can give me other better ideas?

Answer 1

If you wanted to use some more sophisticated F# tricks, you could create an inifinte sequence of names using a sequence expression (which makes it very easy to handle the looping and dealing with >26 names):

let names = seq {
  for i in Seq.initInfinite id do
    for c in 'a' .. 'z' do
      if i = 0 then yield string c
      else yield string c + string i }

A function to get the fresh name would then pick the next name from the sequence. You need to do this using the underlying enumerator. Another nice trick is to hide the state in a local variable and return a function using lambda:

let freshName = 
  let en = names.GetEnumerator()
  fun () -> 
    ignore(en.MoveNext())
    en.Current

Then just call freshName() as many times as you need.

Answer 2

If you really want to do this with an impure function, I would write it like this:

let mutable counter = -1

let generate_fresh_variable () =
    counter <- counter + 1
    counter + int 'a'
        |> char
        |> string

Notes:

• Reference cells are obsolete. If you need impurity, use mutable variables instead. (Alternatively, if you really want to stick with a reference cell, the canonical way to update it is with :=, rather than assigning directly to the underlying Value.)
• There's no need to maintain a list of potential variable names (and there's especially no need to rebuild the entire list each time you generate a fresh variable).
• What happens if you need more than 26 variables?