https://jsperf.com/iterative-array-flatten/2

ункция, которая выравнивает массив

const deepFlatten = (input) => {
  let result = [];
  input.forEach((val, index) => {
    if (Array.isArray(val)) {
      result.push(...deepFlatten(val));
    } else {
      result.push(val);
    }
  });
  return result;
};

Во время обсуждения мне сказали, что это не эффективно для памяти, поскольку это может вызвать переполнение стека.

Я читаю вhttp://2ality.com/2015/06/tail-call-optimization.html что я мог бы переписать его так, чтобы он был TCO-ed.

Как это будет выглядеть и как я могу измерить профиль использования памяти?

 Bergi26 сент. 2017 г., 22:56
Нет. Вы должны снова поговорить со своим партнером по обсуждению. Это не вызывает переполнение стека из-за его рекурсивности.
 MotKohn26 сент. 2017 г., 22:22
Чтобы измерить использование памяти, я бы просто поставил условную точку останова. напримерdeepFlatten([1,[2,[3,[4,5]]]]) затем установите точку останова, если val === 5, затем посмотрите, насколько глубока стека вызовов
 George Katsanos26 сент. 2017 г., 22:28
если вы укажете немного и добавите его в качестве ответа, это, безусловно, получит по крайней мере голосование!
 George Katsanos26 сент. 2017 г., 23:02
@ Bergi, почему это вызывает переполнение стека?
 MotKohn26 сент. 2017 г., 22:13
не уверен, просто предлагаяvar deepFlatten(input) => input.reduce((a,b)=>!Array.isArray(b)?a.concat(b):a.concat(deepFlatten(b)), [])

Ответы на вопрос(3)

Решение Вопроса

forEachпотому что для того, чтобы применить TCO, компилятор должен проверить, что вы не сохраняете «состояние» предыдущего вызова. В случаеforEach Вы сохраняете «состояние» текущей позиции.

Для того, чтобы реализовать это с TCO, вы можете переписать этоforeach чтобы быть реализованным с помощью рекурсивного вызова, это будет выглядеть примерно так:

function deepFlattenTCO(input) {
  const helper = (first, rest, result) => {
    if (!Array.isArray(first)) {
      result.push(first);
      if (rest.length > 0) {
        return helper(rest, [], result);
      } else {
        return result;
      }
    } else {
      const [newFirst, ...newRest] = first.concat(rest);

      return helper(newFirst, newRest, result);
    }
  };

  return helper(input, [], []);
}

console.log(deepFlattenTCO([
  [1], 2, [3], 4, [5, 6, [7]]
]));

Вы можете видеть это в каждомreturn единственная выполняемая операция - это рекурсивный вызов, поэтому вы не сохраняете «состояние» между рекурсивными вызовами, поэтому компилятор применяет оптимизацию.

 felixmosh26 сент. 2017 г., 22:45
Обычной практикой преобразования каждого типа рекурсивной функции в рекурсивную функцию TCO является передача «вычисленного состояния» самой рекурсии.
 George Katsanos26 сент. 2017 г., 22:55
У вас есть какие-либо автоматизированные инструменты, которые бы измеряли использование памяти функцией? (инструменты разработчика, я думаю?) PS: спасибо!
 felixmosh26 сент. 2017 г., 22:47
Классический пример для этого:blog.moertel.com/posts/...
 felixmosh26 сент. 2017 г., 22:44
Да, параметр rest предназначен для сохранения этого «состояния» предыдущих вызовов ...
 George Katsanos26 сент. 2017 г., 22:41
Я знаю, что это не было в моем первоначальном вопросе, но разве это решение не создает много промежуточных массивов? также не могли бы вы объяснить, что аргумент отдыха для?

и оптимизация хвостовой рекурсии может даже предотвратить их перебор стека.

Тем не менее, любую рекурсивную функцию можно преобразовать в более уродливое решение на основе итераторов, которое может быть привлекательным только с точки зрения потребления памяти и производительности, хотя и не на что посмотреть.

Видеть:Итеративное решение для выравнивания n-го вложенного массива в Javascript

и, возможно, это испытание разных подходов:https://jsperf.com/iterative-array-flatten/2

хвостовые вызовы в целом

Яподелился еще одним функциональным подходом к уплощению массивов в JavaScript; Я думаю, что ответ показывает лучший способ решения этой конкретной проблемы, но не все функции можно так хорошо разложить. Этот ответ будет посвящен хвостовым вызовам в рекурсивных функциях и хвостовым вызовамв общем

