# Commits

committed c9e20a8

• Participants
• Parent commits 636ffa6

# File phone2word.hs

` {-# LANGUAGE BangPatterns #-}`
` {-`
`-Attempt to convert numbers like 01523 568304 into`
`-words/numbers, using the map used on most mobile`
`-phone keypads.`
`+`
`+Attempt to convert numbers like 01523 568304 into words/numbers, using the map`
`+used on most phone keypads.`
` `
` -}`
` `
`     then Just char`
`     else Map.lookup (toUpper char) numbersMap`
` `
`+--`
`+-- Dictionary storage`
`+--`
`+`
`+{-`
`+`
`+To quickly determine if a series of digits corresponds to a word, we create a`
`+tree that stores all our dictionary words.  Each node is (effectively) labelled`
`+with a digit, and words are 'hung' onto the tree at nodes where the path to the`
`+node is the series of digits needed to 'spell' the word on a phone keypad.  The`
`+tree is sparse i.e. nodes are only created as they are need to store words or`
`+store the route to a word.`
`+`
`+In this way, looking up any series of digits becomes very quick, as for most`
`+series of digits we 'fall off the bottom' of the tree very quickly, and always`
`+fall off after n moves, where n is the maximum word length in the dictionary.`
`+`
`+Each node does not actually store the digit label - the root node does not have`
`+a digit, and children are stored in a Map where the key is the digit, so we know`
`+what digit each child node corresponds to by the path we have followed.`
`+`
`+-}`
`+`
` data WordTree = Node { nodeSubForest :: !(Map.Map Char WordTree) -- children`
`                      , nodeWords :: ![B.ByteString]              -- words that correspond to this node`
`                      } deriving (Eq, Read, Show)`