How to think about programming in Haskell
This is a node I intend to expand over time.
- use recursion and types to your advantage
This is central to Haskell programming, in fact
it is the most important part of your reasoning process. Getting to know your data type and pulling it apart to handle it case-by-case is the way of Haskell development.
Now that we have established the utility of recursion and strong static typing in building functions, let's use it. Let's see how we can write functions which obey our type rules by looking around for various instances of the output type and asking when they would make sense in the function definition. This might be aseat-of-the-pants approach, but hey, if it works, do it!
- input chunking
- Earlier in my blog I noted that it is important to realize the granularity of a decision. In that problem, one makes a decision at a point in the string not just on a single character but a chunk of the input string that is the same length as the search string.
- final product and transition
When you move over input, your functions relate to one of the aspects of this input - it's initial phase, its intermediate phases or its terminal phase. In recursive functions, the terminal phase is handled by what is known as a base case and this base case relates directly to the final desired output. It must return or represent that directly. The intermediate phase is also important and must be handled properly.
This example of creating a table of codes for a huffman tree shows the concept of final product and transition in action.
- can you use primitive recursion?
- Primitive recursion is characterized by a base case and an inductive case. For example:
sum  = 0
sum (x:xs) = x + sum xs