Combinators and Pipelining
CSI 3120
Amy Felty University of Ottawa
slides copyright 2017, 2018 David Walker, Amy Felty
permission granted to reuse these slides for non-commercial educational purposes
1
FUNCTIONAL DECOMPOSITION
2
Functional Decomposition ==
Break down complex problems into a set of simple functions; Recombine (compose) functions to form solution
Such problems can often be solved using a combinator library. (a set of functions that fit together nicely)
The list library, which contains map and fold, is a combinator library. 3
PIPELINES
4
Pipe
let (|>) x f = f x
Type?
5
Pipe
let (|>) x f = f x
Type?
(|>) : ‘a -> (‘a -> ‘b) -> ‘b
6
let twice f x =
x |> f |> f
val twice : (‘a -> ‘a) -> ‘a -> ‘a =
Pipe
let (|>) x f = f x
7
let twice f x =
x |> f |> f
val twice : (‘a -> ‘a) -> ‘a -> ‘a =
Pipe
let (|>) x f = f x
leftassociative: x|>f1|>f2|>f3 == ((x|>f1)|>f2)|>f3
8
let twice f x =
x |> f |> f
let (|>) x f = f x
val twice : (‘a -> ‘a) -> ‘a -> ‘a =
let square x = x*x
val square : int -> int =
let fourth x = twice square x
val fourth : int -> int =
Pipe
9
let (|>) x f = f x
let twice f x = x |> f |> f
let square x = x*x
let fourth x = twice square x
let compute x =
x |> square
|> fourth
|> ( * ) 3
|> print_int
|> print_newline
Pipe
val compute : int -> unit =
10
let compute x =
x |> square
|> fourth
|> ( * ) 3
|> print_int
|> print_newline
# compute 8;;
50331648
– : unit = ()
# compute 3;;
19683
– : unit = ()
Pipe
11
PIPING LIST PROCESSORS
(Combining combinators cleverly)
12
Another Problem
type first = string
type last = string
type assign = float list
type final = float
type student = (first * last * assign * final)
let students : student list =
[(“Sarah”, “Jones”, [7.0;8.0;10.0;9.0], 8.5);
(“Qian”, “Xi”, [7.3;8.1;3.1;9.0], 6.5);
]
13
Another Problem
type first = string
type last = string
type assign = float list
type final = float
type student = (first * last * assign * final)
• Create a function display that does the following:
– for each student, print the following:
• last_name, first_name: score
• score is computed by averaging the assignments with the final
– each assignment is weighted equally
– the final counts for twice as much • one student printed per line
• students printed in order of score
14
Create a function display that
Another Problem
– takes a list of students as an argument
– prints the following for each student:
• last_name, first_name: score
• score is computed by averaging the assignments with the final
– each assignment is weighted equally
– the final counts for twice as much • one student printed per line
• students printed in order of score
let display (ss : student list) : unit =
ss |> compute score
|> sort by score
|> convert to list of strings
|> print each string
15
let compute_score (s:student) =
match s with
Another Problem
(f,l,grades,exam) ->
let sum x (num,tot) = (num +. 1., tot +. x) in
let score gs e =
List.fold_right sum gs (2., 2. *. e) in
let (number, total) = score grades exam in
(f, l, total /. number)
let display (ss : student list) : unit =
ss |> List.map compute_score
|> sort by score
|> convert to list of strings
|> print each string
16
Another Problem
let compare_score (_,_,score1) (_,_,score2) =
if score1 < score2 then 1
else if score1 > score2 then -1
else 0
let display (ss : student list) : unit =
ss |> List.map compute_score
|> List.sort compare_score
|> convert to list of strings
|> print each string
17
Another Problem
let stringify (first, last, score) =
last ^ “, ” ^ first ^ “: ” ^ string_of_float score
let display (ss : student list) : unit =
ss |> List.map compute_score
|> List.sort compare_score
|> List.map stringify
|> print each string
18
Another Problem
let stringify (first, last, score) =
last ^ “, ” ^ first ^ “: ” ^ string_of_float score
let display (ss : student list) : unit =
ss |> List.map compute_score
|> List.sort compare_score
|> List.map stringify
|> List.iter print_endline
19
COMBINATORS FOR OTHER TYPES: PAIRS
20
Simple Pair Combinators
let both f (x,y) = (f x, f y)
let do_fst f (x,y) = (f x, y) pair combinators letdo_sndf(x,y)=( x,fy)
val both : (‘a -> ‘b) -> ‘a * ‘a -> ‘b * ‘b =
val do_fst : (‘a -> ‘b) -> ‘a * ‘c -> ‘b * ‘c =
val do_snd : (‘a -> ‘b) -> ‘c * ‘a -> ‘c * ‘b =
21
Example: Piping Pairs
let both f (x,y) = (f x, f y) let do_fst f (x,y) = (f x, y) letdo_sndf(x,y)=( x,fy)
pair combinators
let even x = (x mod 2 = 0)
let process (p : float * float) =
p |> both int_of_float |> do_fst ((/) 30)
|> do_snd ((/) 20)
|> both even |>fun(x,y)->x&&y
(* convert to int *)
(* divide 30 by fst *)
(* divide 20 by snd *)
(* test for even *)
(* both even *)
22
Summary
• (|>) passes data from one function to the next
– compact, elegant, clear
• UNIX pipes (|) compose file processors
– unix scripting with | is a kind of functional programming
– but it isn’t very general since | is not polymorphic
– you have to serialize and unserialize your data at each step • there can be type (ie: file format) mismatches between steps
• Higher-order combinator libraries arranged around types:
– List combinators (map, fold, reduce, iter, …)
– Pair combinators (both, do_fst, do_snd, …)
– Network programming combinators (Frenetic: frenetic-lang.org)
23