fp

# Functional programming

## ¶[2016-06-20] What is functional programming? fp

• First-class and higher-order functions
• Pure functions
• Recursion (as a consequence of pure functions?)
• Strict versus non-strict evaluation
• Type systems
When do you choose functional programming over object oriented?
When you anticipate a different kind of software evolution:

Object-oriented languages are good when you have a fixed set of operations on things, and as your code evolves, you primarily add new things. This can be accomplished by adding new classes which implement existing methods, and the existing classes are left alone.

Functional languages are good when you have a fixed set of things, and as your code evolves, you primarily add new operations on existing things. This can be accomplished by adding new functions which compute with existing data types, and the existing functions are left alone.

When evolution goes the wrong way, you have problems:

- Adding a new operation to an object-oriented program may require editing many class definitions to add a new method.
- Adding a new kind of thing to a functional program may require editing many function definitions to add a new case.


Earlier I said that the key to a monad is its Kleisli arrows. The reason why is that Kleisli arrows are morphisms in the Kleisli category, where (>=>) is Kleisli arrow composition:

(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> (a -> m c)
(f >=> g) x = f x >>= g
.. and return is the identity:
return :: (Monad m) => a -> m a


Like all categories, the Kleisli category must obey the category laws:

return >=> f = f                   -- Left identity
f >=> return = f                   -- Right identity
(f >=> g) >=> h = f >=> (g >=> h)  -- Associativity


## ¶[2016-09-25] parametricity fp

In a parametric language the presence of a universally quantified type variable intuitively conveys a very strong guarantee: A (part of a) value passed to a parametric polymorphic function in the position of a type variable is guaranteed only to be copied and moved around, but never inspected in the function


## ¶[2016-08-07] semantics fp

Denotational semantics: natural, maps to mathematical domains
Operational semantics: describes execution on an abstract machine

• Small step / big step

Denotational semantics is similar to high-level operational semantics, except:

• Machine is gone
• Language is mathematics (lambda calculus)

The difference between denotational and operational semantics:

• In operational semantics, the state changes are defined by coded algorithms for a virtual machine
• In denotational semantics, they are defined by rigorous mathematical functions

## ¶[2015-06-20] foldl vs foldr fp

-- Left fold:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z []   = z
foldl f z (x:xs) = foldl f (f z x) xs

-- Tail recurstion, but recurses forever if the list is infinite.
-- Might cause OOM due to enormous thunks.

foldl' : strict version
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f !z [] = z
foldl' f !z (x: xs) = foldl' f (f z x) xs

-- Right fold:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)


foldr: under lazy evaluation, may stop early and thus can deal with infinite lists.
Might cause OOM: foldr (+) 0 [1..1000000]

TODO: internal thunk stack?

## ¶[2015-06-20] let polymorphism http://stackoverflow.com/a/12033549/706389fp

We might want to define
let x = expr in t
as (\x.t) expr

We've got to assign a concrete type to f (TODO why?), which means it can't be forall a.a -> a

Instead, we define it as a primitive:

\Gamma \vdash expr: S; \Gamma \vdash t[x -> expr]: T
----------------------------------------------
\Gamma \vdash let x = expr in t: T

\Gamma vdash expr:S to assure typability of expr at all.


A key insight in this matter is that rather than just typing a lambda-abstraction with a potentially polymorphic argument type, we are typing a (sugared) abstraction that is (1) applied exactly once and, moreover, that is (2) applied to a statically known argument. That is, we can first subject the "argument" (i.e. the definiens of the local definition) to type reconstruction to find its (polymorphic) type; then assign the found type to the "parameter" (the definiendum); and then, finally, type the body in the extended type context.

Basically, we can write polymorphic functions, but can't use arguments in polymorphic way.

Note that it's perfectly possible to pass a polymorphic function as an argument to another function. So something like map id ["a","b","c"] is perfectly legal. But the function may only use it as monomorphic. In the example map uses id as if it had type String -> String

## ¶[2021-01-01]Bartosz Milewski (@BartoszMilewski): "Starting the new year with a new project: The Dao of Functional Programming. Here's a short intro." | nitterfp

Starting the new year with a new project: The Dao of Functional Programming. Here's a short intro.


## ¶TODO[D][2018-11-27] Pinboard: bookmarks for karlicoss tagged 'fp' fp

data Obj = forall a. (Show a) => Obj a

xs :: [Obj]
xs = [Obj 1, Obj "foo", Obj 'c']

doShow :: [Obj] -> String
doShow [] = ""
doShow ((Obj x):xs) = show x ++ doShow xs


Dynamic dispatch:

 class Shape_ a where
perimeter :: a -> Double
area      :: a -> Double

data Shape = forall a. Shape_ a => Shape a

type Side   = Double

data Rectangle = Rectangle Side Side
data Square    = Square    Side

instance Shape_ Circle where
perimeter (Circle r) = 2 * pi * r
area      (Circle r) = pi * r * r

instance Shape_ Rectangle where
perimeter (Rectangle x y) = 2 * (x + y)
area      (Rectangle x y) = x * y

instance Shape_ Square where
perimeter (Square s) = 4*s
area      (Square s) = s*s

instance Shape_ Shape where
perimeter (Shape shape) = perimeter shape
area      (Shape shape) = area      shape

-- Smart constructor:

circle r = Shape (Circle r)

rectangle :: Side -> Side -> Shape
rectangle x y = Shape (Rectangle x y)

square :: Side -> Shape
square s = Shape (Square s)

shapes :: [Shape]
shapes = [circle 2.4, rectangle 3.1 4.4, square 2.1]


forall r . ((a -> r) -> f r) ~ f a, where f is a functor

fun :: forall r . ((Bool -> r) -> [r]