В общем, для перемещения повторяющегося вызова в хвостовую позицию, вспомогательная функция (aux ниже) создается, когда параметры функции содержат все необходимое состояние для завершения этого шага вычисления

const flattenDeep = arr =>
  {
    const aux = (acc, [x,...xs]) =>
      x === undefined
        ? acc
        : Array.isArray (x)
          ? aux (acc, x.concat (xs))
          : aux (acc.concat (x), xs)
    return aux ([], arr)
  }
        
const data = 
  [0, [1, [2, 3, 4], 5, 6], [7, 8, [9]]]
  
console.log (flattenDeep (data))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

JS на самом деле не имеет устранения хвостового вызова

Тем не менее, большинство реализаций JavaScript по-прежнему не поддерживают хвостовые вызовы - вам придется подойти к этому по-другому, если вы хотите использовать рекурсию в своей программе и не беспокоиться о том, что стек будет разбит -об этом я тоже уже много писал

Мое нынешнее стремление - это стиль clojureloop/recur пары, потому что это дает вам безопасность стека и одновременно позволяет писать вашу программу с использованием красивого, чистого выражения

const recur = (...values) =>
  ({ type: recur, values })
  
const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.values)
    return acc
  }
  
const flattenDeep = arr =>
  loop ((acc = [], [x,...xs] = arr) =>
    x === undefined
      ? acc
      : Array.isArray (x)
        ? recur (acc, x.concat (xs))
        : recur (acc.concat (x), xs))
        
let data = []
for (let i = 2e4; i>0; i--)
  data = [i, data]

// data is nested 20,000 levels deep
// data = [1, [2, [3, [4, ... [20000, []]]]]] ...

// stack-safe !
console.log (flattenDeep (data))
// [ 1, 2, 3, 4, ... 20000 ]

важная позиция

почему так важно положение хвоста? ну ты когда-нибудь думал об этомreturn ключевое слово? Это способвне вашей функции; и в строго оцененном языке, таком как JavaScript,return <expr> означает все ввыраж необходимо вычислить, прежде чем мы сможем отправить результат.

Есливыраж содержит подвыражение с вызовами функций, которые не находятся в хвостовой позиции, эти вызовы будут вводить новый кадр, вычислять промежуточное значение, а затем возвращать его в вызывающий кадр для хвостового вызова - поэтому стек может переполниться, если есть нет способа определить, когда этобезопасный удалить кадр стека

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

const add = (x,y) =>
  // + is in tail position
  x + y

const sq = x =>
  // * is in tail position
  x * x
  
const sqrt = x =>
  // Math.sqrt is in tail position
  Math.sqrt (x)

const pythag = (a,b) =>
  // sqrt is in tail position
  // sq(a) and sq(b) must *return* to compute add
  // add must *return* to compute sqrt
  sqrt (add (sq (a), sq (b)))

// console.log displays the correct value becaust pythag *returns* it
console.log (pythag (3,4)) // 5

Оставайтесь со мной здесь на минуту - теперь представьте, что не быловернуть значения - поскольку функция не имеет возможности отправить значение обратно вызывающей стороне, конечно, мы можем легко предположить, что все кадры могут быть немедленно отброшены после оценки функции

// instead of
const add = (x,y) =>
  { return x + y }

// no return value
const add = (x,y) =>
  { x + y }

// but then how do we get the computed result?
add (1,2) // => undefined

продолжение прохождения стиля

ВойтиСтиль прохождения продолжения - добавив параметр продолжения к каждой функции, мы словно изобрели наш собственный механизм возврата

Не удивляйтесь приведенным ниже примерам - большинство людей уже видели стиль прохождения продолжения в форме этих неправильно понятых вещей, называемыхобратные вызовы

// jQuery "callback"
$('a').click (event => console.log ('click event', event))

// node.js style "callback"
fs.readFile ('entries.txt', (err, text) =>
  err
    ? console.error (err)
    : console.log (text))

Так вот как вы работаете с вычисленным результатом - вы передаете его в продолжение

// add one parameter, k, to each function
// k makes *return* into a normal function
// note {}'s are used to suppress the implicit return value of JS arrow functions
const add = (x,y,k) =>
  { k (x + y) }

const sq = (x,k) =>
  { k (x * x) }
  
const sqrt = (x,k) =>
  { k (Math.sqrt (x)) }

const pythag = (a,b,k) =>
  // sq(a) is computed, $a is the result
  sq (a, $a => {
    // sq(b) is computed, $b is the result
    sq (b, $b => {
      // add($a,$b) is computed, $sum is the result
      add ($a, $b, $sum => {
        // sqrt ($sum) is computed, conintuation k is passed thru
        sqrt ($sum, k) }) }) })
  
