The idea is that a program in such a language is a sequence of instructions that pop and push values from a stack. But we still need a lot of parenthesis and applications of the Branch function.Ī clever way to get rid of parenthesis is reverse polish notation, commonly used in stack-based languages. )Ĭompared to the association list, we got rid of the dots '.' and dashes '-', they have been made implicit in the structure of our tree. In Haskell, we’d have to write something like dict = Branch ' ' (Branch 'E'. Now, let’s reduce the source code needed for the dictionary tree. The curious reader may notice that we have actually implemented a trie. In this case, the accumulated value of the fold is the current subtree, although the term “accumulate” is a bit misleading in that we don’t make the dictionary bigger we make it smaller by passing to a subtree. Then, decoding a letter by walking down the tree is simply a left fold over the code word decodeLetter = tag. Of course, writing out the dict tree in full is going to be repetitive and boring, but let’s just imagine we have already done that. First, we assume that our dictionary is given as a tree data Tree a = Leafĭict = Branch ' ' (Branch 'E'. This procedure is also called dichotomic search because at each point in our search for the right letter, we ask a yes/no question “Dot or dash?” (a dichotomy) that partitions the remaining search space into to disjoint parts. For instance, to decode the sequence "-.", we have to go right once and then left thrice, ending up at the letter B. Now, to decode a letter, we simply start at the root of the tree and follow the dotted or dashed lines depending on the symbols read. This is illustrated by means of a dotted line connected to the left subtree and a dashed line connected to the right subtree. We can depict this with a binary tree:Īt each node, the left subtree contains all the letters that can be obtained by adding a dot to the current letter, while the right subtree contains those letters that can be obtained with a dash. With each symbol we read, more and more alternatives disappear until we are left with a single alternative. And if the next symbol is a dot, then it can’t be a G or M because their second symbol is a dash. The idea is the following: whenever an encoded letter starts with a dash '-', we know that it can’t be for example an A or E, because those start with a dot '.'. So, let’s make an exception today and think of something as clever as we can. Dichotomic searchįaithfully replicating the morse code table is clear and preferable, but makes for quite large source code. All you have to do is to a qualified import of a different module, such as Data.Map, and change the definition of dict to dict :: MorseCode CharĪnd use instead of. But fortunately, it is very easy to change data structures in Haskell. A binary search tree, trie, or hash table would be a better choice. Of course, association lists are a rather slow data structure. To decode a letter, we simply browse through this list to determine whether it contains a given code of dots and dashes decodeLetter :: MorseCode -> CharĭecodeLetter code = maybe ' ' id $ lookup code dictĭecoding a whole sequence of letters is done with decode = map decodeLetter. Which we name dict because it’s a dictionary translating between the latin alphabet and morse code. For instance, we could store each letter and corresponding morse code in a big association list type MorseCode = String Into letters, we will have to store this table in some form. To write a program that decodes sequences of dots and dashes like. Morse code was designed to be produced and read, or rather heard by humans, who have to memorize the following table: In the following, I’ll present a series of solutions that gradually include dichotomic search (the straightforward generalization of binary search), stack-based languages or reverse polish notation, and finally deforestation (also called fusion), an optimization technique specific to purely functional languages like Haskell.įor your convenience, source code for the individual sections is available. Of course, what could be more clever than writing it in Haskell? -) In a post to reddit, user CharlieDancey presented a challenge to write a short and clever morse code decoder. This article previously appeared in issue 14 of The Monad.Reader.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |