Code snippets, Functional programming, Haskell

Morse code decoder in Haskell

As I was working my way through various Haskell books and tutorials, I was looking for a good, small coding exercises to practise my newly aquired skills. Morse code translation seems like a prefect candidate to demonstrate the power of algebraic data types and how functional programming really is about modelling your problem with types and then writing a couple of very short functions, just to glue things together. Here is a full implementation:


import Data.Char

data Tree c = Node c (Tree c) (Tree c)  | EmptyNode deriving (Show, Read, Eq)

leaf :: a -> (Tree a)
leaf a = Node a EmptyNode EmptyNode

morseCodesTree =
  let 
      q = leaf 'Q' 
      z = leaf 'Z'
      y = leaf 'Y'
      c = leaf 'C'
      x = leaf 'X'
      b = leaf 'B'
      j = leaf 'J'
      p = leaf 'P'
      l = leaf 'L'
      f = leaf 'F'
      v = leaf 'V'
      h = leaf 'H'
      
      o = leaf 'O'
      g = Node 'G' q z
      k = Node 'K' y c
      d = Node 'D' x b
      w = Node 'W' j p
      r = Node 'R' EmptyNode l
      u = Node 'U' EmptyNode f
      s = Node 'S' v h

      m = Node 'M' o g
      n = Node 'N' k d
      a = Node 'A' w r
      i = Node 'I' u s

      t = Node 'T' m n
      e = Node 'E' a i
  in Node '_' t e

decodeMorse :: Tree Char -> String -> Char
decodeMorse (Node c _ _) [] = c
decodeMorse EmptyNode _ = error "Failed to find code"
decodeMorse  (Node _ left right) (s:ss)
  | s == '-' = decodeMorse left ss
  | s == '.' = decodeMorse right ss

decodeMorseLine :: String -> String
decodeMorseLine  = map (decodeMorse morseCodesTree) . words


main = interact decodeMorseLine 

It’s really beautiful how the actual ‘logic’ of this program is only 7 lines of functional code (voluntary type annotations excluded) is all that’s needeed after you got your types right.

About these ads
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s