Functional Programming

description: Programming using functional idioms

lang: ENG

Programming with Functor, Applicative and Monad

Functor

Functors are here to send value into another space while "keeping" the same form.

 val map : ('a -> 'b) -> ('a t -> 'b t)
 let ( <$> ) = map

We can't code it like this, we need a property to not have:

 let map fn lst = []

FORALL fn lst,

  • assert (List.length lst = List.length (map fn lst)) map (fun x -> x) t = t map f (map g t) = map (fun x -> f (g x)) t

Applicative

Applicatives exist because with Functors, you can't combine things. With Applicatives you are able to combine the information to apply functions.

val pure/return/singleton : 'a -> 'a t
val pair : 'a t -> 'b t -> ('a * 'b) t

val apply : ('a -> 'b) t -> 'a t -> 'b t
let apply fn_t a_t = pair fn_t a_t |> map (fun (fn, a) -> fn a)
let ( <*> ) = apply

val liftA2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t let liftA2 fn a_t b_t = pair a_t b_t |> map (fun (a,b) -> fn a b)

((fn : 'a -> ...) <$> truc : 'a t) <*> bidule (fun t b m -> ...) <$> truc <*> bidule <*> machin

is equivalent to

let+ t = truc and+ b = bidule and+ m = machin in ...

is equivalent to

let+ t = truc
and+ (b, m) =
	let+ b = bidule
	and+ m = machin
	in (b, m)
in ...

We want this property to be true on Applicative:

map (fun (a, (b, c)) -> (a, b, c)) (pair at (pair bt ct)) == map (fun ((a, b), c) -> (a, b, c)) (pair (pair at bt) ct)

Stage functions

Partial applications are really useful. However, sometimes, you want to compute elements in the partial application and keep them in a closure. If you directly provide the function and let people partially applying it, nothing prevent them to recompute the closure every time.

This is where the stage trick comes in action. You simply define a module:

module Stage : sig
  type 'a t
  val staged : 'a -> 'a t
  val unstaged 'a t -> 'a

end = struct
  type 'a t = 'a
  let stage (fn : 'a) : 'a t = fn
  let unstage (fn : 'a t) : 'a' = fn
end

As the function type will be constraint in an abstract a t, there is no risk to execute the partial application without using the Stage.unstaged function.

Resources