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. 

    

Re-Learning to Count with Haskell pt.1

Functional Programming in a Nutshell

    It is becoming clear to me that counting, particularly conditional counting, may be one of the core lessons of Functional Programming and thus Haskell. A pure FP language has no mutable-state variables. Likewise, there are no global-variables in Haskell. This makes counting a serious problem for those new to FP and thus to those new to Haskell. 

    This marks a crucial divergence in how programming languages are designed. Imperative languages make liberal usage of mutable-state global variables. This makes realizing a program into an intuitive process. Imperative languages represent the way that the human mind reasons verbally. For instance, in order to count we memorize a number and add to that number using a universally known-sequence: the number line. At all points during our calculations, the current state of that number (the tally) is known. In this way, all variables are global in the human mind. Not only are they global, they conform to patterns like the number-line. 

    For instance, if you give someone a collection of single digit numbers at random, and ask them to assemble them into an ordered list, we know by sight which  place-setting each individual number belongs in. We do not need to use a merge-sort or insertion-sort method. We simply look at a number, say 7 for example, and intuitively know that it goes ahead of 1 through 6 but below 8 and 9. When we sort, we simply put each number into it's place, there is little to no method needed because we have such a firmly ingrained number line already in our heads.

    Now, we pick up a Haskell book and find that Haskell can't even remember numbers. It has a memory like the compartments of a Nautilus shell, each one closed to all others and none aware of the other's existence. This is supremely frustrating to the uninitiated because counting is one of the first skills we learn and we spend our entire lives doing it exactly the same way. In order to use Haskell, you have to take that fundamental pre-school era tool and chuck it out the window.

    There is only one fundamental tool in Haskell: recursion. Functions are merely a method devised to implement recursion. In order to count, you need to understand recursion. In order to store state-data, you need to utilize recursion. In order utilize recursion, you need to utilize recursion. Its enough to make your brain melt. 

    Once a function outputs a piece of data in Haskell, it is gone forever. You can try to capture that piece of data using a declaration like 'let tally = product [1,5,6,2]'. But once you declare a piece of data (like 'tally'), it is set-in-stone. You can never change 'tally', you can only destroy it and make a new one. This is the crux of FP. If you can accept and master these core precepts, you can master FP. If not, then you might-as-well sell your Haskell texts and forget that you ever even heard the phrase Functional Programming. In fact, this is exactly what the vast majority of people do. Not just students, professionals, academics and instructors do this in droves. More people reject FP than those who last long enough to learn to use it productively. This is unquestionably a massive weakness to the FP paradigm. However, I don't think it is inexorable.

    The fundamental problem with FP is that there just aren't any good texts on the subject. The few that exists are unorganized and vague, most likely because there just aren't enough professional writers in the FP writing-pool. The few authors who will take-on the subject seem to know that FP will never really take off and so only write for the benefit of the most harcore programming enthusiasts, and as such, completely gloss over the most basic of subjects like: How to Count in a Functional Programming Language. I will therefore devote my next blog entry to this fundamental subject. Look for part 2 in the coming weeks; where I shall spell it out free of charge.

   

Haskell is poorly explained

WARNING: The article below was written in a passionate wave of anger over Haskell's ponderous learning curve. I know it's logic is flawed. However, I am confident that plenty of other Haskell newbs have encountered the same issues and are also banging their head into the wall.  Since this section of the blog is about Haskell from the learner's perspective, I have decided to publish it now, and edit the salient points at a later date when the smoke of my ignorance has cleared:
 
     Most of the problems listed here (I suspect) are a result of poor documentation by all of the resources I have used so far. Having said that...

     Yes, it's true Haskell is a functional language, and as a result should not be held too strictly to the tenets of competing non-fp languages like, say ohhh, Python for instance. Python is a superbly easy language to learn from scratch (with zero CS background), and can do just about anything a programmer would ever need to do in the current professional environment. Haskell, is one of many candidates for a new ubiquitous general programming schema (functional programming) which may one day supplant the older imperative programming paradigm. In order for FP to push programming into a new direction and solve the current set of programming limitations, it needs to also do the simple things at least as well, if not better than, the current selection of popular general-purpose languages. Indeed, for it even to be considered a general-purpose language, it needs to excel at the basic level.  As such, it is assumed that Haskell (and any other good implementation of FP) can do things other languages can't do very easily or very well. It is also assumed that it will take some getting used to in order to master FP having come (as 99% of every coder on the planet has) from an imperative programming environment.

     I've been trying to keep this in mind as I develop my attitude towards Haskell as a learner and petty blogger. The problem is that this is not a valid excuse for the many problems facing anyone attempting to learn Haskell without a full-time professor, teacher's aid, or tutor on hand. I personally have begun to use freenode #haskell in lieu of such a resource. But, that is not an ideal solution. The people on #haskell are wise and generous, but they have no obligation to patiently explain things to a frustrated learner. They do so anyways (because they rock), but the IRC format itself forces all but the most blunt and carefree of folks to limit their inquiries for fear of being flamed or banned as a niuscance.

     So, that's no big deal, a good text can change all that. Haskell doesn't have a good text. But I am starting to realize, that is not the sole issue either. I am not a cultural relativist. I believe, scratch that, I know that there are some human behaviours that are right and some that are wrong. It doesn't matter if Functional Programming is based on a totally different way of thinking about problem-solving (which it isn't), there are some basic user-interface considerations that are universal and have nothing to do with the structure of the programming environment. Haskell defies some of these most basic considerations:

