Haskell/T9 words
I like to read programming puzzles. When I search the web about how to apply for a job, those puzzles are just a click away and they are so much more fun than writing a resume. On stackoverflow or something I found this short little task:
- convert a sequence of digits into the possible string using t9 encoding as used on your cell phone.
This is not about filtering out the words that are in the dictionary of your language, so 23 should yield {"ad","ae","af","bd","be","bf","cd","ce","cf"} and 372659 should yield "franky" but also gibberish like "dpamjw" and "fscolz". I've heard interviewees were given 30 minutes to implement such a function, which is IMHO awfully long for such a simple task. Maybe that is because neither Java nor C# are adequate programming languages for the problem. To get from the List [2, 3] to the nested lists [["a","b","c"],["d","e","f"]] should be easy in any language, but the next step reminds me of the mathematical 'lift' operation. Nevertheless, I wrote this step as
stringsFromDigit :: Integer -> [String]
stringsFromDigit = map (:[]) . charsFromDigit where
charsFromDigit 1 = " "
charsFromDigit 2 = "abc"
charsFromDigit 3 = "def"
charsFromDigit 4 = "ghi"
charsFromDigit 5 = "jkl"
charsFromDigit 6 = "mno"
charsFromDigit 7 = "pqrs"
charsFromDigit 8 = "tuv"
charsFromDigit 9 = "wxyz"
charsFromDigit _ = error "not a digit! 1<=d<=9"
To write (:[]) is just an exercise in writing in point-free-style, it embeds an argument into a list and could be written as (\x -> [x]), which is easier to comprehend for me.
Now, which function transforms [["a","b"],["1","2"]] into ["a1","a2","b1","b2"]? Let me cut it short,
*Main> foldr1 (liftM2 (++)) [["a","b"],["1","2"]] ["a1","a2","b1","b2"]
does. From my mathematical knowledge, to 'lift' an operation f: X -> Y to Set(X) -> Set(Y)[1] is
f(A) = { f(a) | a in A }
and liftM2 does so for a binary function.[2] I came up with 2 versions
t9words :: [Integer] -> [String] t9words = foldr (liftM2 (++) . stringsFromDigit) [""] t9words1 = foldr1 (liftM2 (++)) . map stringsFromDigit
of which the latter one does not accept the empty list. I understand t9words1 more easily and wrote it first. I remembered when you combine fold with a map, there is some way to drop the map, and t9words does this.
Revisiting the introduction, I wrote 23 should yield [...], not [2,3] should yield [...]. While I prefer to domain to be a list of digits instead of a single number, for completeness' sake, t9 is the function to convert from a single number to the t9 words.
listFromNum :: (Integral a) => a -> a -> [a]
listFromNum = (reverse .) . listFromNum' where
listFromNum' _ 0 = []
listFromNum' base x = (x `mod` base) : listFromNum' base (x `div` base)
t9 :: Integer -> [String]
t9 = t9words . listFromNum 10
As you can see, Haskell is once again a language that yields short and beautiful programs. Take away the exercise in point-free-style and it is even comprehensible.
