The road to FP

At the moment this page is just a dump of raw ideas of what to put in the various chapters and to have a rough organization of the content. The topics below will have to be properly expanded, with references, comments, examples and exercises.

Target of this content

To learn functional programming applied to Scala
To be able to understand the existing online materials
To be able to use the main FP libraries
To have an intuition of the theory behind FP
To become fluent in the majority of FP concepts, tools and techniques

Different way of thinking

Put aside all other paradigms, you’ll need to learn afresh
Paradigm shift: tons of new concepts, structures, techniques, abstractions
Declarative programming, cleaner way of thinking
- https://bartoszmilewski.com/2015/04/15/category-theory-and-declarative-programming/
Abstract over implementation details
Ease of reasoning with black-box approach
FP referential transparency makes things cumbersome. Requirements of new tools
The unfortunate way of learning FP in Scala: Haskell, few books, blog posts
Composability
- Design and analysis approaches: blackbox, top-down, bottom-up
- Composition of blocks
- Programming languages and modularity

Scala language feature: Case classes

What they add to normal classes
- https://stackoverflow.com/questions/2312881/what-is-the-difference-between-scalas-case-class-and-class
Pattern matching with case classes
- https://docs.scala-lang.org/tutorials/tour/pattern-matching.html.html
- https://alvinalexander.com/scala/how-to-use-pattern-matching-scala-match-case-expressions
How to define values with types
Build data types with case classes
Best practices (like sealed traits, …)

Definition of pure functions and referential transparency

Simple examples of both concepts and counter examples
Show that loops are not good, they require mutability
Immutability as values that cannot change
Local mutabilty can be used
Importance of pure function signatures
Working with expressions
Generating random numbers
Memoization, or values as functions
References:

Recursion

Solves the lack of loops for primitives
- https://sidburn.github.io/blog/2016/04/05/mutable-loops-to-immutability
Recursion is the equivalent of induction reasoning
- Rules of induction and how to translate them to programmi
Examples: list length, take nth element, flatten list, map, flatMap
Tail recursion. But it doesn’t solve all problems!
Recursion to iterators, important for safety:
- http://blog.moertel.com/tags/recursion-to-iteration%20series.html
Recursion from two different functions
- https://medium.com/@olxc/trampolining-and-stack-safety-in-scala-d8e86474ddfa
References:

Scala language feature: Lazyness

Lazy val
By-name parameters
- https://alvinalexander.com/scala/fp-book/how-to-use-by-name-parameters-scala-functions
Streams as infinite lists
- https://www.youtube.com/watch?v=cahvyadYfX8&t=741s
Lazy collections and how they can improve performance
Lazyness is like functions as values
References:
- https://www.manning.com/books/functional-programming-in-scala Chapter 5
- https://www.scala-exercises.org/scala_tutorial/lazy_evaluation

Purely functional data structures

FP as functions acting on data, no objects around
Sharing structure
- https://vimeo.com/20262239
Techniques to work with immutable data structures
Example: Linked list, simple tree
Spatial hash map
- https://github.com/ColOfAbRiX/tankwar/blob/master/src/main/scala/com/colofabrix/scala/geometry/collections/SpatialHash.scala
References:
- https://sidburn.github.io/blog/2016/03/14/immutability-and-pure-functions
- https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Scala language feature: Higher order functions

Polymorphic functions
The type keyword and fixing one type parameter
Functions as objects that can be passed around
- https://alvinalexander.com/scala/fp-book/how-write-functions-take-function-input-parameters
Composition of function (andThen, orElse)
Currying shift the way we interpret function parameters
- https://alvinalexander.com/scala/fp-book/partially-applied-functions-currying-in-scala
References:
- https://www.manning.com/books/functional-programming-in-scala Chapter 2
- http://learnyouahaskell.com/higher-order-functions

Functors and the world of containers

