Higher-order functions
A combinator runs function values in a pattern that stack code keeps repeating: run this
under the top value, run that and keep the value, run both of these on the same value. Quadrate
has ten built in, and the hof module has a few more.
Why combinators?
Stack code often needs to:
- run several operations on the same value
- keep a value while also working on it
- get a value out of the way for a moment
Without combinators, that is what named locals are for:
fn main() {
// Is n both positive and even?
6 -> n
n 0 > -> is_positive
n 2 % 0 == -> is_even
is_positive is_even and print nl // 1
}
With one, the value never needs a name:
fn main() {
6 fn { 0 > } fn { 2 % 0 == } bi and print nl // 1
}
The function values are written fn { … }, with no signature: each one works on the stack, and
the compiler works out what it takes and leaves (see
Anonymous functions). Written right before the
combinator like this, the body is checked against the real stack and compiled inline: there is
no function value at run time at all.
Running function values on the stack
These run a function value on the stack as it is. The function value may take and leave any number of values.
dip
Run a function value on what is under the top value, then put the top value back.
fn main() {
10 20 fn { 2 * } dip
print nl print nl // 20 then 20 (20 set aside, 10 doubled)
1 2 3 fn { + } dip
print nl print nl // 3 then 3 (1 2 added under the 3)
}
keep
Run a function value on the top value, and keep that value.
fn main() {
5 fn { 2 * } keep
print nl print nl // 5 then 10
}
dip2 and keep2
The same for two values: dip2 runs a function value on what is under the top two and puts
them back; keep2 runs it on the top two and keeps them.
fn main() {
1 2 3 fn { 10 * } dip2
print nl print nl print nl // 3 then 2 then 10
2 3 fn { * } keep2
print nl print nl print nl // 3 then 2 then 6
}
bi and tri
Run two (or three) function values on the same value, one after the other.
fn main() {
5 fn { 2 * } fn { 3 + } bi
print nl print nl // 8 then 10
5 fn { 1 + } fn { 2 * } fn { dup * } tri
print nl print nl print nl // 25 then 10 then 6
}
bi_star and tri_star
Run one function value for each value: the first on the first, the second on the second.
tri_star does it for three.
fn main() {
3 4 fn { 1 + } fn { 2 * } bi_star
print nl print nl // 8 then 4
1 2 3 fn { 10 * } fn { 20 * } fn { 30 * } tri_star
print nl print nl print nl // 90 then 40 then 10
}
The first function value runs on what is under the others, so it can reach further down, and one
that leaves nothing is fine: l w c fn { show } fn { show } fn { show } tri_star prints three
values in order.
both
Run the same function value on two values.
fn main() {
3 4 fn { dup * } both
print nl print nl // 16 then 9
}
times
Run a function value n times. Each run starts on what the last one left, so it must leave the stack as it found it.
fn main() {
1 5 fn { 2 * } times print nl // 32
2 3 fn { dup * } times print nl // 256
}
Over arrays
each
Run a function value with each element on top. Like times, it must leave the stack as it
found it, so what it works on below the element carries from one element to the next:
fn main() {
0 [1 2 3 4] fn { + } each print nl // 10
[1 2 3] fn { print " " print } each nl // 1 2 3
}
map
A new array of what the function value leaves for each element. It takes one value and leaves one, and the result may be of another type:
fn main() {
[1 2 3] fn { dup * } map 2 nth print nl // 9
[1 2 3] fn { cast<str> } map 0 nth print nl // 1
}
filter
A new array of the elements for which the function value leaves a true flag:
fn main() {
[1 2 3 4 5 6] fn { 2 % 0 == } filter len print nl // 3
}
fold
Run the function value on an accumulator and each element in turn, starting from an initial value. What it leaves is the next accumulator:
fn main() {
[1 2 3 4] 0 fn { + } fold print nl // 10
[1 2 3 4] 1 fn { * } fold print nl // 24
}
find, index, scan, any and all
Search an array, stopping at the first element that decides the answer. The function value
takes one element and leaves a flag. find leaves the element it found and 1, or the zero of
the element type and 0; index leaves its position, or -1:
fn main() {
[1 5 12 3] fn { 10 > } any print nl // 1
[1 5 12 3] fn { 0 > } all print nl // 1
[1 5 12 3] fn { 4 > } find
print nl print nl // 1 then 5
["a" "bb" "ccc"] fn { len 5 > } find
print nl print nl // 0 then the empty string
[1 5 12 3] fn { 4 > } index print nl // 1
[1 5 12 3] fn { 40 > } index print nl // -1
}
These are what a for loop with a break was for: any and all stop as soon as the answer
is known, which fold cannot do.
scan is index from a position on, as Forth's SCAN is, for a scan that goes on from
where the last one stopped:
fn main() {
[3 8 5 12] 2 fn { 4 > } scan print nl // 2
[3 8 5 12] 9 fn { 4 > } scan print nl // -1
}
All of them also search a string, one character at a time. Each character is its codepoint, an
i64, and a position is a character index, the one strings::char_at takes:
use unicode
fn main() {
"key=value" fn { 61 == } index print nl // 3
"a=b=c" 2 fn { 61 == } scan print nl // 3
"héllo" fn { unicode::is_upper } any print nl // 0
"2026" fn { unicode::is_digit } all print nl // 1
}
Function values that are not written in place
A combinator runs any function value, not only one written right before it: one held in a local,
passed as a parameter, or a named function's &name. It is called rather than inlined, and is
checked by its type.
fn square(x:i64 -- r:i64) {
dup *
}
fn main() {
fn { 100 + } -> add100
1 2 add100 dip print " " print print nl // 2 101
[1 2 3] &square map 2 nth print nl // 9
}
The hof module
hof has the less common ones: when and unless, which run a function value on a condition,
and fold_right.
use hof
fn main() {
5 1 fn { 2 * } hof::when print nl // 10
5 0 fn { 2 * } hof::when print nl // 5
}
Practical examples
Data validation
fn validate_age(age:i64 -- valid:i64) {
// Must be at least 18 and at most 120
fn { 18 >= } fn { 120 <= } bi and
}
fn main() {
25 validate_age if { "Valid" } else { "Invalid" } print nl // Valid
-5 validate_age if { "Valid" } else { "Invalid" } print nl // Invalid
150 validate_age if { "Valid" } else { "Invalid" } print nl // Invalid
}
Several results from one value
fn stats(n:i64 -- doubled:i64 squared:i64 incremented:i64) {
fn { 2 * } fn { dup * } fn { 1 + } tri
}
fn main() {
5 stats
print nl print nl print nl // 6 then 25 then 10
}
A pipeline over an array
fn main() {
// The sum of the squares of the even numbers
[1 2 3 4 5 6]
fn { 2 % 0 == } filter
fn { dup * } map
0 fn { + } fold
print nl // 56
}
Comparison with Factor
Quadrate's combinators are Factor's, and so are their names, except where Factor's has a character a Quadrate name cannot:
| Factor | Quadrate |
|---|---|
[ 2 * ] |
fn { 2 * } |
5 [ 2 * ] [ 3 + ] bi |
5 fn { 2 * } fn { 3 + } bi |
3 4 [ sq ] bi@ |
3 4 fn { dup * } both |
3 4 [ 1 + ] [ 2 * ] bi* |
3 4 fn { 1 + } fn { 2 * } bi_star |
{ 1 2 3 } 0 [ + ] reduce |
[1 2 3] 0 fn { + } fold |
A function value used by a combinator cannot be fallible: the combinator would have nowhere to
send the failure. Handle it inside the function value, or call it and handle it where you are.
See Anonymous functions for closures and variable capture.
What's next?
Now let's learn about Generics to write type-flexible code.