fp

FP Notes

Functional Programming In a Nutshell
================================
### History
The idea of functional programming has been around since well-before the invention of computers.  The concepts of "partial application", "currying", and really higher level mathematics in-general lay out the framework used for the modern functional programming, more than its competing paradigms of imperative and Object-Oriented. 

###What is Functional Programming? 
In a nutshell, Functional programming is two things: 

 - Programming with the ideology that functions can be treated like a first-class-citizen
	 -  Think about math class: 
		 -  $ y = x^2  \equiv x= \pm\sqrt y $
 - Writing functions in such a way to maintain composablity. 
	 - More on this below.

###Composabilty
Again, remember math class: 
 $$
f \circ g = f\left(g\left(x\right)\right) 
 $$
 
In a nutshell, we apply $x$ to $g$, then whatever that returns, we apply that to $f$

As it turns out, this is a surprisingly useful tool for creating new functions, and can be used directly in functional programming. 
####Example
Assume you were tasked at sorting a list. You might write a quicksort function like this (in Haskell)
```
quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted  
```
This works great, it's fast *it passes QA*, you're happy, and then you find out that the client actually wants a reverse-sort. 

There are two options here: 

#####Edit the code so as to satisfy the client. 
This is tempting, but bad for several reasons, outlined below.

 
##### Employ composition. 
Since the first option is pretty lame, perhaps we can utilize mathematics to help us. 

Let's write quick `reverse` function: 
```
reverse :: (Ord a) => [a] -> [a]
reverse [] = []
reverse x:xs = reverse (xs) ++ x
```
Not too hard.  Now, let's solve the client's problem. 

```
(reverse . quicksort) myList
```

This will first do a regular sort, then reverse that. 

###Why was the second option superior?
You might be wondering why the functional solution to this problem is superior to simply modifying the original code.  The answer is multi-faceted. 

First, `quicksort` might have been used elsewhere.  It's entirely possible (and probable) that you're working on a project with more than one person, and it can sometimes be impossible to tell how-far-reaching *changing the behavior* of a function can actually be.  As such, the other option would be to copy-paste the original `quicksort` function, which would work, but then, again, need to be re-QA'd, and would bloat our codebase with largely-duplicate code. 

The first option also had the disadvantage of simply being a bandaid.  For all we know, the client could change their mind and decide they like the first order better.  As it stands, in order to go back to the original order, we simply have to remove the composition using `reverse`.

Yet another reason that employing composition might be the better option comes down to the fact that we're employing a more modular philosophy: Instead of building big things directly, we build a bunch of small, individually-useful things and chain them together. 

That last point really comes down to why functional language is useful.  `reverse` is arguably useful in its own right: it's self-contained, does one little task.  If there's a bug, there's no ambiguity in what to fix: it's simply a function that takes an array and reverses it. 

###Partial application.

Perhaps one of the most shocking things that come to people starting with functional programming, and in particular Haskell is the idea that functions can only have one argument, and one return value.  They seem even more confused when they see functions that *clearly* have more than one argument being used with them, such as 

```
map someFunction [1,2,3,4,5]
```
Clearly, map is a function that takes two arguments (some function and some list) and does stuff with them. 


The answer is that "you're both right".  There's a reason that the type signature in functional languages looks like this: 

```
someFunction :: firstArgType -> secondArgType -> thirdArgType
```

In functional programming, when you call a multi-argumented function, it simply applies the first argument, and then creates a new function based on that.  Here's an example. 

```
makeListNegative = map (negate . abs)
```
You might notice that we haven't applied the second argument to `map`, and this was intentional.  Instead, what we've done is create a new function, and this function's purpose is to take a list, and turn all the elements negative. 

This turns out to be a particularly powerful bit of code.  Here's a couple ways you can use this to your advantage
```
sumation = reduce (+)
```
```
lessThanAverage = (>) (calculateAverage(testScores))
```



###Reducing program complexity. 
The fact of the matter is that programming has the ability to get really hard really quick, and code that doesn't take proper measures to reduce complexity from the beginning will end up being bloated, and arguably-worse: expensive to maintain. 

By employing function composition and partial application, we've created "higher-order functions", and in a way, have utilized existing stuff to create a language within the language. In turn, this allows for highly customizable code while keeping it idiomatic and fast. 
`