JavaScript: рекурсивная анонимная функция?

Question

Допустим, у меня есть базовая рекурсивная функция:

function recur(data) {
    data = data+1;
    var nothing = function() {
        recur(data);
    }
    nothing();
}

Как я могу это сделать, если у меня есть анонимная функция, такая как ...

(function(data){
    data = data+1;
    var nothing = function() {
        //Something here that calls the function?
    }
    nothing();
})();

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

Answer 1

Вы можете дать функции имя, даже когда вы создаете функцию как значение, а не как выражение "объявление функции".Другими словами:

(function foo() { foo(); })();

является рекурсивной функцией с укладкой в ​​стек.Тем не менее, вы , вероятно, не , возможно, не захотите делать это в целом, потому что есть некоторые странные проблемы с различными реализациями Javascript.( note - это довольно старый комментарий; некоторые / многие / все проблемы, описанные в блоге Kangax, могут быть исправлены в более современных браузерах.)

Когда вы даете такое имяимя не видно вне функции (ну, это не должно быть; это одна из странностей).Это похоже на «letrec» ​​в Lisp.

Что касается arguments.callee, то он запрещен в «строгом» режиме и, как правило, считается плохой вещью, поскольку затрудняет некоторые оптимизации.Это также намного медленнее, чем можно было бы ожидать.

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

asyncThingWithCallback(params, (function() {
  function recursive() {
    if (timeToStop())
      return whatever();
    recursive(moreWork);
  }
  return recursive;
})());

Что определяет функцию с хорошей, безопасной, не нарушенной в IE функцией объявление оператор, создающий локальную функцию, имя которой не будет загрязнять глобальное пространство имен.Функция-обертка (действительно анонимная) просто возвращает эту локальную функцию.

Answer 2

Люди говорили о комбинаторе Y в комментариях, но никто не написал его как ответ.

Комбинатор Y можно определить в javascript следующим образом: (спасибо steamer25 за ссылку)

var Y = function (gen) {
  return (function(f) {
    return f(f);
  }(function(f) {
    return gen(function() {
      return f(f).apply(null, arguments);
    });
  }));
}

И когда вы хотите передать свою анонимную функцию:

(Y(function(recur) {
  return function(data) {
    data = data+1;
    var nothing = function() {
      recur(data);
    }
    nothing();
  }
})());

Самое важное, что следует отметить в этом решении, это то, что вы не должны его использовать.

Answer 3

U-комбинатор

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

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

const U = f => f (f)

U (f => (console.log ('stack overflow imminent!'), U (f)))

Мы можем остановить бесконечную рекурсию, используя различные методы.Здесь я напишу нашу анонимную функцию, чтобы она возвращала другую анонимную функцию, которая ожидает ввода;в этом случае какое-то число.Если указан номер, если он больше 0, мы продолжим повторение, в противном случае вернем 0.

const log = x => (console.log (x), x)

const U = f => f (f)

// when our function is applied to itself, we get the inner function back
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
// returns: (x => x > 0 ? U (f) (log (x - 1)) : 0)
// where f is a reference to our outer function

// watch when we apply an argument to this function, eg 5
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0) (5)
// 4 3 2 1 0

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

const log = x => (console.log (x), x)

const U = f => f (f)

const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)

countDown (5)
// 4 3 2 1 0

countDown (3)
// 2 1 0

Только это не прямая рекурсия - функция, которая вызывает себя, используя свое собственное имя.Наше определение countDown не ссылается на себя внутри своего тела, и все же возможна рекурсия

// direct recursion references itself by name
const loop = (params) => {
  if (condition)
    return someValue
  else
    // loop references itself to recur...
    return <b>loop</b> (adjustedParams)
}

// U combinator does not need a named reference
// no reference to `countDown` inside countDown's definition
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)

---

Как удалить самоссылку из существующей функции с помощью U комбинатора

Здесь я покажу вам, как взять рекурсивную функцию, которая использует ссылку на себя, и заменить ее на функцию, которая использует U-комбинатор вместо собственной ссылки