// here the final continuation is to log the result
// no *return* value was used !
// no reason to keep frames in the stack !
pythag (3, 4, $c => { console.log ('pythag', $c) })

как получить значение?

Этотзнаменитый вопрос:Как вернуть ответ от асинхронного вызова? сбило с толку миллионы программистов - только это действительно не имеет никакого отношения к «асинхронному вызову» и всему, что связано с продолжениями и возвращают ли эти продолжения что-либо

  // nothing can save us...
  // unless pythag *returns*
  var result = pythag (3,4, ...)
  console.log (result) // undefined

Без возвращаемого значения выдолжен используйте продолжение, чтобы переместить значение на следующий шаг в вычислении - это не может быть первым способом, которым я пытался сказать, что ^^

но все в хвостовой позиции!

Я знаю, что это может быть трудно сказать, просто посмотрев на него, но каждая функция имеет точноодин вызов функции в хвостовой позиции - если мы восстановимвернуть функциональности в наших функциях, значение вызова 1 является значением вызова 2, является значением вызова 3 и т. д. - нет необходимости вводить новый кадр стека для последующих вызовов в этой ситуации - вместо этого кадр вызова 1 может быть повторно используется для вызова 2, а затем снова используется для вызова 3; и мыВсе еще получить сохранить возвращаемое значение!

// restore *return* behaviour
const add = (x,y,k) =>
  k (x + y)

const sq = (x,k) =>
  k (x * x)
  
const sqrt = (x,k) =>
  k (Math.sqrt (x))

const pythag = (a,b,k) =>
  sq (a, $a =>
    sq (b, $b =>
      add ($a, $b, $sum =>
        sqrt ($sum, k))))
  
// notice the continuation returns a value now: $c
// in an environment that optimises tail calls, this would only use 1 frame to compute pythag
const result =
  pythag (3, 4, $c => { console.log ('pythag', $c); return $c })
  
// sadly, the environment you're running this in likely took almost a dozen
// but hey, it works !
console.log (result) // 5

хвостовые вызовы в целом; очередной раз

это преобразование «нормальной» функции в функцию стиля передачи продолжения может быть механическим процессом и выполняться автоматически - но чтореальный смысл ставить все в хвостовой позиции?

Хорошо, если мы знаем, что значение кадра 1 является значением кадра 2, которое является значением кадра 3 и т. Д., Мы можем свернуть кадры стека вручную, используяwhile цикл, в котором вычисляемый результат обновляется на месте во время каждой итерации - функция, использующая эту технику, называетсябатут

Конечно, о батутах чаще всего говорят при написании рекурсивных функций, потому что рекурсивная функция может многократно «подпрыгивать» (вызывать другой вызов функции); или даже на неопределенный срок - но это не значит, что мы не можем продемонстрировать батут на нашемpythag функция, которая только порождает несколькоcalls

const add = (x,y,k) =>
  k (x + y)

const sq = (x,k) =>
  k (x * x)
  
const sqrt = (x,k) =>
  k (Math.sqrt (x))

// pythag now returns a "call"
// of course each of them are in tail position ^^
const pythag = (a,b,k) =>
  call (sq, a, $a =>
    call (sq, b, $b =>
      call (add, $a, $b, $sum =>
        call (sqrt, $sum, k))))
  

const call = (f, ...values) =>
  ({ type: call, f, values })
  
const trampoline = acc =>
  {
    // while the return value is a "call"
    while (acc && acc.type === call)
      // update the return value with the value of the next call
      // this is equivalent to "collapsing" a stack frame
      acc = acc.f (...acc.values)
    // return the final value
    return acc
  }

// pythag now returns a type that must be passed to trampoline
// the call to trampoline actually runs the computation
const result =
  trampoline (pythag (3, 4, $c => { console.log ('pythag', $c); return $c }))

// result still works
console.log (result) // 5

почему ты мне все это показываешь?

Таким образом, даже если наша среда не поддерживает рекурсию, ориентированную на стек, пока мы держим все в хвостовом положении и используемcall помощник, теперь мы можем конвертировать любой стек вызовов в цикл

// doesn't matter if we have 4 calls, or 1 million ... 
trampoline (call (... call (... call (...))))

В первом примере кода я показал использованиеauxiliary цикл, но я также использовал довольно умный (хотя и неэффективный) цикл, который не требовал глубокого повторения в структуре данных - иногда это не всегда возможно; Например, иногда ваша рекурсивная функция может порождать 2 или 3 повторяющихся вызова - что тогда делать?

