Dive C1.03.1

Functions as values

A function is data: name it, pass it, return it — the same status an integer has.

F# treats a function as an ordinary value. A named binding and an anonymous lambda differ only in spelling; both produce a value with a function type. That single fact powers the rest: a function can be bound to a name, handed to another function as an argument, and returned from one. The functions that take or return other functions are called higher-order, and List.map is the one every F# program reaches for first.

Map a function Module hub

C1.03.1 · part 1

A binding and a lambda are both values

Two ways to write the same thing. The let form names a function; the fun form writes one with no name. Each evaluates to a value, and F# infers the type — the comment on each line is what the F# Interactive prints back.

let add x y = x + y          // val add : int -> int -> int
let inc = fun x -> x + 1     // val inc : int -> int

let square x = x * x          // val square : int -> int
square 5                     // 25

Because inc is bound to a lambda, nothing about it is special: it is a value of type int -> int that happens to be a function. The same binding form would give a name to the integer 42 or the function add.

let f x = …: names a function; the body computes the result from the parameter.
fun x -> …: an anonymous function (a lambda) — a value with a function type, no name.
int -> int: a function type: takes an int, returns an int.
higher-order: a function that takes a function as an argument, returns one, or both.

F# infers the type from how a value is used. add x y = x + y over integers gives int -> int -> int without a single annotation written by hand.

C1.03.1 · part 2

Passing a function and returning one

If a function is a value, it can be an argument. The function apply below takes a function f and a value x and calls f on x. F# infers a generic type — it works for any f whose input matches x.

let square x = x * x
let apply f x = f x          // val apply : ('a -> 'b) -> 'a -> 'b

apply square 5               // 25
List.map square [1; 2; 3]    // [1; 4; 9]

The type of apply reads: given a function from 'a to 'b and a value of type 'a, it returns a 'b. The lowercase 'a and 'b are type variables — apply places no constraint beyond the shapes lining up.

List.map is the canonical higher-order function: it takes a function and a list, and returns a new list with the function applied to every element. Its type is List.map : ('a -> 'b) -> 'a list -> 'b list. The function arrow associates to the right, so the first arrow groups ('a -> 'b) as a single argument — the function being mapped.

Function types read right-associatively. ('a -> 'b) -> 'a list -> 'b list is ('a -> 'b) -> ('a list -> 'b list) — give List.map a function, and a list-to-list function comes back. Dive C1.03.2 follows that right-association in full.

A higher-order playground: `List.map`

Pick a function and watch List.map apply it across a fixed list. The list is [1; 2; 3; 4; 5] throughout; only the function passed in changes. The readout shows the F# line and the list it evaluates to.

List.map f [1; 2; 3; 4; 5] · choose the function f

F# List.map square [1; 2; 3; 4; 5] = [1; 4; 9; 16; 25]

Mapping does not loop by hand; it hands a function to List.map and lets it walk the list. The function is the argument, so changing the result means passing a different value.

The idea

A function is a value, so it can be passed to another function as an argument.

F# today

List.map square xs passes square — a value — into List.map.

Where this leads

Functions are values, and higher-order functions take and return them. The next question is what the type int -> int -> int means when a function looks like it takes two arguments. The answer is currying: it takes one and returns a function that takes the next. Dive C1.03.2 reads that type the way F# means it; C1.03.3 then supplies one argument and keeps the function that comes back.

↑ C1.03 · Functions C1.03.2 · Currying → C1.03.3 · Partial application

References

Sources

Microsoft — F# documentation — functions, lambdas, and first-class values in F#.
FSharp.Core API reference — List.map and the higher-order list functions.
The F# Language Specification — function types and type inference.

Related in this course

C1.03.2 — Currying — reading int -> int -> int the way F# means it.
C1.03 — Functions — the module hub and its three dives.
Elixir — Functions — first-class and anonymous functions on the BEAM.