Day02_types
Separate Compilation
Types
Compound Types
Inductive rgb : Type :=
| red
| green
| blue.
Inductive color : Type :=
| black
| white
| primary (p : rgb).
| red
| green
| blue.
Inductive color : Type :=
| black
| white
| primary (p : rgb).
Let's look at this in a little more detail.
Every inductively defined type (day, bool, rgb, color,
etc.) contains a set of constructor expressions built from
constructors like red, primary, true, false, monday,
etc. The definitions of rgb and color say how expressions in
the sets rgb and color can be built:
We can define functions on colors using pattern matching just as
we have done for day and bool.
- red, green, and blue are the constructors of rgb;
- black, white, and primary are the constructors of color;
- the expression red belongs to the set rgb, as do the expressions green and blue;
- the expressions black and white belong to the set color;
- if p is an expression belonging to the set rgb, then primary p (pronounced "the constructor primary applied to the argument p") is an expression belonging to the set color; and
- expressions formed in these ways are the only ones belonging to the sets rgb and color.
Definition monochrome (c : color) : bool :=
match c with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end.
match c with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end.
Since the primary constructor takes an argument, a pattern
matching primary should include either a variable (as above) or
a constant of appropriate type (as below).
How does monochrome white evaluate? We can write out the
computation like so, simulating the way Coq works:
monochrome white
match white with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end Coq considers each case in turn, comparing the scrutinee (here, white) against the patterns (here, black, white, and primary p).
The scrutinee will always be a value; the pattern will be a mix of
constructors and variable names. The match construct tries to
match the scrutinee to each pattern, where a match is when every
constructor is matched with an identical constructor or a
variable.
Concretely, the scrutinee white doesn't match the pattern
black, because white and black are different
constructors. So Coq will skip that case, and keep evaluating:
match white with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end
match white with
| white ⇒ true
| primary p ⇒ false
end We're being particularly careful with our computation steps---as we gain facility with Coq, we won't need to step each case. But here it helps us see that each pattern is considered in turn, from top to bottom.
The next pattern is white, which matches our scrutinee white,
so our pattern matches and we can execute the code in that branch
of the match:
match white with
| white ⇒ true
| primary p ⇒ false
end
true In this case, there were no variables in the match to keep track of, but in general, Coq will bind each variable in a pattern to the corresponding part of the scrutinee. For example, suppose we had run monochrome (primary blue):
monochrome (primary blue)
match (primary blue) with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end
match (primary blue) with
| white ⇒ true
| primary p ⇒ false
end
match (primary blue) with
| primary p ⇒ false
end At this point, the argument to the primary constructor, blue, in the scrutinee corresponds to the variable p in the pattern primary p. So what Coq will do is evaluate the corresponding branch of the match, remember that p is equal to blue. (In this case, p doesn't occur at all on the right-hand side of ⇒, so it doesn't matter. But it could!)
match (primary blue) with
| primary p ⇒ false
end
false (* with p bound to blue *)
monochrome white
computes to
match white with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end Coq considers each case in turn, comparing the scrutinee (here, white) against the patterns (here, black, white, and primary p).
match white with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end
computes to
match white with
| white ⇒ true
| primary p ⇒ false
end We're being particularly careful with our computation steps---as we gain facility with Coq, we won't need to step each case. But here it helps us see that each pattern is considered in turn, from top to bottom.
match white with
| white ⇒ true
| primary p ⇒ false
end
computes to
true In this case, there were no variables in the match to keep track of, but in general, Coq will bind each variable in a pattern to the corresponding part of the scrutinee. For example, suppose we had run monochrome (primary blue):
monochrome (primary blue)
computes to
match (primary blue) with
| black ⇒ true
| white ⇒ true
| primary p ⇒ false
end
computes to
match (primary blue) with
| white ⇒ true
| primary p ⇒ false
end
computes to
match (primary blue) with
| primary p ⇒ false
end At this point, the argument to the primary constructor, blue, in the scrutinee corresponds to the variable p in the pattern primary p. So what Coq will do is evaluate the corresponding branch of the match, remember that p is equal to blue. (In this case, p doesn't occur at all on the right-hand side of ⇒, so it doesn't matter. But it could!)
match (primary blue) with
| primary p ⇒ false
end
computes to
false (* with p bound to blue *)
Definition isred (c : color) : bool :=
match c with
| black ⇒ false
| white ⇒ false
| primary red ⇒ true
| primary _ ⇒ false
end.
match c with
| black ⇒ false
| white ⇒ false
| primary red ⇒ true
| primary _ ⇒ false
end.
The pattern primary _ here is shorthand for "primary applied
to any rgb constructor except red." Recall again that Coq
applies patterns in order. For example:
isred (primary green)
computes to
match (primary green) with
| black ⇒ false
| white ⇒ false
| primary red ⇒ true
| primary _ ⇒ false
computes to
match (primary green) with
| white ⇒ false
| primary red ⇒ true
| primary _ ⇒ false
computes to
match (primary green) with
| primary red ⇒ true
| primary _ ⇒ false At this point, our scrutinee primary green doesn't match the pattern primary red: while the outermost constructors are both primary, the arguments differ: green and red are different constructors of color. So Coq will skip this pattern:
match (primary green) with
| primary red ⇒ true
| primary _ ⇒ false
computes to
match (primary green) with
| primary _ ⇒ false
computes to
false In this case, the wildcard pattern _ has the same effect as the dummy pattern variable p in the definition of monochrome. Both functions don't actually use the argument to primary. We could have written isred a different way:
isred (primary green)
match (primary green) with
| black ⇒ false
| white ⇒ false
| primary red ⇒ true
| primary _ ⇒ false
match (primary green) with
| white ⇒ false
| primary red ⇒ true
| primary _ ⇒ false
match (primary green) with
| primary red ⇒ true
| primary _ ⇒ false At this point, our scrutinee primary green doesn't match the pattern primary red: while the outermost constructors are both primary, the arguments differ: green and red are different constructors of color. So Coq will skip this pattern:
match (primary green) with
| primary red ⇒ true
| primary _ ⇒ false
match (primary green) with
| primary _ ⇒ false
false In this case, the wildcard pattern _ has the same effect as the dummy pattern variable p in the definition of monochrome. Both functions don't actually use the argument to primary. We could have written isred a different way:
Definition isred' (c : color) : bool :=
match c with
| black ⇒ false
| white ⇒ false
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end.
match c with
| black ⇒ false
| white ⇒ false
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end.
In this definition, we explicitly name the primary color we're
working with and do a nested pattern match. We can compute
isred' (primary green) as follows:
isred' (primary green)
computes to
match (primary green) with
| black ⇒ false
| white ⇒ false
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end
computes to
match (primary green) with
| white ⇒ false
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end
computes to
match (primary green) with
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end
computes to
match green with
| red ⇒ true
| _ ⇒ false
end
computes to
match green with
| _ ⇒ false
end
computes to
false It's good practice to use wildcards when you don't need to name the variable---it helps prevent mistakes, like referring to the wrong variable. Do keep in mind, though: patterns are matched top to bottom. An early wildcard may rule out later cases! Coq should warn you if this is the case.
It's also good practice to try to condense pattern matching: the definition
of isred is cleaner than that of isred'.
isred' (primary green)
match (primary green) with
| black ⇒ false
| white ⇒ false
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end
match (primary green) with
| white ⇒ false
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end
match (primary green) with
| primary p ⇒
match p with
| red ⇒ true
| _ ⇒ false
end
end
match green with
| red ⇒ true
| _ ⇒ false
end
match green with
| _ ⇒ false
end
false It's good practice to use wildcards when you don't need to name the variable---it helps prevent mistakes, like referring to the wrong variable. Do keep in mind, though: patterns are matched top to bottom. An early wildcard may rule out later cases! Coq should warn you if this is the case.
Exercise: 1 star, standard (is_weekday')
Define a function is_weekday' that behaves like is_weekday but has fewer than four cases. Remember: the order of cases matters!
Definition is_weekday' (d:day) : bool (* REPLACE THIS LINE WITH ":= _your_definition_ ." *). Admitted.
☐
☐
Modules
Numbers
- zero (i.e., no tick marks), or
- a natural number followed by another tick mark.
The clauses of this definition can be read:
Again, let's look at this in a little more detail. The definition
of nat says how expressions in the set nat can be built:
The same rules apply for our definitions of day, bool,
color, etc.
The above conditions are the precise force of the Inductive
declaration. They imply that the expression O, the expression
S O, the expression S (S O), the expression S (S (S O)), and
so on all belong to the set nat, while other expressions built
from data constructors, like true, andb true false, S (S
false), and O (O (O S)) do not.
A critical point here is that what we've done so far is just to
define a representation of numbers: a way of writing them down.
The names O and S are arbitrary, and at this point they have
no special meaning -- they are just two different marks that we
can use to write down numbers (together with a rule that says any
nat will be written as some string of S marks followed by an
O). If we like, we can write essentially the same definition
this way:
- O is a natural number (note that this is the letter "O," not the numeral "0").
- S can be put in front of a natural number to yield another one -- if n is a natural number, then S n is too.
- O and S are constructors;
- the expression O belongs to the set nat;
- if n is an expression belonging to the set nat, then S n is also an expression belonging to the set nat; and
- expressions formed in these two ways are the only ones belonging to the set nat.
The interpretation of these marks comes from how we use them to
compute. We use O and S rather than these longer names because
(a) concision is nice, (b) we'll be using nat quite a bit, and
(c) that's how the Coq standard library defines them.
We interpret by writing functions that pattern match on
representations of natural numbers just as we did above with
booleans and days -- for example, here is the predecessor
function, which takes a given number and returns one less than
that number, i.e.,
pred (S n) should compute to n
For example, pred (S O) computes to O, i.e., 0 is the predecessor
of 1.
Our definition has an unfortunate property: pred O computes to
O, i.e., 0 is its own predecessor. A mathematician might take a
different course of action, saying that pred O is
undefined---there really is no natural number that comes before 0,
since 0 is the first one! Coq won't let us leave anything
undefined, though, so we'll simply have to be careful to remember
that pred O = O.
The second branch can be read: "if n has the form S n'
for some n', then return n'."
Because natural numbers are such a pervasive form of data,
Coq provides a tiny bit of built-in magic for parsing and printing
them: ordinary arabic numerals can be used as an alternative to
the "unary" notation defined by the constructors S and O. Coq
prints numbers in arabic form by default:
Check (S (S (S (S O)))).
(* ===> 4 : nat *)
Definition minustwo (n : nat) : nat :=
match n with
| O ⇒ O
| S O ⇒ O
| S (S n') ⇒ n'
end.
Compute (minustwo 4).
(* ===> 2 : nat *)
(* ===> 4 : nat *)
Definition minustwo (n : nat) : nat :=
match n with
| O ⇒ O
| S O ⇒ O
| S (S n') ⇒ n'
end.
Compute (minustwo 4).
(* ===> 2 : nat *)
The constructor S has the type nat → nat, just like
pred and functions like minustwo:
These are all things that can be applied to a number to yield a
number. However, there is a fundamental difference between the
first one and the other two: functions like pred and minustwo
come with computation rules -- e.g., the definition of pred
says that pred 2 can be simplified to 1 -- while the
definition of S has no such behavior attached. Although it is
like a function in the sense that it can be applied to an
argument, it does not do anything at all! It is just a way of
writing down numbers. (Think about standard arabic numerals: the
numeral 1 is not a computation; it's a piece of data. When we
write 111 to mean the number one hundred and eleven, we are
using 1, three times, to write down a concrete representation of
a number.)
For most function definitions over numbers, just pattern matching
is not enough: we also need recursion, i.e., functions that
refer to themselves. For example, to check that a number n is
even, we may need to recursively check whether n-2 is even. To
write such functions, we use the keyword Fixpoint.
In your prior programming experience, you may not have spent a lot
of thought on recursion. Many languages use loops (using words
like while or for) rather than recursion. Coq doesn't have
loops---only recursion. Don't worry if you're not particularly
familiar with recursion... you'll get lots of practice!
The call to evenb n' is a recursive call. One might
worry: is it okay to define a function in terms of itself? How do
we know that evenb terminates?
We can check an example: is 3 even?
evenb 3
is the same as
evenb (S (S (S O)))
computes to
match (S (S (S O))) with
| O ⇒ true
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
computes to
match (S (S (S O))) with
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
computes to
match (S (S (S O))) with
| S (S n') ⇒ evenb n'
end
computes to
evenb n' (* with n' bound to S O *)
is the same as
evenb (S 0)
computes to
match (S O) with
| O ⇒ true
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
computes to
match (S O) with
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
computes to
false More generally, evenb only ever makes recursive calls on smaller inputs: if we put in the number n, we'll make a recursive call on two less than n.
A surprising fact: Coq will only let us write functions that are
guaranteed to terminate on all inputs. A good rule of thumb is
that every recursive function should make a recursive call only on
subparts of its input.
We can define oddb by a similar Fixpoint declaration, but here
is a simpler definition:
evenb 3
evenb (S (S (S O)))
match (S (S (S O))) with
| O ⇒ true
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
match (S (S (S O))) with
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
match (S (S (S O))) with
| S (S n') ⇒ evenb n'
end
evenb n' (* with n' bound to S O *)
evenb (S 0)
match (S O) with
| O ⇒ true
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
match (S O) with
| S O ⇒ false
| S (S n') ⇒ evenb n'
end
false More generally, evenb only ever makes recursive calls on smaller inputs: if we put in the number n, we'll make a recursive call on two less than n.
Definition oddb (n:nat) : bool := negb (evenb n).
Compute (oddb 1).
Compute (oddb 4).
Module NatPlayground2.
Fixpoint plus (n : nat) (m : nat) : nat :=
match n with
| O ⇒ m
| S n' ⇒ S (plus n' m)
end.
Compute (oddb 1).
Compute (oddb 4).
Module NatPlayground2.
Fixpoint plus (n : nat) (m : nat) : nat :=
match n with
| O ⇒ m
| S n' ⇒ S (plus n' m)
end.
Adding three to two now gives us five, as we'd expect.
The simplification that Coq performs to reach this
conclusion can be visualized as follows, a little more succinctly
than what we wrote above:
(* plus (S (S (S O))) (S (S O))
==> S (plus (S (S O)) (S (S O)))
by the second clause of the match
==> S (S (plus (S O) (S (S O))))
by the second clause of the match
==> S (S (S (plus O (S (S O)))))
by the second clause of the match
==> S (S (S (S (S O))))
by the first clause of the match
*)
==> S (plus (S (S O)) (S (S O)))
by the second clause of the match
==> S (S (plus (S O) (S (S O))))
by the second clause of the match
==> S (S (S (plus O (S (S O)))))
by the second clause of the match
==> S (S (S (S (S O))))
by the first clause of the match
*)
As a notational convenience, if two or more arguments have
the same type, they can be written together. In the following
definition, (n m : nat) means just the same as if we had written
(n : nat) (m : nat).
Fixpoint mult (n m : nat) : nat :=
match n with
| O ⇒ O
| S n' ⇒ plus m (mult n' m)
end.
Compute (mult 3 3).
Compute (mult 5 2).
match n with
| O ⇒ O
| S n' ⇒ plus m (mult n' m)
end.
Compute (mult 3 3).
Compute (mult 5 2).
You can match two expressions at once by putting a comma
between them:
Fixpoint minus (n m:nat) : nat :=
match n, m with
| O , _ ⇒ O
| S _ , O ⇒ n
| S n', S m' ⇒ minus n' m'
end.
match n, m with
| O , _ ⇒ O
| S _ , O ⇒ n
| S n', S m' ⇒ minus n' m'
end.
Our minus function has the same problem pred does: minus 0 n
results in 0! This 'truncating' subtraction is necessary because
we're working with natural numbers, i.e., there are no negative
numbers.
Keep in mind: these definitions have suggestive names, but it's up
to us as humans to agree that minus corresponds to our notion of
subtraction. I would wager that it does: if we pick an n and an
m such that m ≤ n, then minus n m yields n - m. We
don't have the tools to prove this... yet!
Again, the _ in the first line is a wildcard pattern. Writing
_ in a pattern is the same as writing some variable that doesn't
get used on the right-hand side. This avoids the need to invent a
variable name.
The pow function defines exponentiation: exp n m should yield
n to the mth power.
Exercise: 1 star, standard (factorial)
Here's the standard mathematical factorial function:factorial(0) = 1 factorial(n) = n * factorial(n-1) (if n>0)
Compute (factorial 3).
Compute (factorial 5).
Notation "x + y" := (plus x y)
(at level 50, left associativity)
: nat_scope.
Notation "x - y" := (minus x y)
(at level 50, left associativity)
: nat_scope.
Notation "x * y" := (mult x y)
(at level 40, left associativity)
: nat_scope.
Check ((0 + 1) + 1).
Compute (factorial 5).
Notation "x + y" := (plus x y)
(at level 50, left associativity)
: nat_scope.
Notation "x - y" := (minus x y)
(at level 50, left associativity)
: nat_scope.
Notation "x * y" := (mult x y)
(at level 40, left associativity)
: nat_scope.
Check ((0 + 1) + 1).
(The level, associativity, and nat_scope annotations
control how these notations are treated by Coq's parser. The
details are not important for our purposes, but interested readers
can refer to the optional "More on Notation" section at the end of
this chapter.)
Note that these do not change the definitions we've already made:
they are simply instructions to the Coq parser to accept x + y
in place of plus x y and, conversely, to the Coq pretty-printer
to display plus x y as x + y.
Comparisons
Fixpoint eqb (n m : nat) : bool :=
match n with
| O ⇒ match m with
| O ⇒ true
| S m' ⇒ false
end
| S n' ⇒ match m with
| O ⇒ false
| S m' ⇒ eqb n' m'
end
end.
match n with
| O ⇒ match m with
| O ⇒ true
| S m' ⇒ false
end
| S n' ⇒ match m with
| O ⇒ false
| S m' ⇒ eqb n' m'
end
end.
The leb function tests whether its first argument is less than or
equal to its second argument, yielding a boolean.
Exercise: 2 stars, standard (leb)
Fixpoint leb (n m : nat) : bool (* REPLACE THIS LINE WITH ":= _your_definition_ ." *). Admitted.
(* Do not modify the following line: *)
Definition manual_grade_for_test_leb : option (nat×string) := None.
☐
(* Do not modify the following line: *)
Definition manual_grade_for_test_leb : option (nat×string) := None.
☐
Exercise: 1 star, standard (ltb)
The blt_nat function tests natural numbers for less-than, yielding a boolean. Instead of making up a new Fixpoint for this one, define it in terms of a previously defined function.
Definition ltb (n m : nat) : bool
(* REPLACE THIS LINE WITH ":= _your_definition_ ." *). Admitted.
(* Do not modify the following line: *)
Definition manual_grade_for_ltb : option (nat×string) := None.
☐
(* REPLACE THIS LINE WITH ":= _your_definition_ ." *). Admitted.
(* Do not modify the following line: *)
Definition manual_grade_for_ltb : option (nat×string) := None.
☐
We can define a notion of minimum.
We can lift this definition to talk about three things. Here's a
lifting via a total rewrite:
Definition min3 (n1 n2 n3 : nat) : nat :=
if leb n1 n2
then if leb n1 n3
then n1
else n3
else if leb n2 n3
then n2
else n3.
if leb n1 n2
then if leb n1 n3
then n1
else n3
else if leb n2 n3
then n2
else n3.
And here's how we'd reuse the existing definition. Do you suppose
this is equivalent to min (min n1 n2) n3?
When Coq checks this definition, it notes that plus' is
"decreasing on 1st argument." What this means is that we are
performing a structural recursion over the argument n -- i.e.,
that we make recursive calls only on strictly smaller values of
n. This implies that all calls to plus' will eventually
terminate. Coq demands that some argument of every Fixpoint
definition is "decreasing."
This requirement is a fundamental feature of Coq's design: In
particular, it guarantees that every function that can be defined
in Coq will terminate on all inputs. However, because Coq's
"decreasing analysis" is not very sophisticated, it is sometimes
necessary to write functions in slightly unnatural ways.
You can write it Fail Fixpoint ... to ensure it fails to compile!
Exercise: 2 stars, standard (decreasing)
To get a concrete sense of this, find a way to write a sensible Fixpoint definition (of a simple function on numbers, say) that does terminate on all inputs, but that Coq will reject because of this restriction.
(* FILL IN HERE *)
(* Do not modify the following line: *)
Definition manual_grade_for_decreasing : option (nat×string) := None.
☐
(* Do not modify the following line: *)
Definition manual_grade_for_decreasing : option (nat×string) := None.
☐
Functions as Data
Higher-Order Functions
The argument f here is itself a function (from X to
X); the body of doit3times applies f three times to some
value n.
Check doit3times : (nat → nat) → nat → nat.
Compute (doit3times minustwo 9). (* ==> 3 *)
Compute (doit3times (fun n ⇒ S n) 2). (* ==> 5 *)
Compute (doit3times minustwo 9). (* ==> 3 *)
Compute (doit3times (fun n ⇒ S n) 2). (* ==> 5 *)
Note that fun n ⇒ S n is morally equivalent to just S:
We can construct a function "on the fly" without declaring it at
the top level or giving it a name.
The expression (fun n ⇒ n + n) can be read as "the function
that, given a number n, yields n + n", i.e., a function that
doubles its input.
Work out on paper how doit3times (fun n ⇒ n + n) 2
evaluate. Here are the first few steps:
doit3times (fun n ⇒ n + n) 2
]] =
[[
(fun n ⇒ n + n) ((fun n ⇒ n + n) ((fun n ⇒ n + n) 2))
]] =
[[
(fun n ⇒ n + n) ((fun n ⇒ n + n) (2 + 2)) Pick up from here. Note: there's more than one way to do this, but you should get the same answer no matter what.
We can use the fix keyword instead of fun to define a
recursive function on the fly. We'll have to give a name to it,
though.
doit3times (fun n ⇒ n + n) 2
]] =
[[
(fun n ⇒ n + n) ((fun n ⇒ n + n) ((fun n ⇒ n + n) 2))
]] =
[[
(fun n ⇒ n + n) ((fun n ⇒ n + n) (2 + 2)) Pick up from here. Note: there's more than one way to do this, but you should get the same answer no matter what.
Check (fix evenb' (n : nat) : bool :=
match n with
| O ⇒ true
| S O ⇒ false
| S (S n') ⇒ evenb' n'
end).
match n with
| O ⇒ true
| S O ⇒ false
| S (S n') ⇒ evenb' n'
end).
Let's think back to min in the last section. min only works
on numbers, so using it can be a little tedious---and sometimes
not really what we want. For example, if we want to find the
least unhealthy thing on a fast food menu, we could convert the
food items to calorie counts or something and then take the min
of those; but then we'd have to figure out which food item had
which calorie count, which is awkward. Instead, we can define a
new function argmin, which yields the least of its arguments
according to a given cost function.
We'll meet the {A : Type} syntax in detail later; for now, just
read it as saying "This function works for any type A, given a
cost function computing a nat for any A".
This next definition uses the let ... in form to define a
local variable; Definition and Fixpoint give you new top-level
definitions, but let is how you get new local
definitions. (Well, each branch of a match has its own
definitions, but that's not exactly the same!)
The general syntax is:
let NAME : TYPE := EXPR in
EXPR
let NAME : TYPE := EXPR in
EXPR
Definition argmin {A:Type} (cost : A → nat) (o1 o2 : A) : A :=
let c1 := cost o1 in
let c2 := cost o2 in
if leb c1 c2
then o1
else o2.
let c1 := cost o1 in
let c2 := cost o2 in
if leb c1 c2
then o1
else o2.
As with min, we can lift it either by rewriting it to take three
arguments:
Definition argmin3 {A:Type} (cost : A → nat) (o1 o2 o3 : A) : A :=
let c1 := cost o1 in
let c2 := cost o2 in
let c3 := cost o3 in
if leb c1 c2
then if leb c1 c3
then o1
else o3
else if leb c2 c3
then o2
else o3.
let c1 := cost o1 in
let c2 := cost o2 in
let c3 := cost o3 in
if leb c1 c2
then if leb c1 c3
then o1
else o3
else if leb c2 c3
then o2
else o3.
Or by using the definition we had lying around already:
Definition argmin3' {A:Type} (cost : A → nat) (o1 o2 o3 : A) : A :=
argmin cost o1 (argmin cost o2 o3).
argmin cost o1 (argmin cost o2 o3).
Functions That Construct Functions
Definition constfun {X: Type} (x: X) : nat→X :=
fun (k:nat) ⇒ x.
Definition ftrue := constfun true.
Compute ftrue 0. (* ===> true *)
Compute (constfun 5) 99. (* ===> 5 *)
fun (k:nat) ⇒ x.
Definition ftrue := constfun true.
Compute ftrue 0. (* ===> true *)
Compute (constfun 5) 99. (* ===> 5 *)
In fact, the multiple-argument functions we have already
seen are also examples of passing functions as data. To see why,
recall the type of plus.
Each → in this expression is actually a binary operator
on types. This operator is right-associative, so the type of
plus is really a shorthand for nat → (nat → nat) -- i.e., it
can be read as saying that "plus is a one-argument function that
takes a nat and returns a one-argument function that takes
another nat and returns a nat." In the examples above, we
have always applied plus to both of its arguments at once, but
if we like we can supply just the first. This is called partial
application.
Definition plus3 := plus 3.
Check plus3 : nat → nat.
Compute (plus3 4). (* ==> 7 *)
Compute (doit3times plus3 0). (* ==> 9 *)
Compute (doit3times (plus 3) 0). (* ==> 9 *)
Check plus3 : nat → nat.
Compute (plus3 4). (* ==> 7 *)
Compute (doit3times plus3 0). (* ==> 9 *)
Compute (doit3times (plus 3) 0). (* ==> 9 *)
Exercise: 1 star, standard (partial_app_minus)
Partial application is a powerful tool, used frequently by functional programmers. It can be very confusing at first, though. Explain what answer you might expect just from reading the code. Why do we get the answer we do?
Compute (doit3times (minus 1) 10).
(* FILL IN HERE *)
(* Do not modify the following line: *)
Definition manual_grade_for_partial_app_minus : option (nat×string) := None.
☐
(* FILL IN HERE *)
(* Do not modify the following line: *)
Definition manual_grade_for_partial_app_minus : option (nat×string) := None.
☐
(* 2021-10-04 14:37 *)