Ниже я собираюсь показать вамflatten как наивная, не хвостовая рекурсивная процедура - здесь важно отметить, что одна ветвь условного приводит кдва повторяющиеся звонкиflatten - этот древовидный повторяющийся процесс может сначала показаться сложным в итеративном цикле, но тщательное механическое преобразование в стиль передачи продолжения покажет, что этот метод может работать практически в любых (если не во всех) сценариях.

[ ЧЕРНОВОЙ ВАРИАНТ ]

// naive, stack-UNSAFE
const flatten = ([x,...xs]) =>
  x === undefined
    ? []
    : Array.isArray (x)
      // two recurring calls
      ? flatten (x) .concat (flatten (xs))
      // one recurring call
      : [x] .concat (flatten (xs))

Продолжение прохождения стиля

// continuation passing style
const flattenk = ([x,...xs], k) =>
  x === undefined
    ? k ([])
    : Array.isArray (x)
      ? flattenk (x, $x =>
          flattenk (xs, $xs =>
            k ($x.concat ($xs))))
      : flattenk (xs, $xs =>
          k ([x].concat ($xs)))

Продолжение прохождения стиля с батутом

const call = (f, ...values) =>
  ({ type: call, f, values })
      
const trampoline = acc =>
  {
    while (acc && acc.type === call)
      acc = acc.f (...acc.values)
    return acc
  }

const flattenk = ([x,...xs], k) =>
  x === undefined
    ? call (k, [])
    : Array.isArray (x)
      ? call (flattenk, x, $x =>
          call (flattenk, xs, $xs =>
            call (k, $x.concat ($xs))))
      : call (flattenk, xs, $xs =>
          call (k, ([x].concat ($xs))))

const flatten = xs =>
  trampoline (flattenk (xs, $xs => $xs))

let data = []
for (let i = 2e4; i>0; i--)
  data = [i, data];

console.log (flatten (data))

вауп, вы случайно обнаружили монады

[ ЧЕРНОВОЙ ВАРИАНТ ]

// yours truly, the continuation monad
const cont = x =>
  k => k (x)

// back to functions with return values
// notice we don't need the additional `k` parameter
// but this time wrap the return value in a continuation, `cont`
// ie, `cont` replaces *return*
const add = (x,y) =>
  cont (x + y)

const sq = x =>
  cont (x * x)
  
const sqrt = x =>
  cont (Math.sqrt (x))

const pythag = (a,b) =>
  // sq(a) is computed, $a is the result
  sq (a) ($a =>
    // sq(b) is computed, $b is the result
    sq (b) ($b =>
      // add($a,$b) is computed, $sum is the result
      add ($a, $b) ($sum =>
        // sqrt ($sum) is computed, a conintuation is returned 
        sqrt ($sum))))
  
// here the continuation just returns whatever it was given
const $c =
  pythag (3, 4) ($c => $c)
  
console.log ($c)
// => 5

продолжения с разделителями

[ ЧЕРНОВОЙ ВАРИАНТ ]

const identity = x =>
  x

const cont = x =>
  k => k (x)

// reset
const reset = m =>
  k => m (k)

// shift
const shift = f =>
  k => f (x => k (x) (identity))

const concatMap = f => ([x,...xs]) =>
  x === undefined
    ? [ ]
    : f (x) .concat (concatMap (f) (xs))

// because shift returns a continuation, we can specialise it in meaningful ways
const amb = xs =>
  shift (k => cont (concatMap (k) (xs)))

const pythag = (a,b) =>
  Math.sqrt (Math.pow (a, 2) + Math.pow (b, 2))

const pythagTriples = numbers =>
  reset (amb (numbers) ($x =>
          amb (numbers) ($y =>
            amb (numbers) ($z =>
              // if x,y,z are a pythag triple
              pythag ($x, $y) === $z
                // then continue with the triple
                ? cont ([[ $x, $y, $z ]])
                // else continue with nothing
                : cont ([ ])))))
        (identity)
        
console.log (pythagTriples ([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]))
// [ [ 3, 4, 5 ], [ 4, 3, 5 ], [ 6, 8, 10 ], [ 8, 6, 10 ] ]      

 user63318328 сент. 2017 г., 12:56
@GeorgeKatsanos есть много, чтобы написать на эту тему, и я хотел собрать этот ответ слишком долго - только, я должен лечь спать! Я оставлю это как черновик и закончу завтра ^^
 George Katsanos28 сент. 2017 г., 11:22
Вы используете деструктуризацию и широкое распространение, и для меня это немного затрудняет чтение, но это определенно интересно.

Ваш ответ на вопрос