примитивная рекурсия
Вот один из возможных способов построения сетки с использованием рекурсии -
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 ]
// ]
// ]
работать умнее, не сложнее
Согласно комментарию Берги, вы можете уменьшить некоторые дополнительные аргументы, используя 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]
]
]
]
любые размеры; плоский результат
Согласно вашему комментарию, вам нужен массив пар flat . Вы можете добиться этого, просто заменив 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]]
Learn more
As другие показывают, что эта конкретная версия makeGrid с использованием flatMap эффективно вычисляет декартово произведение . К тому времени, как вы обернетесь вокруг flatMap, вы уже знаете монаду List!
больше торта, пожалуйста!
Если вы ' жажду большего, я хочу дать вам учебник по одной из моих любимых тем в вычислительном исследовании: продолжения с разделителями . Начало работы с продолжениями первого класса включает в себя разработку интуиции о некоторых способах их использования -
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, выше amb инкапсулирует это понятие ambiguous ( недетерминированные c) вычисления. Мы можем легко написать наше 2-мерное 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]]
Создание сетки N-размерности также очень просто благодаря amb. Реализация почти исчезла -
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 не поддерживает продолжения первого класса, но ничто не мешает нам реализовать их самостоятельно -
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!
Учитывая контекст вашего вопроса, должно быть очевидно, что это чисто академическое упражнение. Ответ Скотта предлагает разумное обоснование некоторых компромиссов, которые мы делаем. Надеемся, что в этом разделе показано, что более мощные вычислительные функции могут легко решать проблемы, которые изначально кажутся сложными.
Первоклассные продолжения открывают мощный поток управления для ваших программ. Вы когда-нибудь задумывались, как JavaScript реализует function* и yield? Что если у JavaScript не было этих способностей? Прочтите пост , чтобы увидеть, как мы можем сделать это (и даже больше), используя только обычные функции.
демонстрация кода продолжения
Посмотрите, как это работает в вашем собственном браузере! Разверните фрагмент ниже, чтобы сгенерировать сетки, используя продолжения с разделителями ... в 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
)
)