Now For Something Completely Different
For as long as I’ve been trying (successfully or not) to program, I’ve been using C like languages. When I was a kid, I struggled in vain to learn C++. As an adult, I learned Java. After that, I used Java as a spring-board into the wonderful world of C Like Languages: C, C++, Perl, Lua. I wrote hello world in dozens of others as well. I found myself proudly proclaiming that “I’m confident I could pick up any C Like Language!”
Then one day I thought “what about the rest of them?” Sure, maybe I can speak Latin. Maybe I can pick up any Latin based language with relative ease. But what if I need to move to China? I speak C, but what if C falls out of favor for something else? I decided it was time to try something else.
C and it’s cousins broadly represent the Procedural and Object Oriented paradigms. We’ve all been there and done that. Procedures and Subroutines may or may not take arguments, do something, and may or may not return a result. The global or local state may or may not change. Loops happen. I don’t think it is a stretch to say that these are the two most mainstream paradigms. For the purposes of this blog post, I’m going to lump the Procedural and Imperative paradigms together. I understand that they are not the same thing, but roughly speaking, the Procedural paradigm is an evolution of the Imperative paradigm.
This leaves us with Functional Programming. Unlike the functions of an Object Oriented or Procedural language, the functions of a Functional language closely resemble those in math. In math,
f(x+2), where x = 2, will always return 4. Similarly, a function in a Functional language will always return the same result given the same input. Where a function in a Procedural or Object Oriented language describes the steps to perform some task (usually, this involves some sort of loop construct), a function in a functional language just describes what the result of some function is. (usually involving recursion)
f(x+f(x-1)) adds x to the result of
f(x-1), which recursively adds x-1 to
f(x'-1) and so on until the end of time.
So, what programming language to choose? Many languages support functional programming to an extent. Python, Lua, and even C# if you squint hard enough. However, these languages are multi-paradigm. As such, it will be easy to fall back into my C Like ways. What about Lisp?
Lisp is a family of languages: Common Lisp, Scheme, Clojure, Emacs Lisp. Sure, I could learn one, and theoretically be able to transition with ease, but this isn’t a level of fragmentation that I’m comfortable with. In addition, Lisps are multi-paradigm, so I’m more likely to not keep the faith. Which leaves me with…
Haskell is a “pure” Functional programming language. While any useful program must have the side effect of reading from or writing to some external source, Haskell places that part of the program neatly in a corner. Let’s talk about some of the neat features of Haskell:
Expressions in Haskell are evaluated lazily. What this means is that a value isn’t computed until it’s needed. Let’s take a look at an example:
embiggen :: Int -> [Int] embiggen x = x:embiggen (x + 1)
This function takes an integer, and creates a list out of it. (Lists in Haskell behave much the same way as a normal linked list: O(1) insertion, O(n) traversal) The passed-in integer is pushed on to the front of the list resulting from
embiggen (x + 1). You may have noticed that this function will go on forever. While maybe not ideal, this is ok in Haskell because of Lazy evaluation. The infinityeth element of this list will not be evaluated until it’s needed!
show (take 5 (embiggen 5)) [5,6,7,8,9] show (embiggen 5) !! 17 22 show (embiggen 5) [OMG INFINITE RECURSION!!!!!]
In the first example, we call the library function
take, which returns a list containing the first
n elements of the passed in list. In the second example, we call the library function
!! (all operators are functions), which is the list indexing operator, which returns the
nth element of the list. In a language with strict evaluation, the list would need to be completely evaluated before these things could happen. In Haskell, it doesn’t! Only in the third example, where we attempt to call show on the entire list, does infinite recursion occur.
Tail Call Optimization
This is one of those terms that gets thrown around a lot, but what does it actually mean? The short answer is that it prevents a recursive function call from consuming a new stack frame. In a language without this feature, if
foo() calls itself, the new call will consume a new stack frame. This will cause a stack overflow if allowed to go on too long. In Haskell, this isn’t a problem because of Tail Call Optimization.
Haskell’s type system is quite different from the usual type systems. Sure there are Ints, Chars, Floats, Bools, and the like, but there’s more to it than that. Haskell is very strongly typed. There is no casting in Haskell, if a function takes an Int, there’s no getting around giving it an Int. However, the whole type system operates in a manner similar to generics in languages like C++ or Java. Take the following examples:
putInList :: a -> [a] putInList thing = [thing] addStuff :: (Num a) => a -> a -> a addStuff lhs rhs = lhs + rhs
The first function takes some arbitrary type, and returns a singleton list containing the passed-in argument. Much like generics, the argument shouldn’t depend on any type-specific behavior.
The second function takes two arguments of the same type that behaves like a number (Int, Float, Double, and friends) adds them, and returns the result. the
addStuff function accomplishes this by specifying that arguments of type
a should be members of the
Num Typeclass. Despite the word “class”, Typeclasses aren’t the same as classes in Object Oriented languages. You CAN think of them as being the same as Java’s interfaces. When you create a type, you can make it a member of any number of Typeclasses. You must then implement the functions specified by the Typeclass, just like when a class in Java
implements some interface, it must define the methods of that interface.
This is just the tip of the iceberg, but I’m sure you’re beginning to see how you can make very general functions in a very type-safe way.
Partial Function Application
A feature of functional programming is higher order functions. This means that functions can take functions as arguments, and functions can return functions. While nice, this isn’t exactly a new concept. Even C supports this to an extent with function pointers. What is new is partial application of functions. Recall the
addStuff function above. It takes two arguments of type
a and returns a result of type
a. Now let’s look at an example:
doNumFunc :: (Num a) => (a -> a) -> a -> a doNumFunc f a = f a addThree :: (Num a) => a -> a addThree a = addStuff 3 a
doNumFunc function takes a function that takes a type
a and returns a type
a (This is what
(a -> a) means), and a second type
a, and returns a type
doNumFunc calls the passed in function with the second passed in argument. The
addThree function takes a type
a and returns a type
addThree takes an argument, and calls the
addStuff function we defined earlier with its argument and 3. How does this all pan out?
addThree 3 6 doNumFunc addThree 3 6
Seems pretty straightforward, right? Though, this isn’t very re-usable. What if I want to add 4? Do I need to define a function
addFour? No, I can partially apply
addStuff. If you call a function in Haskell with less arguments than it takes, it will return a function that takes the remaining arguments and returns a result! Observe:
doNumFunc (addStuff 3) 3 6
Now things are getting cool. By calling
(addStuff 3), we’ve created a function that takes a type
a, adds 3 to it, and returns the result! You can’t do that in C!
Excited yet? You know you are, don’t try to act like you’re not. But how does one get started? Like any language, you need two things to begin: a compiler/interpreter and some reading material.
First up, you should go download the Haskell Platform. This package contains your compiler/interpreter and all the standard libraries. Haskell can be compiled, or interpreted. Or, you could use
ghci, the interactive interpreter, if you just want to doop around and try stuff.
If you’re running a Linux distro,
haskell-platform is likely in the repositories. In Debian or Ubuntu, it’s a simple:
sudo apt-get install haskell-platform
… and you’re set! Unfortunately, there doesn’t seem to be a great IDE for Haskell. NetBeans definitely has nothing to offer in this regard. Luckily for us, Haskell is simple enough to not really need an IDE. GEdit, the default text editor that ships with Gnome, has built-in syntax highlighting for Haskell. Just enable the built-in terminal in GEdit to test stuff and you should be good to go. I like to run
ghci in the embedded terminal to test functions as I write them. Plus, as you code, you can periodically attempt to load the script in
ghci to make sure everything is formatted correctly and you haven’t messed up your syntax/types.
One of the biggest barriers to learning a new language is money. Nobody wants to put down cold hard cash on learning something new when what they have is working just fine. Luckily for us, you can learn you a Haskell for free! Learn You A Haskell For Great Good is a beginner’s guide to learning Haskell aimed at developers coming from C Like Languages. The best part is that the whole book is available to read online for free! You can check it out for the low-low price of zero dollars. If you like it, maybe you buy a copy for your bookshelf. Or maybe you just spread the word.
Whatever you do, you should have a good base of knowledge in Haskell. At that point, you can just consult Hoogle to learn more.