Ленивые фибоначчи в Ruby

Я могу написать ленивый фибоначчи в Clojure следующим образом:

(def fib (lazy-cat [1 1] (map +' fib (rest fib))))

и я пытаюсь (безуспешно) написать это на Ruby следующим образом:

fib = Enumerator.new do |yielder|
  yielder << 1 << 1
  fib.zip(fib.drop(1)).map do |a,b|
    yielder << (a + b)
  end
end

В упрощенном случае это работает:

fib = Enumerator.new do |yielder|
  yielder << 1 << 1
  puts "here"
end
puts fib.take(2).inspect
puts fib.drop(1).take(1).inspect

но это не так:

fib = Enumerator.new do |yielder|
  yielder << 1 << 1
  puts "here"
  fib.drop(1)
end
puts fib.take(2).inspect
puts fib.drop(1).take(1).inspect

Почему последний пример выдает ошибку SystemStackError: stack level too deep?


ruby clojure lazy-sequences fibonacci
person bmaddy    schedule 03.10.2014    source источник
comment
drop — это функция на основе перечислителя. Попробуйте получить доступ к элементу внутри перечислителя олдскульным способом, по индексу.   -  person Aleksei Matiushkin    schedule 03.10.2014

Ответы (1)


arrow_upward
4
arrow_downward

Во-первых, fib в версии ruby ​​не эквивалентна версии clojure. В версии clojure это функция.

И Enumerable#zip, Enumerable#drop и Enumerable.take не являются ленивыми, если вы явно не укажете это. Если вы не вызываете Enumerable#lazy, они возвращают массив ( жадно потребляя все предметы; вызвать исключение).

def fib
  Enumerator.new do |yielder|
    yielder << 1 << 1
    fib.lazy.zip(fib.lazy.drop(1)).each do |a,b|
      yielder << a + b
    end
  end
end

fib.take(2)
# => [1, 1]
fib.lazy.drop(1).take(1).to_a  # Note: `lazy`, `to_a`.
# => [1]
fib.take(4)
# => [1, 1, 2, 3]
person falsetru    schedule 03.10.2014
comment
Ничего себе, меня удивляет, что вам нужно использовать .lazy там. Приведенный выше код Clojure создает переменную и используется следующим образом: (take 2 (drop 1 fib)). Функция будет создана с помощью defn. Спасибо за ответ - именно то, что я искал! - person bmaddy; 03.10.2014
comment
Может быть, предупреждение о неэффективности было бы хорошо. У меня уже fib.take(20) вылетает с can't create fiber (FiberError). Кстати, я пришел сюда из нового вопроса, используя это. - person Stefan Pochmann; 29.01.2018