• Inconsistent Syntax between interactive environments and compiler. Commands and declarations that work on Hugs don't always work on ghci and vice-versa. Commands that work in ghci and Hugs in interactive mode do not always compile. This is dumb. Plain and simple. There is no excuse. There is no point trying out program snippets in an interactive environment that gives totally different results from the compiler. That just defeats the point of even having an interactive environment. IDLE exemplifies how this can be done correctly.
• Conflicting rules based on still more hidden laws. In Chapter 2 of Haskell: The Craft of Functional Programming we are asked to create a module which loads yet another module and uses it's code as a basis for new functions. We have previously been told that indentation is optional in Haskell. We have also been told that indentation is really just a way to make the contents of a function easier to read; and can be dispensed with at will. However, the only way to import a function inside of the definition of another function is to indent the import command, like this:                                                                                                              >module name where                                                                                                                     >    import oldmodule  
• IO what a mess... Yes, I know Haskell IO is based on Monads which are themselves an attempt to separate impure data from pure data. Fine, I get it. But, can we at least get a listing of the reasons behind the ponderous IO mentality at work here? For example: We are told that IO actions have to be performed within a function which is, itself, an IO action. We are also told that IO actions cannot be called outside of the 'main = do' function. Then we realize (I have yet to see this documented anywhere) that certain IO actions (like getLine) cannot be called inside of 'main'. In order to bring data in from the outside world, we need to create seperate functions, each with their own 'do' notations and then call them from main. However, main handles output operations like putStrLn just fine. Why? Likewise, we are told that main, and all other 'do' notation functions must end with a function or command that returns data. Yet, some functions or commands mysteriously don't work, despite meeting all of the qualifications needed. Other functions that do work return no data whatsoever except null (). Why the inconsistency? Then there's print. Print works sometimes and then fails spectacularly at others. And, it should'nt be about type; since print has the capability to display data of all built-in types from Ints to Bools. You eventually learn to use print sometimes and putStrLn at others; often without knowing why. Why is this so hard?!
• 'let' it be already... Declaring a variable is one of the most universal processes that occur in programming. It's the core function. In Haskell, you say 'let x = whatever'. The only problem is that let doesn't always work. For instance, try declaring a list in hugs. 'let x = [1,2,3]' doesn't work. 'x = [1,2,3]'? Nope. How the hell do you declare a stupid list? Yes, there is a way, but who cares? Why do we need to learn a 3rd way to declare a list in Hugs? We shouldn't even need to learn two ways to declare a simple variable. There should only be 1! In the time it takes to figure this out, you could be making list comprehensions in Python that already work!
• Pointless compiler reports that even professors can't understand Why bother? If you can create a logically consistent compiler output then you can also link it to a simple pattern-matching algorithm (perhaps using Haskell's own pattern-matching toolset) that gives the user some information that is actually useful. Most of the compiler errors I have run across fall into one of four categories: 1) A function is missing an argument 2) You used the wrong type for some function or operation 3) You are missing an indent (even though indents are supposed to be voluntary). 4) You are missing parens somewhere. What's the point of even having error-messages when even the experts have a hard time understanding them?

     My point is simple: Haskell is not ready for prime-time. I'm at the point where I must choose to continue studying Haskell even though my gut is telling me that the designers never intended the language to actually be used. Thanks to LYAH, I have seen some of the ways in which Haskell can be exceptionally powerful compared to what I'm used to (Python and C++). I also know that I am an undergrad and my opinion will change once I gain mastery of the language. As a result, I am resolved to continuing my study of Haskell. 

    Still, I can already see why the language is doomed to obscurity in it's current state. It will need either massive ergonomic reform, or an exceptionally bright text to overcome it's pointlessly steep learning curve.