ruk·si
/notes

Functional Programming

Updated at 2015-07-25 21:35

Functional programming can refer to functional programming languages or using functional programming paradigms in non-functional programming languages.

Functional programming focuses on expressions over statements. Statements have implicit side-effect, they change the global state. Expressions return values according to passed parameters, they cannot change the state anything external. This removes hidden states from the program.

// statement in non-functional programming language int total = 0; for (int i = 1; i <= 5; i++) { total = total + i; }

// expression in functional programming language sum [1..5]

Non-functional languages may use functional approaches. Many modern programming languages provide lambda expressions or anonymous functions to get closer to functional programming.

// underscore.js, a JavaScript library
_.reduce([1, 2, 3, 4, 5], function(memo, num) { return memo + num; }, 0);

Functional programming is also about separating data and behavior. Object-oriented programming tries to tie behavior to data, but the same behavior can be applied to multiple types of data which object-oriented programming tries to solve with inheritance. But inheritance is frequently too complex to maintain, especially by less disciplined programmers.

# Object-oriented approach
List is data.
List.map is behavior.

# Functional approach
List is data.
map is behavior that can be used with multiple of types of data, including List.

Functional languages generally also have these main features:

  • Computation is treated as evaluation of mathematical functions.
  • First-class functions, functions can act like variables.
  • Higher-order functions, functions can take and return functions.
  • Lazily evaluated, nothing is calculated before the result is requested the first time.

Functional Paradigms

Type is a name for a collection of similar values.

Bool is a name for a collection that has two values: True and False.

Type error happens when you apply function to an argument of the wrong type.

> 1 + False
TypeError

Compiler calculates the type of each expression with type inference.

Tuple is a sequence of values of different types.

Polymorphic functions. Polymorphic function has one more more type variables. Type variable doesn't define a specific type it accepts.

-- `a` is a type variable
length :: [a] -> Int

Overloaded polymorphic function. A polymorphic function is called overloaded if its type contains one or more class constraints.

-- `Num` is a type class, exposing an interface that it must implement
sum :: Num a => [a] -> a

Conditional expression. They must always have else part.

abs :: Int -> Int
abs n = if n >= 0 then n else -n

Conditionals are rare. It's not unusual to see a program with over 5k lines of code and just few conditional-statements.

Guarded equations. You can think it as a conditional before the function is called.

abs :: Int -> Int
abs n | n >= 0    = n
      | otherwise = -n

Pattern matching. Functions have multiple definition using pattern matching on their arguments.

not :: Bool -> Bool
not False = True
not True  = False

(&&) :: Bool -> Bool -> Bool
True  && b = b
False && _ = False

Lambda expressions.

add x y = x + y
add \x -> (\y -> x + y)

List comprehensions.

[XXX | GENERATOR, GENERATOR]
[(x,y) | x <- [1..3], y <- [2,3]]
[(x,y) | y <- [2,3], x <- [1..3]]
[(x,y) | x <- [1..5], y <- [x..5]]  -- depenant generator
[x | x <- [1..10], even x]          -- generator guard

Loops are rare. Actions should be done on sequentials e.g. sequence, list or vector, or by using recursion.

Using a lot of types. Use types to represent constraints. When defining something new in the program, always first consider introducing a new type.

type Suit = Club | Diamond | Spade | Heart
type Rank = Two | Three | Four | Five | Six | Seven | Eight
            | Nine | Ten | Jack | Queen | King | Ace
type Card = Suit * Rank
type Hand = Card list
type Deal = Deck -> (Deck * Card)
type PickupCard = (Hand * Card) -> Hand

Using types as interfaces of the object-oriented languages.

// OOP
interface IBunchOfStuff
{
    int DoSomething(int x);
}

// FP
type BunchOfStuff: int -> int

Using types as error codes.

let ParseInt = string -> int            # No nulls
let ParseInt = string -> int option     # No exceptions
let FetchPage = CustomerId -> SuccessOrFailure<Customer>

All data is exposed.

type PersonName = {
    FirstName: String50
    MiddleName: String50 option
    LastName: String50
}

Functions are standalone things. They aren't attached to anything e.g. a class.

let z = 1
let add x y = x + y

Functions are everywhere.

ToUpper = string -> string
UpdateProfileData = HttpRequest -> HttpResponse

Everything should be parameterized.

// BAD
let printList() =
    for i in [1..10] do
        printfn "the number is %i" i

// GOOD
let mapList anAction aList =
    for i in aList do
        anAction i

Applications are heavily partitioned.

// BAD
let name = "Scott"
(printfn "Hello, my name is %s") name

// GPPD
let name = "Scott"
let greet = (printfn "Hello, my name is %s")
greet name
let names = ["Alice"; "Bob"; "Scott"]
Names |> List.iter greet

Options are everywhere. When you are using Options like Maybe, don't unwrap the option. Use lifting e.g. Option.map.

Functors are everywhere. If you create a wrapped generic type, create a map function for it. Mappable types are called "functors".

Applicative functors are everywhere. If you use a wrapped generic type, look for a set of "lifts" associated with it. Liftable types are called "applicative functors".

Impure Functional Languages

Easier to be used purely:
Clojure, Scala, F#, OCaml

Harder to be used purely:
C#, Java, JavaScript

Impure functions can have side-effects. Depends on the programmer how strict they want to be. You can use caching, which needs refreshing.

Using impure functional languages is tricky. Impure functional languages can have side effects so using them is basically the same as using object oriented languages with a functional utility library. It all depends on the programmer to create neat code.

Pure Functional Languages

Haskell

Pure functions cannot have side-effects. You can use memoization, which doesn't need any refreshing. The programmer is forced to create neat code.

Pure functions are easy to reason about. Don't trust the names, trust signatures.

// Non-functional example. Is the customer being changed?
customer.SetName(newName);

// Customer is being changed as it is returned.
let newCustomer = setCustomerName(customer, newName)

// You can tell there is something wrong with this function.
// Why would getting customer name change the customer?
let name, newCustomer = getCustomerName(customer)

Pure functions work as maps. There is only one result for every parameter. Functions have referential transparency, which means that you can replace any function call with the value it returns.

(take 25 (squares-of (integers)))

; The take function takes two arguments, an integer n, and a list l.
; It returns the first n items of the list.

; The squares-of function takes a list of integers as its argument and
; returns a list of the squares of those integers.

; The integers function returns a list of integers in sequential order,
; starting at 1.

Pure functions are thread safe. Because of simple and predictable evaluation, omputation can be split easily, naturally utilizing multiple CPUs.

; This example uses five different evaluators to compute the result
; E = Evaluator.

E1: (+ 1 (- 3 2))
E1: +
E2: 1
E3: (- 3 2)
E3: -
E4: 3
E5: 2

Pure functions are more reusable. Because functions don't expect anything about the context, they can easily be used again and again.

Pure functions are more testable. Once again related to the context. If there is no context or state to be considered, testing a pure function is trivial.

There is no assignment operator. There cannot be assignments because problems would arise in parallel computation. You define values but they cannot be changed.

; Think about a hypothetical situation where 2 evaluators start
; processing different branches of the function and the second evaluators
; returns a wrong response because first function changes the value of n.
(fn [n]
    (assign n (+ 1 n))
    (+ n n)
)

Sources