Одним из таких способов является использование стиля прохождения продолжения.В этом методе к вашей функции добавляется дополнительный параметр, чтобы указать, как продолжить вычисление
Ниже мы подчеркиваем каждый хвостовой вызов с помощью /**/
function identity(x) {
/**/return x;
}
function getSublistsWithFixedSize(arr, size, cont = identity) {
if(size === 0) {
/**/ return cont([[]]);
}
if(arr.length === 0 ) {
/**/ return cont([]);
}
let [head, ...tail] = arr;
/**/return getSublistsWithFixedSize(tail, size - 1, function (sublists0) {
/**/ return getSublistsWithFixedSize(tail, size, function (sublists1) {
let sublists2 = sublists0.map(x => {
let y = x.slice();
y.unshift(head);
return y;
});
/**/ return cont(sublists1.concat(sublists2));
});
});
}
console.log(getSublistsWithFixedSize([1,2,3,4], 2))
// [ [ 3, 4 ], [ 2, 4 ], [ 2, 3 ], [ 1, 4 ], [ 1, 3 ], [ 1, 2 ] ]
Вы можете думать о продолжении почти так же, как мы изобретаем наш собственный механизм return;только здесь это функция, а не специальный синтаксис.
Возможно, это станет более очевидным, если мы укажем собственное продолжение на сайте вызовов
getSublistsWithFixedSize([1,2,3,4], 2, console.log)
// [ [ 3, 4 ], [ 2, 4 ], [ 2, 3 ], [ 1, 4 ], [ 1, 3 ], [ 1, 2 ] ]
Или даже
getSublistsWithFixedSize([1,2,3,4], 2, sublists => sublists.length)
// 6
Шаблон может быть легче увидеть с более простой функцией.Рассмотрим знаменитый fib
const fib = n =>
n < 2
? n
: fib (n - 1) + fib (n - 2)
console.log (fib (10))
// 55
Ниже мы преобразуем его в стиль продолжения
const identity = x =>
x
const fib = (n, _return = identity) =>
n < 2
? _return (n)
: fib (n - 1, x =>
fib (n - 2, y =>
_return (x + y)))
fib (10, console.log)
// 55
console.log (fib (10))
// 55
Хочу отметить, что использование .slice и .unshift не является необходимым для этой конкретной проблемы.Я дам вам возможность предложить некоторые другие решения, прежде чем поделиться альтернативой.
Редактировать
Вы проделали хорошую работу по переписыванию своей программы, но, как вы определили, тамЕсть еще области, которые можно улучшить.Я думаю, что одна из проблем, с которыми вы сталкиваетесь больше всего - это использование операций мутации массивов, таких как arr[0] = x или arr.push(x), arr.pop() и arr.unshift(x).Конечно, вы можете использовать эти операции для достижения желаемого результата, но в функциональной программе мы думаем о вещах по-другому.Вместо того, чтобы уничтожать старое значение, перезаписывая его, мы только читаем значения и создаем новые единицы.
Мы также избегаем операций высокого уровня, таких как Array.fill илиuniq (не уверен, какую реализацию вы выбрали), так как мы можем построить результат естественным образом с помощью рекурсии.
Индуктивная логика для вашей рекурсивной функции идеальна, поэтому нам не нужно настраивать это
- если
size равен нулю, вернуть пустой результат [[]] - , если входной массив пуст, вернуть пустой набор,
[] - в противном случае
size это хотя бы один, и у нас есть хотя бы один элемент x - получить подсписки на один размер меньше r1, получить подсписки того же размера r2, вернуть объединенный результат r1 и r2добавляя x к каждому результату в r1
Мы можем закодировать это простым способом.Обратите внимание на сходство в структуре по сравнению с вашей исходной программой.
const sublists = (size, [ x = None, ...rest ], _return = identity) =>
size === 0
? _return ([[]])
: x === None
? _return ([])
: sublists // get sublists of 1 size smaller, r1
( size - 1
, rest
, r1 =>
sublists // get sublists of same size, r2
( size
, rest
, r2 =>
_return // return the combined result
( concat
( r1 .map (r => prepend (x, r)) // prepend x to each r1
, r2
)
)
)
)
Мы называем это size и входным массивом
console.log (sublists (2, [1,2,3,4,5]))
// [ [ 1, 2 ]
// , [ 1, 3 ]
// , [ 1, 4 ]
// , [ 1, 5 ]
// , [ 2, 3 ]
// , [ 2, 4 ]
// , [ 2, 5 ]
// , [ 3, 4 ]
// , [ 3, 5 ]
// , [ 4, 5 ]
// ]
Наконец, мы предоставляем зависимости identity, None, concat и prepend - Ниже concat - пример предоставления функционального интерфейса к методу объекта.Это один из многих методов, используемых для увеличения повторного использования функций в ваших программах и одновременного улучшения читабельности
const identity = x =>
x
const None =
{}
const concat = (xs, ys) =>
xs .concat (ys)
const prepend = (value, arr) =>
concat ([ value ], arr)
Вы можете запустить полную программу в вашем браузере ниже
const identity = x =>
x
const None =
{}
const concat = (xs, ys) =>
xs .concat (ys)
const prepend = (value, arr) =>
concat ([ value ], arr)
const sublists = (size, [ x = None, ...rest ], _return = identity) =>
size === 0
? _return ([[]])
: x === None
? _return ([])
: sublists // get sublists of 1 size smaller, r1
( size - 1
, rest
, r1 =>
sublists // get sublists of same size, r2
( size
, rest
, r2 =>
_return // return the combined result
( concat
( r1 .map (r => prepend (x, r)) // prepend x to each r1
, r2
)
)
)
)
console.log (sublists (3, [1,2,3,4,5,6,7]))
// [ [ 1, 2, 3 ]
// , [ 1, 2, 4 ]
// , [ 1, 2, 5 ]
// , [ 1, 2, 6 ]
// , [ 1, 2, 7 ]
// , [ 1, 3, 4 ]
// , [ 1, 3, 5 ]
// , [ 1, 3, 6 ]
// , [ 1, 3, 7 ]
// , [ 1, 4, 5 ]
// , [ 1, 4, 6 ]
// , [ 1, 4, 7 ]
// , [ 1, 5, 6 ]
// , [ 1, 5, 7 ]
// , [ 1, 6, 7 ]
// , [ 2, 3, 4 ]
// , [ 2, 3, 5 ]
// , [ 2, 3, 6 ]
// , [ 2, 3, 7 ]
// , [ 2, 4, 5 ]
// , [ 2, 4, 6 ]
// , [ 2, 4, 7 ]
// , [ 2, 5, 6 ]
// , [ 2, 5, 7 ]
// , [ 2, 6, 7 ]
// , [ 3, 4, 5 ]
// , [ 3, 4, 6 ]
// , [ 3, 4, 7 ]
// , [ 3, 5, 6 ]
// , [ 3, 5, 7 ]
// , [ 3, 6, 7 ]
// , [ 4, 5, 6 ]
// , [ 4, 5, 7 ]
// , [ 4, 6, 7 ]
// , [ 5, 6, 7 ]
// ]