FP Scala Notes

# Scala FP Summary Notes
## What is a function?
In math, a function is a mapping from the set of possible inputs, the /domain/, to the set of possible outputs, the /codomain/.

This function maps from the set of possible inputs (the type `A`) to the set of possible outputs (the type `B`)
`A => B`

### Rules
* Every item in the domain must have a *single* deterministic mapping to an item in the co-domain
* However, not every item in the codomain has to have a mapping in the domain.

## What is a Type?
In math, a type is a Set of values. In code, a Type is a logical proposition, saying that the value you provide as an instance of the Type is within the Set of allowed values.  The compiler checks this and points out any logical inconsistencies.

Examples of possible types we can use:

Describe set by all elements it contains
`Boolean = { true, false }`

Some proposition that must be true for all elements of a Set
`Int = { x | x is an integer that can fit into 4 bytes }`

## Algebraic Data Types
Algebraic Data Types are compositions of other types, either *product types* or *sum types*

### Product Data Type
Think of different columns in a SQL row or keys and values in a JavaScript object

Here a person is a product data type consisting of the sub types Int and String
```javascript
const person = {
  age: 5,
  name: "Jon"
}
```

### Sum Data Type
Think a bounded union, it has to be one of a predefined set of things
```scala
sealed trait Animal
case object Seal extends Animal
case object Dog extends Animal
```

## Type classes
A type class isn’t a class in the OO sense (i.e. like `new Person()`), but instead a group (a /class/) of types that fulfill a certain contract for behavior such that *we can implement polymorphic functionality before knowing what actual concrete types this functionality will be used with.*

## What problem do type classes solve?
Using parametric polymorphism, Scala allows us to implement generic algorithms that are not bound to a specific type.

```scala
object Ops {
  def sumProduct[A](a: A, b: A): A = times(plus(a, b), a)
}
```

However this implementation “lies”, because this sumProduct method cannot possible handle all types of `A`, which can be any arbitrary type.  This algorithm will only work for types `A`  where `times[A]` is of type `(A, A) => A` and  `plus[A]` is of the same type.

Type classes allow us to say that this algorithm can only be used for types `A` where the times and plus function meet the criteria above.

### To create a type class we need:
1. Types (usually implemented as a trait with method signatures)
2. Operations on those types (usually implemented as a polymorphic method on the companion class of the trait creating the types)
3. Rules governing the operations on those types (additional methods on the companion object that can be configured for ScalaCheck)

## Functional Programming Type Classes
Thesis: if we implement (or have a library like `scalaz` or `cats` that implements) mathematically proven data types as type classes, we can access operations (methods) on these type classes without having to implement them again for every possible type.  In other words they are *polymorphic*. We just have to guarantee that the types we pass to operations in the type class meet the rules to the type class (see requirement #3 in section above)

/Note: Things like Functors or Monad are algebraic data types, usually Sum Types that are a closed union of types that follow Functor/ Monad laws and therefore can use Functor/ Monad generic methods./

## What the F#@k is the point of these FP Type classes?
[scala - How are Functors useful? - Stack Overflow](https://stackoverflow.com/questions/37929088/how-are-functors-useful)

1. We have collections of *generic* methods that guarantee certain mathematically proven behavior *if* used with types that implement a certain type class (like Functor or Monad)
2. If we create a type class implementation (like Functor or Monad) for a data type that we create, then we gain the ability to use the generic methods and get the mathematically proven guarantees for free.

Example:
We know there is a concrete type class implementation of `Functor` for types of  `List[A]` . So we know if we map from `List[A]` using a function of type `A => B`, we are guaranteed to get a return type of `List[B]`.  This is guaranteed because we have a Functor so we can use the generic `map` function that guarantees this behavior.

*In practice* a lot of people create data types that can easily be represented as algebraic data types, (product type or sum type or collection type) which means that if given an implementation of `Functor`, we get it’s generic methods for free.

### Semigroup/ Monoids
A Semigroup is any type that can be combined with itself with the `append` method
I.e. an Int combined with another Int would be the sum of both Ints.

A Monoid is a Semigroup that also has a `zero` or identity method.

### Functor
#### Veeeery Abstractly
A Functor represented in the type system as `F[A]`  (where `F` is a type that falls in the set of values that is the Functor sum type) is a program that may yield one or more values of type A, depending on the instruction set.

#### Methods on Functor
The `map` capability of a functor allows you to turn any instruction of type `return a` into `return f(a)`

### Additional Methods can be added to Functor to create more and more powerful type classes eventually leading to Monad which is the the “most powerful  general type class abstraction”


## Side Note: “The Functional Programming Game”
@jdegoes brought up this idea where the types in the method signature should determine the one possible implementation of the function.

When writing an implementation of a method, you’re not actually thinking about what you’re concretely trying to accomplish with the method, but instead just trying to find the shortest possible path from input type to output type.

The idea is that if you define your types well enough, the method should only be constrained to one possible implementation.

### Some corollaries of this
* *Write stupid code that uses smart objects*: The hard part shouldn’t be writing the implementation of the algorithm, it’s choosing the right types to represent your data, and the rules that these types need to follow (i.e. usually mathematical rules).

Linus Torvalds: `"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."`

Rob Pike: `Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.`
* *Declarative Code*: Eventually in the future, we will have compilers that are able to write out method implementations based on the input and output types we have defined and tune themselves for performance.  Taking a long view, how we write code today is just a single point in time along the trend from being imperative to being declarative.
* *Don’t impose unnecessary constraints to concrete types*:  FP has a lot of method signatures like this where all the variable names look like this:
```scala
implicit def SemigroupTuple2[A: Semigroup, B: Semigroup]:
  Semigroup[(A, B)] = new Semigroup[(A, B)] {
     def append(l: (A, B), r: => (A, B)): (A, B) =
      (l._1 |+| r._1, l._2 |+| r._2)
  }
```
This is very counter to my experience in JavaScript programming where you want the variable names to be descriptive. However, in this FP paradigm, when you’re writing generic algorithms, it’s often not possible to create good names for things, since the names you choose won’t apply to some concrete types. (Philosophically if you’re writing generic polymorphic code, you’re creating algorithms for data types that will be created by others in the future that you will never know about) So it’s often better to have basic short names that don’t imply some concrete data type.  It’s better to be more simple to allow the user to focus on the *types* which can’t lie, versus the *names* which can lie.