const factorial = x =>
  x === 0 ? 1 : x * factorial (x - 1)
  
console.log (factorial (5)) // 120

Теперь с помощью комбинатора U замените внутреннюю ссылку на factorial

const U = f => f (f)

const factorial = U (f => x =>
  x === 0 ? 1 : x * U (f) (x - 1))

console.log (factorial (5)) // 120

Основной шаблон замены - это.Запомните, мы будем использовать аналогичную стратегию в следующем разделе

// self reference recursion
const foo =         x => ...   foo (nextX) ...

// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)

---

Y комбинатор

связанный: комбинаторы U и Y объяснили, используя зеркальную аналогию

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

Во-первых, давайте выведем наш собственный Y-комбинатор

// standard definition
const Y = f => f (Y (f))

// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (<b>x =></b> Y (f) <b>(x)</b>)

// remove reference to self using U combinator
const Y = <b>U (h =></b> f => f (x => <b>U (h)</b> (f) (x))<b>)</b>

Теперь посмотрим, как его использование сравнивается.к U-комбинатору.Обратите внимание, чтобы повториться, вместо U (f) мы можем просто позвонить f ()

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

Y (f => (console.log ('stack overflow imminent!'),  f ()))

Теперь я продемонстрирую программу countDown с использованием Y - вы увидите, что программы почти идентичны, но Y-комбинатор делает вещи немного чище

const log = x => (console.log (x), x)

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const countDown = Y (f => x => x > 0 ? f (log (x - 1)) : 0)

countDown (5)
// 4 3 2 1 0

countDown (3)
// 2 1 0

А теперь мы тоже увидим factorial

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const factorial = Y (f => x =>
  x === 0 ? 1 :  x * f (x - 1))

console.log (factorial (5)) // 120

---

U и Y комбинатор с более чем 1 параметром

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

Мы можем использовать составные данные, такие как массив или что-то в этом роде ...

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (f => ([a, b, x]) =>
  x === 0 ? a : f ([b, a + b, x - 1]))

// starting with 0 and 1, generate the 7th number in the sequence
console.log (fibonacci ([0, 1, 7])) 
// 0 1 1 2 3 5 8 13

Но это плохо, потому что показывает внутреннее состояние (счетчики a и b).Было бы хорошо, если бы мы могли просто позвонить fibonacci (7), чтобы получить желаемый ответ.

Используя то, что мы знаем о каррируемых функциях (последовательности унарных (1-параметрических) функций), мы можем легко достичь нашей целибез необходимости изменять наше определение Y или полагаться на составные данные или расширенные функции языка.

Посмотрите определение fibonacci ниже.Мы немедленно применяем 0 и 1, которые связаны с a и b соответственно.Теперь Фибоначчи просто ждет, когда будет предоставлен последний аргумент, который будет связан с x.Когда мы возвращаемся, мы должны вызывать f (a) (b) (x) (не f (a,b,x)), потому что наша функция находится в карри.

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (f => a => b => x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)

console.log (fibonacci (7)) 
// 0 1 1 2 3 5 8 13

---

Этот тип шаблона может быть полезен для определения всех видов функций.Ниже мы увидим еще две функции, определенные с использованием комбинатора Y (range и reduce) и производной от reduce, map.

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const range = Y (f => acc => min => max =>
  min > max ? acc : f ([...acc, min]) (min + 1) (max)) ([])

const reduce = Y (f => g => y => ([x,...xs]) =>
  x === undefined ? y : f (g) (g (y) (x)) (xs))
  
const map = f =>
  reduce (ys => x => [...ys, f (x)]) ([])
  
const add = x => y => x + y

const sq = x => x * x

console.log (range (-2) (2))
// [ -2, -1, 0, 1, 2 ]

console.log (reduce (add) (0) ([1,2,3,4]))
// 10

console.log (map (sq) ([1,2,3,4]))
// [ 1, 4, 9, 16 ]

---