Mapping of values in the container
- http://learnyouahaskell.com/making-our-own-types-and-typeclasses#the-functor-typeclass
- https://fsharpforfunandprofit.com/posts/elevated-world/#map
Why do I want a container?
Mapping doesn’t change the shape of the container
Mapping as lifting of functions
Simple example with List+map as functor
Covariant and contravariant functors
- https://ocharles.org.uk/blog/guest-posts/2013-12-21-24-days-of-hackage-contravariant.html
- https://kubuszok.com/2018/the-f-words-functors-and-friends/#functor
Exceptions and null are evil. Option+map as functor
- https://sidburn.github.io/blog/2016/03/20/null-is-evil
References:

Scala language feature: Typeclasses

The expression problem
- https://www.wikiwand.com/en/articles/Expression_problem
Type constructors
Forms of polymorphism: type polymorphism, inclusion polymorphism ad-hoc polymorphism
- https://slides.com/petrabierleutgeb/polymorphism-in-scala-scaladays19
Simple examples of typeclasses
The materializer function
View bound and context bounds
Proof that a kind exists (as in proof that a type has the X typeclass)
Creating a typeclass for Functors
Recursive resolution of type classes (with implicits scopes)
References:

Monoids

What they are, mempty and mappend
Examples that generalize some operations like log addition
- https://typelevel.org/cats/typeclasses/monoid.html
Create new instances of monoid with type classes
Collapse a list with fold and reduce
- https://typelevel.org/cats/typeclasses/monoid.html
Show another example like Int and summing prices of items
Exercise: create a typeclass for Monoids and functions that work with them
References:
- http://learnyouahaskell.com/functors-applicative-functors-and-monoids

Applicative functors

What are applicatives
- http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors
- https://kubuszok.com/2018/the-f-words-functors-and-friends/#functor
Apply as lifting funtions and pipelining
- https://fsharpforfunandprofit.com/posts/elevated-world/#apply
Validating errors in a pipeline
- https://sihil.net/cats-validated.html
Indipendent computations and parallel processing
- https://alexn.org/blog/2017/01/30/asynchronous-programming-scala.html#h6-2
Traverse and sequence
- https://fsharpforfunandprofit.com/posts/elevated-world-4/
- https://sidburn.github.io/blog/2016/04/14/sequence-and-traverse
References:
- http://learnyouahaskell.com/functors-applicative-functors-and-monoids
- http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

Optics

Introducing monads

The need for sequencing elaborations
- https://stackoverflow.com/questions/28139259/why-do-we-need-monads?rq=1
A brief history of monads: monads defined, haskell without I/O, eugenio moggi uses monads, philip wadler explains them
How to keep a log of function calls
- http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html
Generate a sequence of random numbers
- http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html
Operate on multiple values at the same time
- http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html
Generalizing the composition of operations
- https://fsharpforfunandprofit.com/posts/elevated-world-2/#bind
Railway oriented programming
- https://fsharpforfunandprofit.com/rop/
Scala for-comprehensions and syntactic sugar for flatMap, map and filter
- https://alvinalexander.com/scala/fp-book/quick-review-scala-for-expressions
Writing your own LeMonad
References:

Most common monads

Intuitive monads: List, Option
Error handling monads: Option, Either, Try
- https://www.scala-exercises.org/fp_in_scala/handling_error_without_exceptions
Configuration and state monads: Reader and State
Evaluated-values monads and examples: Reader, Future and the IO monad
- https://www.beyondthelines.net/programming/cats-effect-an-overview/
Advanced monads and examples: Trampoline, Cont
- https://medium.com/@olxc/trampolining-and-stack-safety-in-scala-d8e86474ddfa
Real world examples of using these monads, writing a more complex application
Applicatives vs Monads
- https://fsharpforfunandprofit.com/posts/elevated-world-3/#validation
References:
- http://learnyouahaskell.com/for-a-few-monads-more
- http://adit.io/posts/2013-06-10-three-useful-monads.html

Handling errors in FP

Reviewing Option, Either and Validated
Scala exceptions and the ErrorMonad
Examples of the ErrorMonad with IO
- https://www.youtube.com/watch?v=KQZjOJjnHIE