1

So, I'm trying to make a function to rename variables in a Lambda Calculus expression, but I can't seem to figure out how to get a Char that's not already in use so I can set it as the new name to a variable.

I've already got a list with all the Chars that are being used as names to variables, so what I need is just a function that receives this list e returns a differnt Char, i.e. one that's not in use.

A function like that:

getNewVarName :: [Char] -> Char

I don't really use lists, or Haskell, for that matter, so I hope you can excuse my silly question.

// Edit 1

-- acceptableNames is passed as the second argument to getNewVarName
acceptableNames = ['a'..'z'] ++ ['A'..'Z']

getNewVarName :: [Char] -> [Char] -> Char
-- vars is the list with all the names actually being used
-- acceptable == acceptableNames
getNewVarName vars acceptable
    | (not(null acceptable)) = let e = head acceptable
                               in  if(elem e vars)
                                   then getNewVarName vars (tail acceptable)
                                   else e
    | otherwise = '$' -- returns '$' just if all acceptableNames are used up

Basically, what it does is return the first Char in acceptableNames that is not contained in vars. Apparently, it works.

I realize there must be lots of better ways to do it, but, considering my knowledge on Haskell, that was the way that made sense to me.

Please, let me know of any ways I can improve this code.

// Edit 2

@luqui answer worked perfectly in this case. Way simpler than my solution.

Bruno Nascimento
  • 83
  • 9
  • You can use a list of acceptable characters like `['a'..'z']` or whatever, `filter`, and `notElem` to get a list of acceptable characters that aren't used yet in the `String`. – Chai T. Rex Dec 07 '16 at 22:13
  • 1
    You could do `import Data.Unique; uniqueName = ("var" ++) <$> hashUnique <$> newUnique`. This function lives in `IO`, but you're guaranteed to always get a unique string of the form `varN` where `N` is a sequence of digits. Considering there's only so many characters to choose from and `Data.Unique` can provide as many unique names as you have RAM for, this solution scales more. – bheklilr Dec 07 '16 at 22:16
  • @ChaiT.Rex comment actually gave me an idea to try something. I'll edit the question to add my try. Also, I'm not sure if I uderstood bheklilr's idea, but it seems it wouldn't work in my case, since the variables are named using a single Char. – Bruno Nascimento Dec 08 '16 at 02:35

2 Answers2

2

For a quadratic time algorithm (made generic, in Haskell style):

import Data.List ((\\))

getNewVarName :: (Eq a) => [a] -> [a] -> a
getNewVarName possibleVars varsInUse = head (possibleVars \\ varsInUse)

Where (\\) is the list difference operator.

If you use Data.Set to store the possible variables and the variables in use instead of a list, then this same algorithm only costs O(n log n). You can use a trie to get linear time, but this is just getting silly. If you actually care about speed you should use a supply of fresh variables.

luqui
  • 59,485
  • 12
  • 145
  • 204
1

You can save state of free characters when you've just got one.

So, you need the function like this:

getNewVarName :: [Char] -> (Char, [Char])
getNewVarName (x:xs) = (x, xs)
getNewVarName _      = error "Ups, here are not free characters."

let
    (name1, xs') = getNewVarName xs
    (name2, xs'') = getNewVarName xs'
in ...

And you can see this question.

Community
  • 1
  • 1
freestyle
  • 3,692
  • 11
  • 21