如何在 Javascript 中用递归替换 for 循环？
How do I replace for loops with recursion in Javascript?
我有 2 个 for 循环，可以很好地创建包含行和列的网格，但我想使用递归改进解决方案，因为它更简洁，更值得推荐（在函数式编程中）。
所需的输出是 css 网格中使用的单个对数组
const createGrid = (rows,columns) => {
let grid=[]
for (let y = 3; y <= rows; y += 2){
let row = []
for (let x = 3; x <= columns; x += 2){
let col = [y, x]
row = [...row,col]
}
grid =[...grid, ...row]
}
return grid
}
是否还有关于如何尽可能将 for 循环转换为递归解决方案的指南？
原始递归
这是使用递归制作网格的一种可能方法 -
const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols), makeRow(f, rows, cols) ]
const makeRow = (f, row = 0, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, row, cols - 1), f(row, cols) ]
const g =
makeGrid((x, y) => ({ xPos: x, yPos: y }), 2, 3)
console.log(JSON.stringify(g))
// [ [ {"xPos":1,"yPos":1}
// , {"xPos":1,"yPos":2}
// , {"xPos":1,"yPos":3}
// ]
// , [ {"xPos":2,"yPos":1}
// , {"xPos":2,"yPos":2}
// , {"xPos":2,"yPos":3}
// ]
// ]
函数参数 f 允许我们以多种方式构建网格单元
const g =
makeGrid((x, y) => [ x - 1, y - 1 ], 3, 2)
console.log(JSON.stringify(g))
// [ [ [ 0, 0 ]
// , [ 0, 1 ]
// ]
// , [ [ 1, 0 ]
// , [ 1, 1 ]
// ]
// , [ [ 2, 0 ]
// , [ 2, 1 ]
// ]
// ]
更聪明地工作，而不是更努力地工作
根据 Bergi 的评论，您可以使用 curried 单元格构造函数减少一些额外的参数传递 -
const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols), makeRow(f(rows), cols) ]
const makeRow = (f, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, cols - 1), f(cols) ]
const g =
makeGrid
( x => y => [ x, y ] // "curried" constructor
, 2
, 3
)
console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
// , [ 1, 2 ]
// , [ 1, 3 ]
// ]
// , [ [ 2, 1 ]
// , [ 2, 2 ]
// , [ 2, 3 ]
// ]
// ]
吃蛋糕也吃
或者，我们可以合并该建议并仍然使用部分应用程序在调用站点接受二元函数 -
const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols)
, makeRow(_ => f(rows, _), cols) // <-- partially apply f
]
const makeRow = (f, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, cols - 1), f(cols) ]
const g =
makeGrid
( (x,y) => [ x, y ] // ordinary constructor
, 2
, 3
)
console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
// , [ 1, 2 ]
// , [ 1, 3 ]
// ]
// , [ [ 2, 1 ]
// , [ 2, 2 ]
// , [ 2, 3 ]
// ]
// ]
第N维
以上我们仅限于二维网格。如果我们想要 3 维甚至更多怎么办？
const identity = x =>
x
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ] // <-- recursion
const map = ([ x, ...more ], f = identity) =>
x === undefined
? []
: [ f(x), ...map(more, f) ] // <-- recursion
const makeGrid = (r = [], d = 0, ...more) =>
d === 0
? r
: map(range(0, d), x => makeGrid(r(x), ...more)) // <-- recursion
const g =
makeGrid
( x => y => z => [ x, y, z ] // <-- constructor
, 2 // <-- dimension 1
, 2 // <-- dimension 2
, 3 // <-- dimension 3
, // ... <-- dimension N
)
console.log(JSON.stringify(g))
输出
[ [ [ [0,0,0]
, [0,0,1]
, [0,0,2]
]
, [ [0,1,0]
, [0,1,1]
, [0,1,2]
]
]
, [ [ [1,0,0]
, [1,0,1]
, [1,0,2]
]
, [ [1,1,0]
, [1,1,1]
, [1,1,2]
]
]
]
任意维度；持平结果
根据您的评论，您需要一个 平坦 对数组。您可以通过简单地将 map 替换为 flatMap 来实现，如下所示 -
const identity = x =>
x
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ]
const flatMap = ([ x, ...more ], f = identity) =>
x === undefined
? []
: [ ...f(x), ...flatMap(more, f) ] // <-- flat!
const makeGrid = (r = [], d = 0, ...more) =>
d === 0
? r
: flatMap(range(0, d), x => makeGrid(r(x), ...more))
const g =
makeGrid
( x => y => [{ x, y }] // <-- constructor
, 2 // <-- dimension 1
, 2 // <-- dimension 2
, // ... <-- dimension N
)
console.log(JSON.stringify(g))
// [ { x: 0, y: 0 }
// , { x: 0, y: 1 }
// , { x: 1, y: 0 }
// , { x: 1, y: 1 }
// ]
函数式构造函数再次展示了它的多功能性-
const g =
makeGrid
( x => y =>
[[ 3 + x * 2, 3 + y * 2 ]] // whatever you want
, 3
, 3
)
console.log(JSON.stringify(g))
// [[3,3],[3,5],[3,7],[5,3],[5,5],[5,7],[7,3],[7,5],[7,7]]
了解更多
正如其他人所展示的那样，使用 flatMap 的 makeGrid 的这个特定版本有效地计算了 cartesian product。当你已经完全了解 flatMap 时，你已经了解了 List Monad！
再来点蛋糕！
如果您还想了解更多，我想为您介绍我在计算研究中最喜欢的主题之一：定界延续。开始使用第一个 class continuations 涉及对它们的某些使用方式形成直觉 -
reset
( call
( (x, y) => [[ x, y ]]
, amb([ 'J', 'Q', 'K', 'A' ])
, amb([ '♡', '♢', '♤', '♧' ])
)
)
// [ [ J, ♡ ], [ J, ♢ ], [ J, ♤ ], [ J, ♧ ]
// , [ Q, ♡ ], [ Q, ♢ ], [ Q, ♤ ], [ Q, ♧ ]
// , [ K, ♡ ], [ K, ♢ ], [ K, ♤ ], [ K, ♧ ]
// , [ A, ♡ ], [ A, ♢ ], [ A, ♤ ], [ A, ♧ ]
// ]
就像 List Monad 一样，上面的 amb 封装了这种 模糊 （非确定性）计算的概念。我们可以很容易地使用定界延续来写我们的二维 simpleGrid -
const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
reset
( call
( f
, amb(range(0, dim1))
, amb(range(0, dim2))
)
)
simpleGrid((x, y) => [[x, y]], 3, 3)
// [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
由于 amb，创建 N 维网格变得轻而易举。实施几乎消失了 -
const always = x =>
_ => x
const multiGrid = (f = always([]), ...dims) =>
reset
( apply
( f
, dims.map(_ => amb(range(0, _)))
)
)
multiGrid
( (x, y, z) => [[ x, y, z ]] // <-- not curried this time, btw
, 3
, 3
, 3
)
// [ [0,0,0], [0,0,1], [0,0,2]
// , [0,1,0], [0,1,1], [0,1,2]
// , [0,2,0], [0,2,1], [0,2,2]
// , [1,0,0], [1,0,1], [1,0,2]
// , [1,1,0], [1,1,1], [1,1,2]
// , [1,2,0], [1,2,1], [1,2,2]
// , [2,0,0], [2,0,1], [2,0,2]
// , [2,1,0], [2,1,1], [2,1,2]
// , [2,2,0], [2,2,1], [2,2,2]
// ]
或者我们可以在单元构造函数中使用 line 创建所需的增量和偏移 -
const line = (m = 1, b = 0) =>
x => m * x + b // <-- linear equation, y = mx + b
multiGrid
( (...all) => [ all.map(line(2, 3)) ] // <-- slope: 2, y-offset: 3
, 3
, 3
, 3
)
// [ [3,3,3], [3,3,5], [3,3,7]
// , [3,5,3], [3,5,5], [3,5,7]
// , [3,7,3], [3,7,5], [3,7,7]
// , [5,3,3], [5,3,5], [5,3,7]
// , [5,5,3], [5,5,5], [5,5,7]
// , [5,7,3], [5,7,5], [5,7,7]
// , [7,3,3], [7,3,5], [7,3,7]
// , [7,5,3], [7,5,5], [7,5,7]
// , [7,7,3], [7,7,5], [7,7,7]
// ]
那么reset、call、apply和amb是从哪里来的呢？ JavaScript 不支持第一个 class 延续，但没有什么能阻止我们 -
const call = (f, ...values) =>
({ type: call, f, values }) //<-- ordinary object
const apply = (f, values) =>
({ type: call, f, values }) //<-- ordinary object
const shift = (f = identity) =>
({ type: shift, f }) //<-- ordinary object
const amb = (xs = []) =>
shift(k => xs.flatMap(x => k(x))) //<-- returns ordinary object
const reset = (expr = {}) =>
loop(() => expr) //<-- ???
const loop = f =>
// ... //<-- follow the link!
考虑到您问题的背景，很明显这是一个纯粹的学术练习。斯科特的回答为我们所做的一些权衡提供了合理的理由。希望本节向您展示更强大的计算功能可以轻松解决最初看起来很复杂的问题。
首先 class 继续为您的程序解锁强大的控制流。你有没有想过 JavaScript 是如何实现 function* 和 yield 的？如果 JavaScript 没有内置这些功能怎么办？ 看看我们如何只使用普通函数来实现这些（以及更多）。
continuations 代码演示
在您自己的浏览器中查看它的运行情况！展开下面的代码片段以使用分隔的延续生成网格...在 JavaScript 中！ -
// identity : 'a -> 'a
const identity = x =>
x
// always : 'a -> 'b -> 'a
const always = x =>
_ => x
// log : (string, 'a) -> unit
const log = (label, x) =>
console.log(label, JSON.stringify(x))
// line : (int, int) -> int -> int
const line = (m, b) =>
x => m * x + b
// range : (int, int) -> int array
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ]
// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
({ type: call, f, values })
// apply : (* -> 'a expr, * array) -> 'a expr
const apply = (f, values) =>
({ type: call, f, values })
// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
({ type: shift, f })
// reset : 'a expr -> 'a
const reset = (expr = {}) =>
loop(() => expr)
// amb : ('a array) -> ('a array) expr
const amb = (xs = []) =>
shift(k => xs .flatMap (x => k (x)))
// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
const aux1 = (expr = {}, k = identity) =>
{ switch (expr.type)
{ case call:
return call(aux, expr.f, expr.values, k)
case shift:
return call
( aux1
, expr.f(x => trampoline(aux1(x, k)))
, identity
)
default:
return call(k, expr)
}
}
// aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
const aux = (f, exprs = [], k) =>
{ switch (exprs.length)
{ case 0:
return call(aux1, f(), k) // nullary continuation
case 1:
return call
( aux1
, exprs[0]
, x => call(aux1, f(x), k) // unary
)
case 2:
return call
( aux1
, exprs[0]
, x =>
call
( aux1
, exprs[1]
, y => call(aux1, f(x, y), k) // binary
)
)
case 3: // ternary ...
case 4: // quaternary ...
default: // variadic
return call
( exprs.reduce
( (mr, e) =>
k => call(mr, r => call(aux1, e, x => call(k, [ ...r, x ])))
, k => call(k, [])
)
, values => call(aux1, f(...values), k)
)
}
}
return trampoline(aux1(f()))
}
// trampoline : * -> *
const trampoline = r =>
{ while (r && r.type === call)
r = r.f(...r.values)
return r
}
// simpleGrid : ((...int -> 'a), int, int) -> 'a array
const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
reset
( call
( f
, amb(range(0, dim1))
, amb(range(0, dim2))
)
)
// multiGrid : (...int -> 'a, ...int) -> 'a array
const multiGrid = (f = always([]), ...dims) =>
reset
( apply
( f
, dims.map(_ => amb(range(0, _)))
)
)
// : unit
log
( "simple grid:"
, simpleGrid((x, y) => [[x, y]], 3, 3)
)
// : unit
log
( "multiGrid:"
, multiGrid
( (...all) => [ all.map(line(2, 3)) ]
, 3
, 3
, 3
)
)
函数式编程更多的是关于高阶函数而不是直接递归。我相信以下等同于您的示例，使用 underscore.js 中的 _.range 以及标准库中的 map 和 flatMap。
const rowRange = _.range(3, rows + 1, 2);
const colRange = _.range(3, columns + 1, 2);
return rowRange.flatMap(row => colRange.map(col => [col, row]));
起初，在阅读您的代码时，我认为您生成了一种网格样式，因此 makeGrid (7, 9) 会产生如下结果：
[
[[3, 3], [3, 5], [3, 7], [3, 9]],
[[5, 3], [5, 5], [5, 7], [5, 9]],
[[7, 3], [7, 5], [7, 7], [7, 9]]
]
相反，它 returns 一对数组：
[[3, 3], [3, 5], [3, 7], [3, 9], [5, 3], [5, 5], [5, 7], [5, 9], [7, 3], [7, 5], [7, 7], [7, 9]]
我很确定我不是唯一一个。 Bergi 在评论中建议修复以将其更改为前者。 （这就是将 grid =[...grid, ...row] 更改为 grid =[...grid, row] 的结果。）来自 Thankyou 的精彩回答基于相同的假设。
这是个问题。
当 reader 无法快速理解您的代码的作用时，维护起来就会变得更加困难......即使是几周后的您自己也是如此。
您可能会听到用递归代替循环的建议的原因与此有关。循环都是关于明确的命令式指令来获得你想要的东西，这取决于变异变量，然后你必须跟踪这些变量，并且很容易出现差一错误。递归通常更具声明性，它表示您正在寻找的结果只是将这些更简单的结果与我们当前的数据相结合，并指出如何通过基本案例或递归来获得更简单的结果打电话。
不过，可读性和可理解性的优势才是关键，而不是解决方案是递归的。
不要误会我的意思，递归是我最喜欢的编程技术之一。 Thankyou 的回答漂亮而优雅。但这并不是解决显式 for 循环出现的问题的唯一技术。通常，当我试图将初级程序员提升到中级以上时，我做的第一件事就是用更有意义的结构替换 for-loops。大多数循环都试图做几件事之一。他们试图将列表中的每个元素转换为新的元素 (map)，试图选择元素的一些重要子集 (filter)，试图找到第一个重要元素 (find)，或尝试将所有元素组合成一个值 (reduce)。通过使用这些，代码变得更加明确。
同样重要的是，如 Thankyou 的回答所示，将代码的可重用部分分开，以便您的主要功能可以专注于重要部分。下面的版本提取了一个函数 rangeBy，它在我常用的 range 函数的基础上添加了一个 step 参数。 range 创建一个整数范围，例如，range (3, 12) 产生 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] rangeBy 添加初始 step 参数，因此 range (2) (3, 12) 产生[3, 5, 7, 9, 11].
我们将 rangeBy 函数与 map 及其堂兄 flatMap 一起使用，以制作更明确的循环函数版本：
const rangeBy = (step) => (lo, hi) =>
[... Array (Math .ceil ((hi - lo + 1) / step))]
.map ((_, i) => i * step + lo)
const createGrid = (rows, columns) =>
rangeBy (2) (3, rows) .flatMap (y =>
rangeBy (2) (3, columns) .map (x =>
[y, x]
)
)
console .log (createGrid (7, 9))
知道 rangeBy 的作用，我们可以在心里将其理解为
const createGrid = (rows, columns) =>
[3, 5, 7, ..., rows] .flatMap (y =>
[3, 5, 7, ..., columns] .map (x =>
[y, x]
)
)
请注意，如果您想要我期望的行为，只需将 createGrid 中的 flatMap 替换为 map 即可实现。此外，如果您这样做，通过将 [y, x] 替换为 f (x, y) 并将 f 作为参数传递，添加 Thankyou 提供的更通用的行为是微不足道的。在此版本中保留硬编码的是将 rows 和 columns 转换为以 3 开头的奇数数组。我们可以将实际数组作为我们函数的参数，并应用 rangeBy 外部。但那时，我们可能正在寻找一个理想名称为 cartesianProduct.
的不同函数
所以递归是一个了不起的有用工具。但它是一种工具，而不是目标。然而，简单、可读的代码是一个重要目标。
更新
我本来想提这个的，只是忘记了。以下版本演示了 rangeBy 中的柯里化远非根本。我们可以轻松地使用单个调用：
const rangeBy = (step, lo, hi) =>
[... Array (Math .ceil ((hi - lo + 1) / step))]
.map ((_, i) => i * step + lo)
const createGrid = (rows, columns) =>
rangeBy (2, 3, rows) .flatMap (y =>
rangeBy (2, 3, columns) .map (x =>
[y, x]
)
)
console .log (createGrid (7, 9))
柯里化 rangeBy 的主要理由是，当它这样写时：
const rangeBy = (step) => (lo, hi) =>
[... Array (Math .ceil ((hi - lo + 1) / step))]
.map ((_, i) => i * step + lo)
我们可以通过简单地将 1 应用到上面来编写更常见的 range。也就是说，
const range = rangeBy (1)
range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
这太有用了，已经成为我写函数的惯用风格。但这不是简化问题的重要部分。
我有 2 个 for 循环，可以很好地创建包含行和列的网格，但我想使用递归改进解决方案，因为它更简洁，更值得推荐（在函数式编程中）。
所需的输出是 css 网格中使用的单个对数组
const createGrid = (rows,columns) => {
let grid=[]
for (let y = 3; y <= rows; y += 2){
let row = []
for (let x = 3; x <= columns; x += 2){
let col = [y, x]
row = [...row,col]
}
grid =[...grid, ...row]
}
return grid
}
是否还有关于如何尽可能将 for 循环转换为递归解决方案的指南？
原始递归
这是使用递归制作网格的一种可能方法 -
const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols), makeRow(f, rows, cols) ]
const makeRow = (f, row = 0, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, row, cols - 1), f(row, cols) ]
const g =
makeGrid((x, y) => ({ xPos: x, yPos: y }), 2, 3)
console.log(JSON.stringify(g))
// [ [ {"xPos":1,"yPos":1}
// , {"xPos":1,"yPos":2}
// , {"xPos":1,"yPos":3}
// ]
// , [ {"xPos":2,"yPos":1}
// , {"xPos":2,"yPos":2}
// , {"xPos":2,"yPos":3}
// ]
// ]
函数参数 f 允许我们以多种方式构建网格单元
const g =
makeGrid((x, y) => [ x - 1, y - 1 ], 3, 2)
console.log(JSON.stringify(g))
// [ [ [ 0, 0 ]
// , [ 0, 1 ]
// ]
// , [ [ 1, 0 ]
// , [ 1, 1 ]
// ]
// , [ [ 2, 0 ]
// , [ 2, 1 ]
// ]
// ]
更聪明地工作，而不是更努力地工作
根据 Bergi 的评论，您可以使用 curried 单元格构造函数减少一些额外的参数传递 -
const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols), makeRow(f(rows), cols) ]
const makeRow = (f, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, cols - 1), f(cols) ]
const g =
makeGrid
( x => y => [ x, y ] // "curried" constructor
, 2
, 3
)
console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
// , [ 1, 2 ]
// , [ 1, 3 ]
// ]
// , [ [ 2, 1 ]
// , [ 2, 2 ]
// , [ 2, 3 ]
// ]
// ]
吃蛋糕也吃
或者，我们可以合并该建议并仍然使用部分应用程序在调用站点接受二元函数 -
const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols)
, makeRow(_ => f(rows, _), cols) // <-- partially apply f
]
const makeRow = (f, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, cols - 1), f(cols) ]
const g =
makeGrid
( (x,y) => [ x, y ] // ordinary constructor
, 2
, 3
)
console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
// , [ 1, 2 ]
// , [ 1, 3 ]
// ]
// , [ [ 2, 1 ]
// , [ 2, 2 ]
// , [ 2, 3 ]
// ]
// ]
第N维
以上我们仅限于二维网格。如果我们想要 3 维甚至更多怎么办？
const identity = x =>
x
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ] // <-- recursion
const map = ([ x, ...more ], f = identity) =>
x === undefined
? []
: [ f(x), ...map(more, f) ] // <-- recursion
const makeGrid = (r = [], d = 0, ...more) =>
d === 0
? r
: map(range(0, d), x => makeGrid(r(x), ...more)) // <-- recursion
const g =
makeGrid
( x => y => z => [ x, y, z ] // <-- constructor
, 2 // <-- dimension 1
, 2 // <-- dimension 2
, 3 // <-- dimension 3
, // ... <-- dimension N
)
console.log(JSON.stringify(g))
输出
[ [ [ [0,0,0]
, [0,0,1]
, [0,0,2]
]
, [ [0,1,0]
, [0,1,1]
, [0,1,2]
]
]
, [ [ [1,0,0]
, [1,0,1]
, [1,0,2]
]
, [ [1,1,0]
, [1,1,1]
, [1,1,2]
]
]
]
任意维度；持平结果
根据您的评论，您需要一个 平坦 对数组。您可以通过简单地将 map 替换为 flatMap 来实现，如下所示 -
const identity = x =>
x
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ]
const flatMap = ([ x, ...more ], f = identity) =>
x === undefined
? []
: [ ...f(x), ...flatMap(more, f) ] // <-- flat!
const makeGrid = (r = [], d = 0, ...more) =>
d === 0
? r
: flatMap(range(0, d), x => makeGrid(r(x), ...more))
const g =
makeGrid
( x => y => [{ x, y }] // <-- constructor
, 2 // <-- dimension 1
, 2 // <-- dimension 2
, // ... <-- dimension N
)
console.log(JSON.stringify(g))
// [ { x: 0, y: 0 }
// , { x: 0, y: 1 }
// , { x: 1, y: 0 }
// , { x: 1, y: 1 }
// ]
函数式构造函数再次展示了它的多功能性-
const g =
makeGrid
( x => y =>
[[ 3 + x * 2, 3 + y * 2 ]] // whatever you want
, 3
, 3
)
console.log(JSON.stringify(g))
// [[3,3],[3,5],[3,7],[5,3],[5,5],[5,7],[7,3],[7,5],[7,7]]
了解更多
正如其他人所展示的那样，使用 flatMap 的 makeGrid 的这个特定版本有效地计算了 cartesian product。当你已经完全了解 flatMap 时，你已经了解了 List Monad！
再来点蛋糕！
如果您还想了解更多，我想为您介绍我在计算研究中最喜欢的主题之一：定界延续。开始使用第一个 class continuations 涉及对它们的某些使用方式形成直觉 -
reset
( call
( (x, y) => [[ x, y ]]
, amb([ 'J', 'Q', 'K', 'A' ])
, amb([ '♡', '♢', '♤', '♧' ])
)
)
// [ [ J, ♡ ], [ J, ♢ ], [ J, ♤ ], [ J, ♧ ]
// , [ Q, ♡ ], [ Q, ♢ ], [ Q, ♤ ], [ Q, ♧ ]
// , [ K, ♡ ], [ K, ♢ ], [ K, ♤ ], [ K, ♧ ]
// , [ A, ♡ ], [ A, ♢ ], [ A, ♤ ], [ A, ♧ ]
// ]
就像 List Monad 一样，上面的 amb 封装了这种 模糊 （非确定性）计算的概念。我们可以很容易地使用定界延续来写我们的二维 simpleGrid -
const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
reset
( call
( f
, amb(range(0, dim1))
, amb(range(0, dim2))
)
)
simpleGrid((x, y) => [[x, y]], 3, 3)
// [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
由于 amb，创建 N 维网格变得轻而易举。实施几乎消失了 -
const always = x =>
_ => x
const multiGrid = (f = always([]), ...dims) =>
reset
( apply
( f
, dims.map(_ => amb(range(0, _)))
)
)
multiGrid
( (x, y, z) => [[ x, y, z ]] // <-- not curried this time, btw
, 3
, 3
, 3
)
// [ [0,0,0], [0,0,1], [0,0,2]
// , [0,1,0], [0,1,1], [0,1,2]
// , [0,2,0], [0,2,1], [0,2,2]
// , [1,0,0], [1,0,1], [1,0,2]
// , [1,1,0], [1,1,1], [1,1,2]
// , [1,2,0], [1,2,1], [1,2,2]
// , [2,0,0], [2,0,1], [2,0,2]
// , [2,1,0], [2,1,1], [2,1,2]
// , [2,2,0], [2,2,1], [2,2,2]
// ]
或者我们可以在单元构造函数中使用 line 创建所需的增量和偏移 -
const line = (m = 1, b = 0) =>
x => m * x + b // <-- linear equation, y = mx + b
multiGrid
( (...all) => [ all.map(line(2, 3)) ] // <-- slope: 2, y-offset: 3
, 3
, 3
, 3
)
// [ [3,3,3], [3,3,5], [3,3,7]
// , [3,5,3], [3,5,5], [3,5,7]
// , [3,7,3], [3,7,5], [3,7,7]
// , [5,3,3], [5,3,5], [5,3,7]
// , [5,5,3], [5,5,5], [5,5,7]
// , [5,7,3], [5,7,5], [5,7,7]
// , [7,3,3], [7,3,5], [7,3,7]
// , [7,5,3], [7,5,5], [7,5,7]
// , [7,7,3], [7,7,5], [7,7,7]
// ]
那么reset、call、apply和amb是从哪里来的呢？ JavaScript 不支持第一个 class 延续，但没有什么能阻止我们
const call = (f, ...values) =>
({ type: call, f, values }) //<-- ordinary object
const apply = (f, values) =>
({ type: call, f, values }) //<-- ordinary object
const shift = (f = identity) =>
({ type: shift, f }) //<-- ordinary object
const amb = (xs = []) =>
shift(k => xs.flatMap(x => k(x))) //<-- returns ordinary object
const reset = (expr = {}) =>
loop(() => expr) //<-- ???
const loop = f =>
// ... //<-- follow the link!
考虑到您问题的背景，很明显这是一个纯粹的学术练习。斯科特的回答为我们所做的一些权衡提供了合理的理由。希望本节向您展示更强大的计算功能可以轻松解决最初看起来很复杂的问题。
首先 class 继续为您的程序解锁强大的控制流。你有没有想过 JavaScript 是如何实现 function* 和 yield 的？如果 JavaScript 没有内置这些功能怎么办？
continuations 代码演示
在您自己的浏览器中查看它的运行情况！展开下面的代码片段以使用分隔的延续生成网格...在 JavaScript 中！ -
// identity : 'a -> 'a
const identity = x =>
x
// always : 'a -> 'b -> 'a
const always = x =>
_ => x
// log : (string, 'a) -> unit
const log = (label, x) =>
console.log(label, JSON.stringify(x))
// line : (int, int) -> int -> int
const line = (m, b) =>
x => m * x + b
// range : (int, int) -> int array
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ]
// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
({ type: call, f, values })
// apply : (* -> 'a expr, * array) -> 'a expr
const apply = (f, values) =>
({ type: call, f, values })
// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
({ type: shift, f })
// reset : 'a expr -> 'a
const reset = (expr = {}) =>
loop(() => expr)
// amb : ('a array) -> ('a array) expr
const amb = (xs = []) =>
shift(k => xs .flatMap (x => k (x)))
// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
const aux1 = (expr = {}, k = identity) =>
{ switch (expr.type)
{ case call:
return call(aux, expr.f, expr.values, k)
case shift:
return call
( aux1
, expr.f(x => trampoline(aux1(x, k)))
, identity
)
default:
return call(k, expr)
}
}
// aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
const aux = (f, exprs = [], k) =>
{ switch (exprs.length)
{ case 0:
return call(aux1, f(), k) // nullary continuation
case 1:
return call
( aux1
, exprs[0]
, x => call(aux1, f(x), k) // unary
)
case 2:
return call
( aux1
, exprs[0]
, x =>
call
( aux1
, exprs[1]
, y => call(aux1, f(x, y), k) // binary
)
)
case 3: // ternary ...
case 4: // quaternary ...
default: // variadic
return call
( exprs.reduce
( (mr, e) =>
k => call(mr, r => call(aux1, e, x => call(k, [ ...r, x ])))
, k => call(k, [])
)
, values => call(aux1, f(...values), k)
)
}
}
return trampoline(aux1(f()))
}
// trampoline : * -> *
const trampoline = r =>
{ while (r && r.type === call)
r = r.f(...r.values)
return r
}
// simpleGrid : ((...int -> 'a), int, int) -> 'a array
const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
reset
( call
( f
, amb(range(0, dim1))
, amb(range(0, dim2))
)
)
// multiGrid : (...int -> 'a, ...int) -> 'a array
const multiGrid = (f = always([]), ...dims) =>
reset
( apply
( f
, dims.map(_ => amb(range(0, _)))
)
)
// : unit
log
( "simple grid:"
, simpleGrid((x, y) => [[x, y]], 3, 3)
)
// : unit
log
( "multiGrid:"
, multiGrid
( (...all) => [ all.map(line(2, 3)) ]
, 3
, 3
, 3
)
)
函数式编程更多的是关于高阶函数而不是直接递归。我相信以下等同于您的示例，使用 underscore.js 中的 _.range 以及标准库中的 map 和 flatMap。
const rowRange = _.range(3, rows + 1, 2);
const colRange = _.range(3, columns + 1, 2);
return rowRange.flatMap(row => colRange.map(col => [col, row]));
起初，在阅读您的代码时，我认为您生成了一种网格样式，因此 makeGrid (7, 9) 会产生如下结果：
[
[[3, 3], [3, 5], [3, 7], [3, 9]],
[[5, 3], [5, 5], [5, 7], [5, 9]],
[[7, 3], [7, 5], [7, 7], [7, 9]]
]
相反，它 returns 一对数组：
[[3, 3], [3, 5], [3, 7], [3, 9], [5, 3], [5, 5], [5, 7], [5, 9], [7, 3], [7, 5], [7, 7], [7, 9]]
我很确定我不是唯一一个。 Bergi 在评论中建议修复以将其更改为前者。 （这就是将 grid =[...grid, ...row] 更改为 grid =[...grid, row] 的结果。）来自 Thankyou 的精彩回答基于相同的假设。
这是个问题。
当 reader 无法快速理解您的代码的作用时，维护起来就会变得更加困难......即使是几周后的您自己也是如此。
您可能会听到用递归代替循环的建议的原因与此有关。循环都是关于明确的命令式指令来获得你想要的东西，这取决于变异变量，然后你必须跟踪这些变量，并且很容易出现差一错误。递归通常更具声明性，它表示您正在寻找的结果只是将这些更简单的结果与我们当前的数据相结合，并指出如何通过基本案例或递归来获得更简单的结果打电话。
不过，可读性和可理解性的优势才是关键，而不是解决方案是递归的。
不要误会我的意思，递归是我最喜欢的编程技术之一。 Thankyou 的回答漂亮而优雅。但这并不是解决显式 for 循环出现的问题的唯一技术。通常，当我试图将初级程序员提升到中级以上时，我做的第一件事就是用更有意义的结构替换 for-loops。大多数循环都试图做几件事之一。他们试图将列表中的每个元素转换为新的元素 (map)，试图选择元素的一些重要子集 (filter)，试图找到第一个重要元素 (find)，或尝试将所有元素组合成一个值 (reduce)。通过使用这些，代码变得更加明确。
同样重要的是，如 Thankyou 的回答所示，将代码的可重用部分分开，以便您的主要功能可以专注于重要部分。下面的版本提取了一个函数 rangeBy，它在我常用的 range 函数的基础上添加了一个 step 参数。 range 创建一个整数范围，例如，range (3, 12) 产生 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] rangeBy 添加初始 step 参数，因此 range (2) (3, 12) 产生[3, 5, 7, 9, 11].
我们将 rangeBy 函数与 map 及其堂兄 flatMap 一起使用，以制作更明确的循环函数版本：
const rangeBy = (step) => (lo, hi) =>
[... Array (Math .ceil ((hi - lo + 1) / step))]
.map ((_, i) => i * step + lo)
const createGrid = (rows, columns) =>
rangeBy (2) (3, rows) .flatMap (y =>
rangeBy (2) (3, columns) .map (x =>
[y, x]
)
)
console .log (createGrid (7, 9))
知道 rangeBy 的作用，我们可以在心里将其理解为
const createGrid = (rows, columns) =>
[3, 5, 7, ..., rows] .flatMap (y =>
[3, 5, 7, ..., columns] .map (x =>
[y, x]
)
)
请注意，如果您想要我期望的行为，只需将 createGrid 中的 flatMap 替换为 map 即可实现。此外，如果您这样做，通过将 [y, x] 替换为 f (x, y) 并将 f 作为参数传递，添加 Thankyou 提供的更通用的行为是微不足道的。在此版本中保留硬编码的是将 rows 和 columns 转换为以 3 开头的奇数数组。我们可以将实际数组作为我们函数的参数，并应用 rangeBy 外部。但那时，我们可能正在寻找一个理想名称为 cartesianProduct.
所以递归是一个了不起的有用工具。但它是一种工具，而不是目标。然而，简单、可读的代码是一个重要目标。
更新
我本来想提这个的，只是忘记了。以下版本演示了 rangeBy 中的柯里化远非根本。我们可以轻松地使用单个调用：
const rangeBy = (step, lo, hi) =>
[... Array (Math .ceil ((hi - lo + 1) / step))]
.map ((_, i) => i * step + lo)
const createGrid = (rows, columns) =>
rangeBy (2, 3, rows) .flatMap (y =>
rangeBy (2, 3, columns) .map (x =>
[y, x]
)
)
console .log (createGrid (7, 9))
柯里化 rangeBy 的主要理由是，当它这样写时：
const rangeBy = (step) => (lo, hi) =>
[... Array (Math .ceil ((hi - lo + 1) / step))]
.map ((_, i) => i * step + lo)
我们可以通过简单地将 1 应用到上面来编写更常见的 range。也就是说，
const range = rangeBy (1)
range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
这太有用了，已经成为我写函数的惯用风格。但这不是简化问题的重要部分。