Foldr, который не падает и работает достаточно хорошо - PullRequest
Новая
       32

Foldr, который не падает и работает достаточно хорошо

0 голосов
/ 16 мая 2018

Мне нужен фолд, который похож на фолдер в Хаскеле или Лиспе. Мой Foldr вызывает переполнение стека на больших массивах, и, вероятно, потому, что большое количество ожидающих операций в стеке не может быть уменьшено, пока не достигнет базового варианта. Как бы вы оптимизировали мой Foldr, чтобы он работал достаточно хорошо для больших массивов. 

const foldr = (f, acc, [x, ...xs]) => 
  (typeof x === 'undefined') 
  ? acc 
  : f (x, foldr (f, acc, xs))

foldr((x, acc) => x + acc, 0, [...Array(100000).keys()])

Ответы [ 2 ]

0 голосов
/ 16 мая 2018

Проблема состоит в том, что структура, подобная списку по умолчанию, которую использует JavaScript, представляет собой изменяемые массивы (не истинные c-подобные массивы, они могут быть внутренне реализованы в виде деревьев), в то время как функциональные языки, такие как Haskell или Lisp, используют связанные списки. Вы можете получить первый элемент и остальную часть связанного списка без мутаций за постоянное время. Если вы хотите сделать то же самое в JavaScript (без мутации), вам нужно создать (выделить) новый массив, чтобы получить оставшуюся часть массива.

Однако вся складка может быть реализована с внутренней мутацией. Вся функция не будет делать никаких внешних мутаций: 

const foldr = (f, initialValue, arr) => {
  let value = initialValue;

  for (let i = arr.length - 1; i >= 0; i--) {
    value = f(arr[i], value)
  }

  return value;
}
0 голосов
/ 16 мая 2018

foldr довольно почти reduceRight: 

const flip = f => (a, b) => f(b, a)

const foldr = (f, acc, arr) =>
  arr.reduceRight(flip(f), acc)

Замените arr.reduceRight на [...arr].reduceRight, если вы хотите сохранить поддержку произвольных итераций, которые дает вам [x, ...xs] распаковка. 

const flip = f => (a, b) => f(b, a)

const foldr = (f, acc, arr) =>
  arr.reduceRight(flip(f), acc)

console.log(foldr((x, acc) => x + acc, 0, [...Array(100000).keys()]))
...