ЭТО ВСЕ АНОНИМНОЕ OMG

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

/* const U = f => f (f)
 *
 * const Y = U (h => f => f (x => U (h) (f) (x)))
 *
 * const fibonacci = Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
 *
 */

/*
 * given fibonacci (7)
 *
 * replace fibonacci with its definition
 * Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
 *
 * replace Y with its definition
 * U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
//
 * replace U with its definition
 * (f => f (f)) U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
 */

let result =
  (f => f (f)) (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
  
console.log (result) // 13

И вот он у вас - fibonacci (7) вычисляется рекурсивно, используя только анонимные функции

Answer 4

Вместо этого может быть проще использовать «анонимный объект»:

({
  do: function() {
    console.log("don't run this ...");
    this.do();
  }
}).do();

Ваше глобальное пространство полностью незагрязнено.Это довольно просто.И вы можете легко воспользоваться неглобальным состоянием объекта.

Answer 5

Я бы не стал делать это как встроенную функцию.Это раздвигает границы хорошего вкуса и на самом деле ничего вам не дает.

Если вам действительно нужно, есть arguments.callee, как в ответе Фабрицио.Однако это обычно считается нецелесообразным и не допускается в «строгом режиме» ECMAScript пятого издания.Хотя ECMA 3 и не строгий режим не уходят, работа в строгом режиме обещает больше возможных языковых оптимизаций.

Можно также использовать именованную встроенную функцию:

(function foo(data){
    data++;
    var nothing = function() {
        foo(data);
    }
    nothing();
})();

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

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

Answer 6

(function(data){
    var recursive = arguments.callee;
    data = data+1;
    var nothing = function() {
        recursive(data)
    }
    nothing();
})();

Answer 7

Вы можете сделать что-то вроде:

(foo = function() { foo(); })()

или в вашем случае:

(recur = function(data){
    data = data+1;
    var nothing = function() {
        if (data > 100) return; // put recursion limit
        recur(data);
    }
    nothing();
})(/* put data init value here */ 0);

Answer 8

Почему бы не передать функцию самой функции?

    var functionCaller = function(thisCaller, data) {
        data = data + 1;
        var nothing = function() {
            thisCaller(thisCaller, data);
        };
        nothing();
    };
    functionCaller(functionCaller, data);

Answer 9

Когда вы объявляете анонимную функцию следующим образом:

(function () {
    // Pass
}());

Он считается выражением функции и имеет необязательное имя (которое можно использовать для вызова его изнутри. Но поскольку это выражение функции (а не выражение), оно остается анонимным (но имеет имя, которое можно вызывать ). Так что эта функция может вызывать сама себя:

(function foo () {
    foo();
}());
foo //-> undefined

Answer 10

В определенных ситуациях вы должны полагаться на анонимные функции.Дана рекурсивная map функция:

const map = f => acc => ([head, ...tail]) => head === undefined 
 ? acc
 : map (f) ([...acc, f(head)]) (tail);

const sqr = x => x * x;
const xs = [1,2,3,4,5];

console.log(map(sqr) ([0]) (xs)); // [0] modifies the structure of the array

Обратите внимание, что map не должно изменять структуру массива.Таким образом, аккумулятор acc не нужно подвергать воздействию.Мы можем заключить map в другую функцию, например:

const map = f => xs => {
  let next = acc => ([head, ...tail]) => head === undefined
   ? acc
   : map ([...acc, f(head)]) (tail);

  return next([])(xs);
}

Но это решение довольно многословно.Давайте использовать недооцененный комбинатор U:

const U = f => f(f);

const map = f => U(h => acc => ([head, ...tail]) => head === undefined 
 ? acc
 : h(h)([...acc, f(head)])(tail))([]);

const sqr = x => x * x;
const xs = [1,2,3,4,5];

console.log(map(sqr) (xs));

Кратко, не так ли?U очень прост, но имеет тот недостаток, что рекурсивный вызов немного запутывается: sum(...) становится h(h)(...) - и все.