רקורסיה - ג'אווהסקריפט: פונקציה אנונימית רקורסיבית?

נאמר שיש לי פונקציה רקורסיבית בסיסית:

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();
})();

הייתי רוצה דרך לקרוא לפונקציה שקראה לפונקציה הזו... ראיתי סקריפטים איפשהו (לא זכור לי איפה) שיכולים לומר לך את השם של הפונקציה שנקראה, אבל כרגע אני לא מצליח להזכר בכל המידע הזה.

תשובה #1

אתה יכול לתת לפונקציה שם, גם כאשר אתה יוצר את הפונקציה כערך ולא כהצהרת "function". במילים אחרות:

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

היא פונקציה רקורסיבית שמפוצצת את המחסנית. עכשיו, עם זאת, ייתכן שתרצה לא לעשות זאת באופן כללי כי יש כמה בעיות מוזרות עם מימושים שונים של Javascript. (הערה — זהו תגובה די ישנה; חלק/רוב/כל הבעיות שמתוארות בפוסט הבלוג של Kangax עשויות להיות מתוקנות בדפדפנים מודרניים יותר.)

כאשר אתה נותן שם כזה, השם אינו נראה מחוץ לפונקציה (ובכן, הוא לא אמור להיות; זו אחת מהמוזרויות). זה כמו "letrec" ב-Lisp.

לגבי arguments.callee, זה אסור במצב "strict" ובכלל נחשב לדבר רע, כי זה מקשה על כמה אופטימיזציות. זה גם הרבה יותר איטי ממה שאפשר לצפות.

ערוך — אם ברצונך לקבל את האפקט של פונקציה "אנונימית" שיכולה לקרוא לעצמה, תוכל לעשות משהו כזה (בהנחה שאתה מעביר את הפונקציה כקולבק או משהו כזה):

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

מה שזה עושה הוא מגדיר פונקציה עם הצהרת פונקציה declaration נחמדה, בטוחה, שלא נשברת ב-IE, ויוצר פונקציה מקומית ששמה לא יזהם את המרחב השם הגלובלי. פונקציית העטיפה (אנונימית באמת) פשוט מחזירה את הפונקציה המקומית הזו.

תשובה #2

קומבינטור U

על ידי מסירת פונקציה לעצמה כארגומנט, פונקציה יכולה לחזור על עצמה תוך שימוש בפרמטר שלה במקום בשמה! לכן, הפונקציה שניתנת ל-U צריכה שיהיה לה לפחות פרמטר אחד שיקושר לפונקציה (לעצמה).

בדוגמה למטה, אין לנו תנאי יציאה, אז פשוט נסתובב לנצח עד שיקרה Overflow בערימה

const U = f => f (f) // call function f with itself as an argument

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 loop (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 (x => Y (f) (x))

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

עכשיו נראה איך השימוש בו משתווה ל-U-combinator. שימו לב, כדי לבצע רקורסיה, במקום 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

כמו שאתם יכולים לראות, f הופך למנגנון של הרקורסיה עצמה. כדי לבצע רקורסיה, אנו קוראים לו כמו פונקציה רגילה. אנו יכולים לקרוא לו מספר פעמים עם ארגומנטים שונים והתוצאה עדיין תהיה נכונה. ומכיוון שהוא פרמטר של פונקציה רגילה, אנו יכולים לקרוא לו כל שם שנרצה, כמו recur למטה -

const U = f => f (f)

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

const fibonacci = Y (recur => n =>
  n < 2 ? n : recur (n - 1) +  (n - 2))

console.log (fibonacci (10)) // 55

U ו-Y קומבינטור עם יותר מפרמטר אחד

בדוגמאות למעלה, ראינו כיצד אנו יכולים לבצע לולאה ולהעביר ארגומנט כדי לעקוב אחרי ה"מצב" של החישוב שלנו. אבל מה אם אנחנו צריכים לעקוב אחרי מצב נוסף?

אנחנו יכולים להשתמש בנתונים מורכבים כמו מערך או משהו כזה...

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) כדי לקבל את התשובה שאנחנו רוצים.

באמצעות מה שאנו יודעים על פונקציות מותאמות (רצפים של פונקציות יונריות (עם פרמטר אחד)), אנו יכולים להשיג את מטרתנו בקלות מבלי שצריך לשנות את ההגדרה שלנו של Y או להסתמך על נתונים מורכבים או תכונות מתקדמות של השפה.

הסתכלו על ההגדרה של fibonacci מקרוב למטה. אנחנו מייד מיישמים את 0 ו-1 שקושרים ל-a ו-b בהתאמה. עכשיו fibonacci פשוט מחכה שהארגומנט האחרון יסופק, שיהיה קשור ל-x. כשאנחנו מבצעים קריאה רקורסיבית, עלינו לקרוא ל-f (a) (b) (x) (ולא ל-f (a,b,x)) כי הפונקציה שלנו נמצאת בצורה curried.

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 ]

הכל אנונימי אוי אלוהים

מכיוון שאנחנו עובדים עם פונקציות טהורות כאן, אנחנו יכולים להחליף כל פונקציה עם שם בהגדרתה. שימו לב מה קורה כשאנחנו לוקחים את הפונקציה fibonacci ומחליפים פונקציות עם שם בביטויים שלהן

/* 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 => h (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) מחושב רקורסיבית באמצעות שום דבר מלבד פונקציות אנונימיות

תשובה #3

אנשים דיברו על 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();
  }
})());

הדבר החשוב ביותר לציין לגבי הפתרון הזה הוא שאסור לך להשתמש בו.

תשובה #4

ייתכן שהכי פשוט להשתמש ב״אובייקט אנונימי״ במקום:

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

המרחב הגלובלי שלך נקי לחלוטין מזיהום. זה די פשוט. ואתה יכול לנצל בקלות את המצב הלא-גלובלי של האובייקט.

אתה גם יכול להשתמש בשיטות של אובייקטים ב-ES6 כדי להפוך את התחביר ליותר תמציתי.

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

תשובה #5

אני לא הייתי עושה זאת כפונקציה מקוונת. זה דוחף נגד גבולות הטעם הטוב ולא באמת נותן לך שום דבר.

אם אתה באמת חייב, יש arguments.callee כפי שמופיע בתשובתו של פבריציו. עם זאת, זה נחשב בדרך כלל לבלתי רצוי ואסור במצב 'strict' של גרסת ECMAScript החמישית. אף על פי ש-ECMA 3 ומצב שאינו strict לא נעלמים, עבודה במצב strict מבטיחה יותר אפשרויות לאופטימיזציות בשפה.

ניתן גם להשתמש בפונקציה מובנית עם שם:

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

עם זאת, גם ביטויים של פונקציות מוכללים עם שם עדיף להימנע מהם, מכיוון ש-JScript של IE עושה כמה דברים רעים להם. בדוגמה שלמעלה, foo מזהם בטעות את התחום ההורה ב-IE, וה-foo ההורה הוא מופע נפרד מה-foo שנראה בתוך foo.

מה המטרה של לשים את זה בפונקציה אנונימית מקוונת? אם אתה פשוט רוצה להימנע מזיהום של הסקופ ההורה, אתה כמובן יכול להחביא את הדוגמה הראשונה שלך בתוך פונקציה אנונימית אחרת שקוראת לעצמה (מרחב שמות). האם באמת צריך ליצור עותק חדש של nothing בכל סבב של הרקורסיה? ייתכן שיהיה לך טוב יותר עם מרחב שמות שמכיל שתי פונקציות פשוטות רקורסיביות הדדית.