(同事建议我用“自从用了递归,我头发又长回来了”作为标题,哈哈哈哈哈但我是老实人,明明从来没有掉过头发,我就不欺骗大家了~)
前言
首先,这是一篇用 haskell 和 javascript 两种语言来练习递归的基本实践(基准 + 递归条件)的分享文章。
一般解决一个问题,命令式语言期望我们给出求解步骤,而 haskell 则倾向于让你提供问题的描述,所以在 haskell 中,没有 while 和 for 循环,只有递归作为求解工具,所以递归之于 haskell 的重要性,可想而知。
在 javascript 里则比较灵活,这种灵活性给予了我们许多范式可以选择,即可使用 while 和 for 命令式的解决问题,也可以使用递归求解。
当然,声明两点:
- haskell 语法不是本文的重点,但会适当讲解一下。
- 本篇文章不代表具有任何实用性,但肯定有一定的学习参考价值。
递归的用处?
递归善于处理树、图等数据结构,比如抽象语法树、DOM 处理。同时可以优雅解决一些循环语句不能解决的问题等。
但是也会有使用不恰当,导致堆栈溢出、内存泄漏的情况,有可能也比较晦涩难懂,把代码转交给同事的时候,可能人家一脸懵逼。
但是!值得学习值得学习值得学习,重要的事情说三遍。
文章规约
本文每个函数都会贴两种语言的同一种实现, haskell 和 javascript。大家如果和我一样略懂 haskell,也可以品尝一下 haskell 代码。不过作为一名前端工程师,本文主要看 javascript 代码即可。
elem
判断元素是否存在元素列表中
haskell 实现
elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem'` xs
js 实现
function elem(a, list) {
if (list.length === 0) {
return false;
}
if (a === list[0]) {
return true;
}
return elem(a, list.slice(1));
}
首先我们先看第一段 haskell 的实现:
elem' :: (Eq a) => a -> [a] -> Bool
这一句实际上是 elem' 函数的类型签名(使用过 ramda.js 的同学应该也比较眼熟),意思可大概理解为,elem' 函数接收 任意类型 a 和 任意类型 a[], 最终返回一个布尔值类型。
(补充一下,haskell 的函数都是自动柯里化的,所以函数签名才会 a -> [a] -> Bool
。因为如果只传一个参数,则签名可以理解为:a -> ([a] -> Bool)
)
接下来以 elem' 两句表达式在 haskell 里被称为模式匹配,当然也可以理解为函数重载。对于 javascript 来说没有函数重载的语法机制,但是我们可以通过 arguments 的类型和数量人工模拟重载。
因此,以上两句,也就意味着:
第一句 elem' a [] = False
如果第二个数组参数匹配为空数组,则默认返回 False,很明显,空数组不可能包含任意元素~
第二句 elem' a (x:xs) | a == x = True | otherwise = a
elem'xs
,有 | 的地方被 Haskell 称为 Guards,暂时也可以简单理解为 if else 或者 switch case。而(x:xs)
这个很像 ES6 中的解构赋值,将传入匹配的数组列表参数切成了第一个元素 x 和剩下的所有元素 xs。因此在满足此前提下,如果 a==x 则 返回了 True,否则递归判断 a 是否在剩余的 xs 数组里。
注意以上,在 elem'函数里,递归的基准,也称边界条件,就是 a [] = False 或者 a == x = True。
而递归条件就是 x:xs 和 a elem'
xs(这里使用了中缀表达式)
以上,就是 haskell 里的 elem'递归实现原理。
那么如果以上关于 haskell 的部分没有理解,可以直接看上述的 javascript 编写的递归。
同样,递归的基准是两个 if 判断,分别返回不存在和存在的两种结果。
而递归条件则是 elem(a, list.slice(1))
。如果以上两个边界条件均为触发,则我们将元素列表缩小范围,递归再次判断。
正常解法:include, indexOf,lastIndexOf
sum
数字列表求和
haskell 实现
sum' :: Num a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs
js 实现
function sum(list) {
if (list.length === 0) {
return 0;
}
return list[0] + sum(list.slice(1));
}
同理如上,一样用递归的基准 + 递归条件来理解。
甚至我们得到了一个问题的定义:一个数字列表的和,必然等于第一个数和剩余列表数字和的和。
正常解法:list.reduce((a, b) => a + b)
maximum
求数字列表的最大值
haskell 实现
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
js 实现
function maximum(list) {
if (list.length === 0) {
throw new Error('maximum of empty list');
}
if (list.length === 1) {
return list[0];
}
return Math.max(list[0], maximum(list.slice(1)));
}
正常解法:当然直接用 Math.max(1,2,30,4,5)
是直接可以的。
repeat
重复一个值
haskell 实现
repeat' :: a -> [a]
repeat' x = x:repeat' x
js 实现
function repeat(x) {
return [x].concat(repeat(x));
}
这里比较有趣的是,haskell 本身是惰性计算,因此同样的实现,在 javascript 里会堆栈溢出,而在 haskell 里可以妥妥的,如下,take 5 告诉 haskell 只需要 5 个 repeat 的值就可以啦,于是人家就及时停止了。
Prelude> take 5 (repeat "*")
["*","*","*","*","*"]
replicate
固定次数重复一个值
haskell 实现
replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
| n <= 0 = []
| otherwise = x:replicate' (n-1) x
js 实现
function replicate(n, x) {
if (n <= 0) {
return [];
}
return [x].concat(replicate(n - 1, x));
}
还是一样,不多说。
不过一般人正常解法,还是 "?".repeat(n).split('')
reverse
数组倒序
haskell 实现
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
js 实现
function reverse(list) {
if (list.length === 0) {
return [];
}
return reverse(list.slice(1)).concat(list[0]);
}
倒序的递归还是挺有意思的,感觉可以归纳为一句话:一个数组的倒序结果,等于第一个元素推入剩余已经倒序过的元素数组的结果。
take
取数组元素的前 n 项
haskell 实现
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
js 实现
function take(n, list) {
if (n <= 0) {
return [];
}
if (list.length === 0) {
return [];
}
return [list[0]].concat(take(n - 1, list.slice(1)));
}
到这里,基本感觉是一种递归思想写一百个不同的函数了。
正常解法:当然是直接 slice 呀哈哈哈哈
zip
将两个数组的元素打成一对对 pair
(我们可以理解为,尽可能的组 cp 哈哈哈)
haskell 实现
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys
js 实现
function zip(list1, list2) {
if (list1.length === 0) {
return [];
}
if (list2.length === 0) {
return [];
}
return [[list1[0], list2[0]]].concat(zip(list1.slice(1), list2.slice(1)));
}
haskell 里的 zip,把两个数组打包成了一对对的元组(tuple)。
Prelude> zip ["a","b","c"] [1,2,3]
[("a",1),("b",2),("c",3)]
由于 javascript 里没有元组,只能用数组模拟。
> zip(["a","b","c"], [1,2,3])
[ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ] ]
虽然 zip 函数看上去稍微复杂了点,但是细细一看,其实也不过如此,对吧。
quicksort
快速排序
haskell 实现
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
biggerSorted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSorted
js 实现
function quicksort(list) {
if (list.length === 0) {
return [];
}
let x = list[0];
let rest = list.slice(1);
let smallerSorted = quicksort(rest.filter(i => i <= x));
let biggerSorted = quicksort(rest.filter(i => i > x));
return [smallerSorted, x, biggerSorted].flat();
}
这里的 quicksort'方法 [a | a <- xs, a <= x] 用到了一个 haskell 里很有趣的 List Comprehension,这种写法有点像数学里的集合。
在 javascript 里,可以通过写两个 filter 分别替代 [a | a <- xs, a <= x] 和 [a | a <- xs, a > x]。
当然,算法的定义:排过序的数组,就是令所有小于等于头部的元素在先(它们已经排序完成), 后跟大于头部的元素(它们同样已经排序完成)。 这里与众不同的是,因为定义中有两次排序,所以就递归两次!~
这个函数实现的确证明了递归之美,对吧~
写在最后
本文兴趣所致~ 目测是一篇枯燥的文章,嗯。