module Seq from Microsoft.FSharp.Collections
val tryFind : predicate:('T -> bool) -> source:seq<'T> -> 'T option Full name: Microsoft.FSharp.Collections.Seq.tryFind
val n : int
module Option from Microsoft.FSharp.Core
val map : mapping:('T -> 'U) -> option:'T option -> 'U option Full name: Microsoft.FSharp.Core.Option.map
val iter : action:('T -> unit) -> option:'T option -> unit Full name: Microsoft.FSharp.Core.Option.iter
val printf : format:Printf.TextWriterFormat<'T> -> 'T Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printf
Living in a post-imperative world
Introduction to Functional Programming \(\lambda x . x\)
Ask at any time, if no fit: take offline
Ask for breaks
What
Computation = evaluation of functions
execution of procedures
Declarative = expressions and declarations
statements
change state, mutate data, side-effects
Why
Easier to understand temporal dependency
Testability by default
Composable
Usually FP languages are very concise
Less bugs, faster (safer) to change
Understandability, Readability
Why? 1/2
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
int [] numbers = new int [] { 1 , 2 , 3 , 5 , 4 , 6 , 7 };
int ? result = null ;
for (int i = 0 ; i < numbers.Length; i++ )
{
int current = numbers[i];
if (current > 3 & & current % 2 = = 0 )
{
result = current * 2 ;
break ;
}
}
if (result.HasValue)
{
Console.WriteLine(result.Value);
}
1:
2:
3:
4:
[ 1 ; 2 ; 3 ; 5 ; 4 ; 6 ; 7 ]
|> Seq . tryFind (fun n -> n > 3 && n % 2 = 0 )
|> Option . map ((*) 2 )
|> Option . iter (printf " %i " )
Exercise: Write a function compute(n, k)
returning the total of square roots of the k
first even numbers starting from n
Why? 2/2
FP is easier to write, easier to read, easier to test, and easier to understand. [...] you have found it anything but easy. All those [...] are anything but easy .
[...] But that’s just a problem with familiarity. Once you are familiar with those concepts – and it doesn’t take long to develop that familiarity – programming gets a lot easier.
This means that the programmer has to juggle fewer balls in the air at the same time. There’s less to remember. Less to keep track of. And therefore the code is much simpler to write, read, understand, and test. ...
"[...] The bottom line is this.
Functional programming is important.
You should learn it. [...] I suggest Clojure."
Uncle Bob 2017-07-11
Why not
Further away from the machine, some things difficult to encode.
Promise of automated parallelization not met (yet).
Lazy evaulation, data structure builders
Discuss later
Functions
as values
can take functions
can return functions
name of function is an ordinary variable
sorting (sortBy)
Higher order functions
1:
2:
3:
4:
main :: IO()
main = mapM_ print ["Hello" , "world" ]
-- "Hello"
-- "world"
1:
2:
3:
4:
5:
6:
7:
map :: (a - > b) - > [a] - > [b]
map f [] = []
map f (x : ys) = (f x) : map f ys
main :: IO()
main = print $ map (\x - > x*x) [1 , 2 , 3 ]
-- [1,4,9]
Currying
\(f: X \times Y \rightarrow Z : curry(f): X \rightarrow (Y \rightarrow Z)\)
\(f(x, y) : curry(f)(x)(y)\)
\((A \wedge B) \rightarrow C \Leftrightarrow A \rightarrow (B \rightarrow C)\)
Partial application
\(f: X \rightarrow Y \rightarrow Z : partial(f, x): Y \rightarrow Z\)
\(f(x)(y) : partial(f, x)(y)\)
Pure functions
No side-effects
No hidden dependency
Benefits
Referential transparency
\(f(x) - f(x) = ???\)
Idempotence
\(f(x); f(x) \equiv f(x)\)
Re-ordering
\(a=f(x); b = g(y) \;\;\equiv\;\; b = g(y); a = f(x)\)
Boolean algebra: AND, OR are idempotent
Database:
- lookup: no side-effects, idempotent, not pure, not referential transparent
- setting address: idempotent, side-effects, not pure
HTTP:
- GET, PUT, DELETE should be idempotent, POST does not need to be
Recursion
\(f(x) =
\begin{cases}
1 & x \leq 1\\
f(x-1) + f(x-2) & \text{otherwise}
\end{cases}\)
Tail recursion
A function calling itself (only) in tail (last) position.
Transformed by the compiler into
efficient while
(goto
, jmp
).
Exercise 1: Why is this important?
Tail recursion?
\(f(x) =
\begin{cases}
0 & x \leq 0\\
1 + f(x-1) & \text{otherwise}
\end{cases}\)
is not tail recursive.
Exercise 1: Why?
Exercise 2: What does this function do?
Exercise 3: How to transform into a tail-recursive function?
Tail recursion using continuation passing
\(\begin{align}
g(x, y) &=
\begin{cases}
y & x \leq 0\\
g(x-1, y + 1) & \text{otherwise}
\end{cases}\\
f(x) &= g(x, 0)
\end{align}\)
Tail recursion can usually be replaced using higher-order functions .
Strict vs. lazy
1:
2:
print $ length [ 1 /0 , error "Oops" ]
-- 2
1:
2:
// printfn "%A" [ 1/0 ].Length
// System.DivideByZeroException: Attempted to divide by zero.
Exercise 1: What are the preconditions for lazyness?
Exercise 2: How can you make something lazy?
Exercise 3: Are there any detrimetal effects? Why?
Preconditions: pureness, otherwise needs to be evaluated for sideeffects.
`Lazy`, `lazy`
Locking (side-effects) -> pure or idempotent
Type systems
static vs. dynamic
manifest vs. inferred
nominal vs. structural
Sub-categories
dependent
flow-sensitive
gradual
Data structures
Immutable, sharing structure
Algebraic data types
Product types
Tuples, Records
Sum types
Discriminated Unions
Tuples: use only for up to 3 elements with different types, otherwise use Records
Structural equality
Simulating state
As there is no mutation, how to keep state?
Monads
A mathematical concept from Category Theory.
Type constructor M
return :: a -> M a
bind :: M a -> (a -> M b) -> M b
(>>=
)
CT: a language composed of *objects* and *arrows* (morphisms) used to formalize other high-level abstract concepts such as sets, rings, groups.
Monads are also called *programmable semicolons*.
[Haskell doc](http://hackage.haskell.org/package/category-extras-0.53.4/docs/Control-Morphism-Synchro.html) [Example](https://books.google.ch/books?id=Ugzth388fX4C&pg=PA144&dq=categorical+definition+of+synchromorphisms&hl=en&sa=X&ved=0ahUKEwjHrKWazcPVAhXQJFAKHdb0DygQ6AEIKDAA#v=onepage&q=categorical%20definition%20of%20synchromorphisms&f=false)
More concepts: [The Extended Functor Family](https://www.youtube.com/watch?v=JZPXzJ5tp9w) by George Wilson
Examples:
Maybe, State, I/O, Collections, Continuation (Async), Parsers, Exception handling, ...
Alternative operations
fmap :: M a -> (a -> b) -> M b
join :: M M a -> M a
Questions?
Raphael Schweizer
@_Caring_Dev_
caringdev.ch
Supported by