Re-Learning to Count with Haskell pt.2

Easy as Pi, and that's not very easy at all!

    The basic idea of recursion is to create a feedback loop. Exactly the sort that Jimi Hendrix used to create his immortal guitar sound. In a computer program, a function is like a guitar amp. It amplifies the input according to some mechanism of your design. If your guitar pickups receive the sound being output by your amp, the amp then amplifies that sound, then your guitar picks-up the sound at an amplified level, the amp amplifies THAT sound and it goes on and on until you transcend the mortal coil and achieve rock-nirvana (which for me is Nirvana). That's recursion. Example:

function x =

  x + function x

Notice how it says x PLUS function x, the 'plus' part is the amplifier I was rambling on about.

    The problem is that the program which does this will never terminate; it will go on forever (which is what laymen call 'hanging') until you pull the plug on the amp. So, what if you could program-in some condition wherein the function 'pulls the plug' on itself. This is called a base-case.

The program below counts how many elements there are in a list of Integers:

count :: [Integer] -> Integer

count [] = 0

count (x:xs) = 1 + count xs

    The base-case here is the second line (count [] = 0). This says "when you come to an empty-list, output the Integer 0."

    The third line features a magical symbol which I call "Head-Tail Notation": (x:xs). In this symbol,  'x' represents the first item in the list and 'xs' represents the rest of the list or the 'tail'. This allows us to split the list into sections, which is incredibly useful. For instance, '1 + count xs' says "add one to the output of the 'count' function as it is applied over the remainder of the list ('xs' is the remainder of the list)." With this tool, we can operate on each item in the list -- one at a time -- until there isn't anything left in the list. Again, the second line gives us an exit from the program which is triggered by an empty list. 

    Finally, we add 1 to the output of each successive pass of count xs. Remember, with each pass through 'count' ( if we make it past 'count [] = 0' ) the 'Head-Tail' operator will split the head off of whatever's left of the list so that we are only operating on the tail or (xs).

    With the color red signifying the 'unseen' operations performed by the cpu, the flow of operations would go like this:

Assuming that [] means 'empty list'

listA = [1,4,7]

count listA =

~ count [] = 0 -- False, Continue

~ count (x:xs) = 1 + count [4,7]

~ count [] = 0 -- False, Continue

~ count (x:xs) = 1 + ( 1 + count [7])

~ count [] = 0 -- False, Continue

~ count (x:xs) = 1 + ( 1 + ( 1 + count []))

~ count [] = 0 -- True, Output 0

~ Output (1 + (1 + (1 + ( 0)))) = 3

    To recap in plain English, we take a list which (in this case) has 3 elements. We test the list to see if it is empty. If not, we proceed to the next 'definition' in the 'count' function: line 3. This definition says that we want to split the input list into two parts, the first element (head) and everything else (tail). Then, the definition says, "add the number one to whatever the output of 'count the tail' is. This is the feedback we were talking about. Since we are not including the 'head' in our feedback loop, we know that the list will get smaller as the 'head' is removed with each pass; until the list is empty. Once that happens, we know that line two will trigger the feedback loop to 'pull the plug' on the whole function. However, Haskell knows we still have all those 'plus ones' to add together. It then uses that sum as an output value. Voila, counting achieved! 

   This is all fine and dandy except that Haskell already has a built-in function for this called 'length'. Besides, what we really need is a conditional function; something that will allow us to count a specific type of element amongst a field of others. I call this conditional counting, but it would probably be better to call it selective counting. That's what the next function does. 

    'countElems' takes an Integer and looks for it amongst a list of other Integers. It has almost-the-same base case as 'count': countElems x [] = 0. In function definitions, we must always include BOTH arguments; even when one of them is not being used for that line. Here we include x, which is the target Integer: the Integer we are trying to match. In definition 3, we plan on splitting the list into a head and tail section; so we employ 'head-tail' notation. Since we're using the name 'x' for the target Integer, we can't use the name 'x' for our 'head-tail' notation; for fear of confusing the compiler. Thankfully, Haskell understands the 'head-tail' symbol natively. As a result, it knows that (x:xs) is the same as (y:ys) when used in an argument. This allows us to avoid confusion in our definition.

countElems :: Integer -> [Integer] -> Integer

countElems x [] = 0

countElems x (y:ys)  

  | x == y = 1 + countElems x ys

  | x /= y = 0 + countElems x ys

    The key maneuver here is that we used 'guards'. Here we say, "if x is equal to y (the 'head' of the remaining list), then add 1 to the output of countElems on the tail end of the list ('ys'). If not, add 0." With each pass through 'countElems', we chop off one more item from the list and add either 1 or 0 depending on the outcome of the two tests:

  | x == y = 1 + countElems x ys

  | x /= y = 0 + countElems x ys

    Just like 'count' above, we eventually chop all the elements off of the list until nothing is left. This triggers the base-case. The real magic here is that Haskell knows to then go backwards and sum-up all of the 'plus 1' operations and then spit out the sum upon exiting the function. Well, the magic is that it does all this without being told to. Actually, it remembers all of those 'plus ones'! So Haskell does have a memory after all! 

    Still, you see now that Haskell really does cause you to review all but the most basic of mathematical processes, like counting and memorizing, through the mind-bending lense of recursion  For this reason, I believe that recursion should be taught as early as possible -- perhaps Chapter 2. Whenever I finish Chapter 1, I'll give it a go.