实现基本的数组操作。
在函数式语言中,像length、map和reduce这样的数组操作非常常见。
请实现一系列基本的数组操作,不要使用现有的函数。
需要实现的操作的具体数量和名称会因你所在的编程语言轨道而异,以避免与现有名称冲突,但你将要实现的一般操作包括:
append(给定两个数组,把第二个数组中的所有元素添加到第一个数组的末尾);concatenate(给定一系列数组,把所有数组中的所有元素合并成一个扁平数组);filter(给定一个谓词和一个数组,返回所有满足 predicate(item) 为 True 的元素组成的数组);length(给定一个数组,返回其中元素的总数);map(给定一个函数和一个数组,返回对每个元素应用 function(item) 所得结果组成的数组);foldl(给定一个函数、一个数组和一个初始累加器,从左到右把每个元素折叠(归约)进累加器);foldr(给定一个函数、一个数组和一个初始累加器,从右到左把每个元素折叠(归约)进累加器);reverse(给定一个数组,返回一个包含所有原元素、但顺序相反的数组)。注意,传给折叠函数(foldl、foldr)的实参顺序很重要。
这个练习需要用到 Odin 的参数多态(更常见的叫法是泛型)。 如果你以前没见过这个特性,下面有一个简要说明,帮你快速上手。
参数多态是一种编程语言特性,它让程序员不必把代码中用到的类型写得那么具体(写得更通用,泛型这个名字就是这么来的),同时又能保持类型安全。 显然,这只对 Odin 这样的强类型语言才有意义。
我们先从一个例子开始。 假设你想把数组里的每个元素都自增一个固定的值,这个问题很简单。
incr_array_int :: proc(a: []int, by: int) -> []int {
new_array := make([]int, len(a))
for i := 0; i < len(a); i+= 1 {
new_array[i] = a[i] + by
}
return new_array
}
那如果现在浮点数也需要同样的功能呢?
incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {
new_array := make([]f64, len(a))
for i := 0; i < len(a); i+= 1 {
new_array[i] = a[i] + by
}
return new_array
}
再往后还有无符号整数、32 位浮点数,等等,又该怎么办?
用不了多久,你就会写出一大堆过程,它们做的事情完全一样,只是处理的数据类型不同。 一旦需要修改逻辑,你就得确保每个变体都改到,这会带来大量的维护工作。 另一个麻烦是,你得给每个过程起不同的名字,因为 Odin 不支持隐式的过程重载(你仍然可以使用显式重载,不过那是另一个练习的话题了)。
Odin 是一门讲求实用的语言,它用参数多态给出了解决方案。
只要编译器能在编译时推断出某个形参的类型,你就可以给它起一个泛型名字,比如T。
我们来重写上面的过程:
incr_array :: proc(a: []$T, by: T) -> []T {
new_array := make([]T, len(a))
for i := 0; i < len(a); i+= 1 {
new_array[i] = a[i] + by
}
return new_array
}
注意,我们把所有类型标注(int或f64)都换成了T,而且T第一次出现时前面加了一个美元符号($T)。
$T告诉 Odin 编译器,T这个名字是该类型的泛型名,编译时会被替换成实际的类型名。
而且,既然编译器现在已经知道泛型类型T,后面再出现同一个类型时,只需要标上选定的类型名(T)就可以了。
现在你可以写出这样的代码:
a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)
在第一条语句里,Odin 编译器会把第一个形参的类型([]int)与泛型形参的类型([]$T)对应起来,推断出T = int,然后编译出一个版本,把后面所有出现的T都替换成int(等价于上面那个特化版本incr_array_int())。
如果你在定义第一个形参时省略了美元符号,编译器就会在当前包和导入列表里查找一个叫T的类型,最后多半会报出一个编译错误Error: Undeclared name: T。
第二条语句的作用和第一条完全相同,只不过编译器把T认定成了f64。
按照惯例,泛型类型通常用单个字母来命名(常用的是T和E)。
现在,你应该已经对参数多态(也就是泛型类型)有了足够的了解,可以去做“数组操作”练习了。