Javascript ленивый оценить fibonacci функцию

Question

Я спросил a question прежде чем использовать ленивую оценку в Scala. Я пытался написать следующую функцию Haskell в Scala:

fib a b = c : (fib b c) 
    where c = a+b 

Ответ на этот вопрос в том, что я не мог использовать списки, а должны использовать потоки. Теперь я пытаюсь сделать то же самое в Javascript. Я перевел эту функцию, и попробовал его на this site:

function fib(a,b) { 
    c = a+b; 
    return [c] + fib(b,c); 
} 

var res = fib(0,1).slice(0,10); 

console.log(res); 

Но я получаю следующее сообщение об ошибке:

RangeError: Maximum call stack size exceeded 

ли Javascript иметь способ сделать это?

Answer 1

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

var fib = function (a, b) { 
    var c = a + b 
    return { "this": c, "next": function() { return fib(b, c) } } 
} 

Такое, что

> var x = fib(1,1) 
> x.this 
2 
> x = x.next() 
> x.this 
3 

В каком-то смысле это точный перевод *, где мой обратный объект представляет один Haskell (:) «против» клетки. Отсюда было бы относительно легко написать функцию «взять», чтобы преобразовать этот ленивый список javascript в строковый массив javascript.

Вот одна из версий.

var take = function(n, cons) { 

    var res = [] 
    var mem = cons 

    for (var i = 0; i < n; i++) { 
     res.push(mem.this) 
     mem = mem.next() 
    } 

    return res 
} 

Такое, что

> take(10, fib(1,1)) 
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144] 

(*) Технически даже значение "this" должно быть завернуто в стуке, но я взял лобовое строгое понятие списков, которые, как правило, довольно близко к интуиции каждого ,

Answer 2

Не совсем Haskell ленивая оценка, но вы можете сделать что-то подобное с currying.

function fib(a,b) { 
    var first = true; 

    return function(n) { 
     if (!isFinite(n) || n < 0) 
      throw "Invalid argument"; 

     var result = first ? [a,b] : []; 
     first = false; 

     for (var i = result.length; i < n; i++) 
      result.push(b = a+(a=b)); 

     return result; 
    }; 
} 

---

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

var f = fib(0,1); // Initialize the sequence with starting values 

// Invoke the resulting function with the number of results you want 
console.log(f(10)); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] 

console.log(f(4)); // [55, 89, 144, 233] 

console.log(f(4)); // [377, 610, 987, 1597] 

Answer 3

ES6 имеет generator functions вы можете использовать его для ленивых оценки (в сочетании с destructuring assignment operator) Используя эту технику, мы можем написать функцию, как Фибоначчи ниже (только еще один способ сделать это).

var fib_generator = function *(){ 
 
    var current = 0, next = 1; 
 
    while(true) 
 
    { 
 
    [next, current] = [next+current, next]; 
 
    yield current; 
 
    } 
 
} 
 

 
var fib = fib_generator(); 
 

 

 
// below is the sample code prints values uptill 55 
 
for(var i=0; i<10; i++) 
 
{ 
 
    console.log(fib.next().value); 
 
}