"ALT TEXT"

T9 is a method of typing in words using letters on a keypad (such as on candy-bar phones and other keypad-only interfaces. The keypad usually looks like the image above (but there are variations). Note that the 1 key has no other characters, the 0 key is used to insert the “space” character, the asterisk (*) key is used to insert punctuation ( ()’.,!? etc ), and the octothorpe (#) key is used to switch between capital and small letters, amongst other modifiers. In this activity, we’re going to ignore the # modifiers in the interest of simplicity.

Before T9, you had to press the key multiple times to arrive at the correct input (e.g. for “h” you had to press 4 -> 4). T9 uses a smarter approach, suggesting the most common word for the value of keypresses in a sequence (e.g. just pressing 4 gives the suggestion “I”, pressing 4 -> 6 gives the suggestion “in”). We want to write a series of functions to go from an input of keypresses (e.g. 4->3->5->5->6) to the most common word(e.g. “hello”).

  1. Working at the TYPE level only (ignore implementation!), come up with a series of TYPES using algebraic notation (you can use a Haskell-y type signature if you like) for:
    • A single keypress
    • A function to transform from a keypress into all its possible values
    • A function to transform lists of characters into their combinations as strings (e.g. [“abc”,”def”] -> [“ad”,”ae”,..,”cf”]
    • A function to form a “dictionary” of all possible character combinations given a sequence of keypresses (do you need some new types here?)
    • A function to remove the “garbage words” from this “dictionary”
    • A function that assigns a probability value (e.g. is this a common word for that sequence?) to each word of this now clean “dictionary”
    • A function that chooses the word from the “dictionary” with the highest probability value for the input
    • A function that wraps this all together to go from a sequence of keypresses to a single word!
  2. Consider the function make_combinations, taking a list of keypresses and turning them into a “dictionary” of possible letter combinations. How would you approach this problem (is there a way to reuse previous functions to transform types – ignoring their implementation! – to your advantage)?
  3. Create a type signature for remove_garbage that, given a list of “known words” and a built-up “dictionary” of words formed from the keypresses, strips out (filters) the garbage words from the list.
  4. Create a type signature for a pipeline function that takes a list of keypresses and returns a dictionary of possible non-garbage words.
  5. Assume now that the “known words” list is actually a list of tuples, of type (Word,Probability) where type Word = String and type Probability = Float. Improve your “pipeline” type signature above to add in the probability as a tuple (non-garbage-word,assigned-probability).
  6. Create a type signature for a function that sorts these tuples in the list by probability (highest probability first)!
  7. Draft up (implement using the functions you’ve defined type signatures for) a top-level function that takes in a series of keypresses and translates them into a single possible word.