| ↑ Up |
A function is called a higher order function if it
takes a function as its argument or returns a function as its
result. The data types List and Iterable
already provide a number of such functions. The most well known
are map, filter and reduce.
By a.map(f) we return a copy of the list a
with f applied to every element.
> list(1..4).map(|x| 2*x) [2, 4, 6, 8]
The same function is provided by Iterable, with the
difference that it returns an iterator.
> (1..).map(|x| 2*x).list(4) [2, 4, 6, 8] > iter(list(1..4)).map(|x| 2*x).list() [2, 4, 6, 8]
Besides A.map(f) it is possible to write
f[A]. Here A is seen as a set, and
f[A] the image of the set A under
f. But it works not only on sets, but on any iterable
object. For example, to convert a string s
into the list of its character values, use ord[s].
> ord["abcd"] [97, 98, 99, 100]
If f is a binary operator, f[a,b]
allows to operate a and b
pointwise.
> a = list(1..4) > add = |x,y| x+y > add[a,a] [2, 6, 4, 8] > zip(a,a).map(|[x,y]| x+y).list() [2, 6, 4, 8]
By a.filter(p) we filter every element from
a that fulfills the predicate p.
For example, let us filter all divisors of n.
> divisors = |n| list(1..n).filter(|k| n%k==0) > divisors(12) [1, 2, 3, 4, 6, 12]
Let us find some Pythagorean triples.
> (list(1..10)^3).filter(|[x,y,z]| x^2+y^2==z^2) [[3, 4, 5], [4, 3, 5], [6, 8, 10], [8, 6, 10]]
Again, Iterable has a version that produces
an iterator.
> list(1..).filter(|x| x%2==0).list(4) [2, 4, 6, 8]
By a.reduce(f) we insert f as a
binary operator between the elements of a.
> 1+2+3+4+5+6+7+8+9+10 55 > list(1..10).reduce(|x,y| x+y) 55
Note that reduce works not just on lists,
but on any iterable:
> (1..10).reduce(|x,y| x+y) 55
A start element may be specified.
> 1000+1+2+3+4 1010 > (1..4).reduce(1000,|x,y| x+y) 1010
By a.count(p) we count how often the predicate
p is fulfilled. Let us count all divisors of a number
n.
> d = |n| (1..n).count(|k| n%k==0)
A number is prime if it has two divisors.
> isprime = |n| d(n)==2 > (1..).filter(isprime).list(10) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
The operation zip(a,b) joins
a and b elementwise.
> zip([1,2,3,4],["a","b","c","d"]).list() [[1, "a"], [2, "b"], [3, "c"], [4, "d"]]
For convenience:
> zip(1..,"abcd").list() [[1, "a"], [2, "b"], [3, "c"], [4, "d"]] > "abcd".enum(1).list() [[1, "a"], [2, "b"], [3, "c"], [4, "d"]]
In Moss, if we want to list the square numbers x2 for x from 1 to 10, we have the following choices:
a = list(1..10).map(|x| x^2) a = list(x^2 for x in 1..10) a = (|x| x^2)[1..10] a = (1..).map(|x| x^2).list(10) a = (x^2 for x in 1..).list(10) a = list((1..10).map(|x| x^2))
You might ask why there are so many ways to achieve this. Let me explain how the following three forms have a slightly different purpose.
a.map(f) | Maps a function f to each element of a.
This is abstract and will work even for matrix data types.
|
f(x) for x in a | Creates an iterator which can be turned into a list, set or map. This allows multiple for- and if-clauses. Thus it can be used for constructions involving subsets of cartesian products. |
f[a,b,c,...] | Performs an implicit zip-operation. Reflects the notation
f[X] for the image of the set X
under f.
|
For example, a cartesian product is created this way:
prod = |a,b| list([x,y] for x in a for y in b) prod = |a,b| a.map(|x| b.map(|y| [x,y])).chain() prod = |a,b| (|x| (|y| [x,y])[a])[b].chain() prod = |a,b| a*b
The addition of two lists as if they would be vectors is achieved this way:
add = |v,w| list(zip(v,w).map(|[x,y]| x+y)) add = |v,w| list(x+y for x,y in zip(v,w)) add = |v,w| (|x,y| x+y)[v,w]
A list comprehension is basically filter,
map or chaining both:
a = list(1..10).filter(|x| x%2==0).map(|x| x^2) a = list(x^2 for x in 1..10 if x%2==0)
Abstractly, we have:
a = list(r).filter(p).map(f) a = list(f(x) for x in r if p(x))
In these expressions, r is some range or iterable,
p is a predicate and f is a function/mapping.
A predicate is a function that returns values of type Bool.
The predicate may be omitted:
a = list(r).map(f) a = list(f(x) for x in r)
The mapping may be omitted:
a = list(r).filter(p) a = list(x for x in r if p(x))
In mathematics sets are stated by set-builder notation:
{f(x) | x ∈ A ∧ p(x)}
For finite sets this can be stated in Moss:
set(f(x) for x in A if p(x))
For infinite sets you might at least want a function that depends on
a number n, examining finite subsets:
B = |n| set((f(x) for x in A() if p(x)).take(n))
A map comprehension allows to inverse a map:
inv = |m| map([value,key] for key,value in m.items())
An imperative formulation of inv is slightly longer:
function inv(m)
m2 = {}
for key in m
m2[m[key]] = key
end
return m2
end
Another example. The numbers from 0 to 25 are shuffled and a random permutation map of the latin alphabet is obtained from that:
m = map([chr(x+ord('a')),chr(y+ord('a'))]
for x,y in zip(0..25,list(0..25).shuffle()))
For convenience:
m = map(zip("a".."z",list("a".."z").shuffle()))
We want to find solutions of the Diophantine equation
x3 + y3 + z3 = w3.
A generator comprehension prevents the program from memory exhaustion and allows to print found solutions instantly.
g = |n| ([x,y,z,w] for x in 1..n for y in 1..n for z in 1..n for w in 1..n if x^3+y^3+z^3 == w^3) g(200).each(print)