###Andrew Alexander
A loose transcription of an impromptu five-minute presentation at the Recurse Center, 5 May 2016
##Pattern-matching
(I don't think "pattern matching" is a great name, but this is what everyone calls it.) Anyway, in normal programming, you define a function exactly ONCE, and if you need it to behave differently depending on what its input is, you have to write if-then branches or switch or case statements, and things can get very ugly very fast.
This is an issue when you're writing recursive functions, since you need to seperate out the base and the inductive cases. Here's a factorial function in JavaScript:
factorial = function(n){
if (n == 1) {
return 1
}
else {
return n * factorial(n-1)
}
}
But Haskell lets you define functions like they're piecewise functions in your high school algebra class:
factorial 1 = 1
factorial n = n * factorial (n-1)
It's that easy! You can have multiple definitions of your functions, and the when the compiler tries to evaluate something, it'll look at each definition in turn until it finds one whose input domain matches.
##Infinite lists
You can have infinite lists in Haskell!!! Well, not really. You can't have infinite anything, at least not anything that's actually infinite, not anywhere in a finite computer or our finite universe. But you can have potentially-infinite lists in Haskell. Here's a list that contains (potentially) ALL THE NATURAL NUMBERS:
x = [1..]
You can think of this as like a while loop gone wrong, except that in Haskell it's not wrong! You can type this into your program, or into GHCi, and everything is fine. (If you then ask it to actually show x, then the universe will explode. But if you just define it, there's no problem.)
Here's another example. This is a bit confounded with some other stuff, but I like it. This is a function that returns a list of the factorials––i.e., ALL OF THEM:
factorials = scanl1 (*) [1..]
So what's going on here is that scan is kind of like fold or reduce, in that it combines all the elements in [1..] using * (i.e., multiplication), but unlike normal fold and reduce, it returns not just the final value of the reduction, but also all the intermediate values. So it takes the list [1,2,3,4,5..], and shows us how it tries to fold it up using multiplication, element by element:
[1*2,1*2*3,1*2*3*4, ...]
Anyway, we get an infinite list of all the factorials, which we can verify if we use Haskell's take function, which returns the first however-many items of a list:
take 5 factorials
>> [1,2,6,24,120]
By themselves, potentially-infinite lists probably aren't that interesting computationally, but philosophically, they're really exciting. (They feel so dangerous!)
And even from a computational perspective, they're a good example of some very important behavior. They're a good example of lazy evaluation, which is an important concept in Haskell and functional programming in general. Basically, in normal, imperative programming, you tell the computer to do something, and it does it. In functional programming, you tell the computer to do something, and maybe it does it. But usually not. Haskell only evaluates things if it absolutely has to.
##Partial Application
You've probably seen map before. We can, for exampe, map the plus ten function over a list, and get back a new list, to which ten has been added to every element:
map (+10) [1,2,3,4,5]
>> [10,12,13,14,15]
But what if I do this:
map (+) [1,2,3,4,5]
"But Andrew," you say, "you can't do that! Addition takes two arguments, and yet you've only supplied it with one! The compiler will complain!" Oh no, it won't! In fact, I'll get back a list of functions:
[1+,2+,3+,4+,5+]
So I get back a list not of numbers, but of functions: a function that adds one to its argument, a function that adds two to its argument, a function that adds three to its argument, and so on. (Note that in GHCi it can't actually display this, but it does work.) I start with a list of numbers, I map a two-argument function over it, and I get back a list of functions of one argument!
The fancy name for this is "partial application," or, even fancier, "currying." It's really useful, really powerful, and really beautiful!