В чем разница между функцией Clojure (nth [индекс колла]) и композицией (последняя (взять колл индекса)) - PullRequest
Новая
       55

В чем разница между функцией Clojure (nth [индекс колла]) и композицией (последняя (взять колл индекса))

12 голосов
/ 15 декабря 2011

Я пытаюсь проработать книгу Стюарта Хэллоуэя «Программирование Clojure». Весь этот функциональный материал очень новый для меня.

Я понимаю, как 

(defn fibo[]
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

генерирует последовательность Фибоначчи лениво. Я не понимаю, почему 

(last (take 1000000 (fibo)))

работает, а 

(nth (fibo) 1000000)

выдает ошибку OutOfMemoryError. Может кто-нибудь объяснить, как эти два выражения отличаются? (Nth) как-то держится за начало последовательности?

Спасибо!

Ответы [ 3 ]

4 голосов
/ 15 декабря 2011

Я думаю, что вы говорите о проблеме, которая обсуждалась в группе Google , и Рич Хики предоставил патч , который решил эту проблему.И книга, которая была опубликована позже, не охватывала эту тему.

В clojure 1.3 ваш пример nth работает с небольшими улучшениями в функции fibo.Теперь, из-за изменений в 1.3, мы должны явно пометить M для использования произвольной точности, или он падает с throwIntOverflow. 

(defn fibo[]
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0M 1M])))

И с этими изменениями 

(nth (fibo) 1000000)

успешно (если у вас достаточно памяти)

1 голос
/ 15 декабря 2011

Какую версию Clojure вы используете?Попробуйте (clojure-version) на репл.Я получаю одинаковые результаты для обоих выражений в 1.3.0, а именно переполнение целых чисел.

Для 

(defn fibo[]
    (map first (iterate (fn [[a b]] [b (+ a b)]) [(bigint 0) 1])))

Я получаю правильные результаты для обоих выражений (действительно большое целое число ...)

0 голосов
/ 15 декабря 2011

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

Глядя на исходный код nth в https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java, не похоже, что nth или take сохраняют голову.

Однако nth использует индексацию с нуля, а не счет по номеру элемента. Ваш код с nth выбирает 1000001-й элемент последовательности (тот, который имеет индекс 1000000). Код с take возвращает последний элемент в последовательности 1000000 элементов. Это предмет с индексом 999999. Учитывая, как быстро растет фиб, последним может быть тот, который сломал спину верблюду.

Кроме того, я проверял источник 1.3.0. Возможно, более ранние версии имели разные реализации. Чтобы заставить ваше fibo работать должным образом в 1.3.0, вам нужно использовать арифметические функции, которые будут переводить числа в bignums: 

(defn fibo[]
    (map first (iterate (fn [[a b]] [b (+' a b)]) [0 1])))
...