Functions

Yes, it's time to do some actual programming! Cue applause and confetti.

We'll start with one of everybody's favorites, the factorial. In fact, we'll do it several ways. We'll start with a one-liner. You'll just need to remember two things: ranges, and the product function. Our first factorial function looks like this:

fact n = product [1..n]

Note that we don't need any silly complicated stuff like "let," or "def," or "public static int." Just function name, parameters, what you get. Now, if you're doing this in the interactive shell, you will need a "let." I think a demonstration is in order.

> let fact n = product [1..n]
> fact 5
120
> fact 12
479001600
> fact 147
172724589045463891120349865930862023193347650359789782279909232218331909803632016425196
730421051185517193022186186753141552289286530880054617437418211264485685176226179744177
18521481737240752909004600275325629858346067558400000000000000000000000000000000000

Haskell has arbitrary-precision integers for happy fun times.

Note the way we call the function. We don't need any parentheses, just the function and its argument. Now, if you're nesting function calls, you probably will want to include parentheses to clarify order of operations. Like so:

> fact (fact 5)
668950291344912705758811805409037258675274633313802981029567135230163355724496298936687
416527198498130815763789321409055253440858940812185989848111438965000596496052125696000
0000000000000000000000000

Hokay, moving on. Factorial function number two:

fact n = foldl (*) 1 [1..n]

Foldl is a very common function in functional languages. It's what's known as a higher-order function - a function that takes another function as a parameter. Let's take a look at foldl's type.

> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

Notice that first part in parentheses? The first parameter to foldl is a function. In our case, we're using the * function. (We need to enclose it in parentheses because it's an infix function.) Foldl basically takes a function, an initial value, and a list, and combines the initial value and everything in the list together using the function. It does this by putting the initial value and every element from the list in a line, putting the function between every pair, and associating to the left. (There's another function, foldr, that associates to the right.) So when we call, say, this:

foldl (+) 0 [1..5]

We're essentially doing this:

((((0+1)+2)+3)+4)+5

Moving on, a minor modification. Let's call it factorial program 2.5.

fact n = foldl1 (*) [1..n]

The foldl1 function is identical to foldl, except it doesn't need an initial value; it just uses the first element of the list.

Moving on, we come to one of Haskell's most powerful features: pattern matching.

You're likely familiar with C or Java's switch statement, Ruby's case statement, or maybe even Perl's given. Pattern matching is a souped-up version of this. To the example! (We'll also use recursion!)

fact 0 = 1
fact n = n * fact (n-1)

When you call this version of the factorial program, Haskell will run through the lines in order, checking for one that matches what you called. If you used 0 as your parameter, then that's easy! 0! is 1, it says so right there! If you didn't use 0, then whatever you used is n, right? So multiply n by (n-1)!, and there you go. For a slightly more complicated example, we can also do Fibonacci numbers:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

(There's actually a much cooler way to do the Fibonacci sequence, which I'll cover later.)

With pattern matching, we can do things like implementing foldl:

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f i [] = i
foldl' f i (x:xs) = foldl' f (f i x) xs

The apostrophe is a legal character in function names. In the (x:xs) pattern, x is the first element of the list and xs is the rest.

Now we can implement foldl1 in terms of our foldl1' function.

foldl1' :: (a -> a -> a) -> [a] -> a
foldl1' f (x:xs) = foldl f x xs

We can implement product specifically:

product' :: (Num a) => [a] -> a
product' [x] = x
product' (x:xs) = x * product' xs

Or we can implement it with foldl1:

product' :: (Num a) => [a] -> a
product' xs = foldl1 (*) xs

Haskell has a built-in function called zipWith, which takes a function and two lists, and combines the lists by applying the function to corresponding elements. So, for example, we can do:

> zipWith (*) [1..10] [2..11]
[2,6,12,20,30,42,56,72,90,110]

Let's reimplement zipWith. Start by looking at the type:

> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

So we'll need three parameters: a function and two lists. We start with the base case: if we combine two empty lists, we obviously get an empty list. So we can start with

zipWith' f [] [] = []

If we have a list with elements, we want to combine the first elements of each list, put it at the front of the result list, and add the combinations of the rest of the elements. So we do this:

zipWith' f (a:as) (b:bs) = (f a b):(zipWith' f as bs)

Now, add a type header (you don't actually have to do this, but it can make things nicer) and put it all together:

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f [] [] = []
zipWith' f (a:as) (b:bs) = (f a b):(zipWith' f as bs)

Remember I said there was a really cool way to do the Fibonacci sequence? Here it is.

 fibonacci = 0 : 1 : (zipWith (+) fibonacci (tail fibonacci))

That's the entire Fibonacci sequence. The whole thing. Remember that Haskell is lazy, so it won't evaluate anything in the list until it needs to.

Let's finish with one more common one: the quicksort. First, let's figure out the type. We start with a list of things, and end with a list of things of the same type. The things also have to be comparable. So our type is this:

(Ord t) => [t] -> [t]

We'll start with our base cases. Obviously, a one-element list and an empty list are already sorted.

quicksort [] = []
quicksort [x] = [x]

If we have multiple elements, we select a pivot (we'll use the first element of the list), sort the stuff lower than the pivot, add on the pivot, then sort the stuff higher than the pivot.

quicksort (x:xs) = (quicksort [ a | a <- xs, a < x]) ++ [x] ++ (quicksort [a | a <- xs, a >= x])

Put it all together:

quicksort :: (Ord t) => [t] -> [t]
quicksort [] = []
quicksort [x] = [x]
quicksort (x:xs) = (quicksort [ a | a <- xs, a < x]) ++ [x] ++ (quicksort [a | a <- xs, a >= x])