Целочисленное переполнение с использованием ленивых последовательностей в Clojure

Я только учусь использовать ленивые последовательности в Clojure, и я не уверен, что я делаю неправильно в следующем коде:

(defn sum [seqn]
  (reduce + seqn))

(defn fib
  ([] (concat [0 1] (fib 0 1)))
  ([a b] (lazy-seq (cons (+ a b) (fib b (+ a b))))))

(defn up-to [n seqn]
  (filter (fn [x] (< x n)) seqn))

(sum (up-to 100 (fib))) => ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)

Суммируемые числа не должны быть больше 100, так что же вызывает целочисленное переполнение?


clojure lazy-evaluation integer-overflow
person Chetan    schedule 25.06.2012    source источник
comment
Я столкнулся с этой проблемой, пытаясь решить ту же проблему: Project Euler, проблема номер 2!   -  person Geoffrey    schedule 03.08.2015

Ответы (2)


arrow_upward
5
arrow_downward

Фильтрация бесконечной последовательности создает бесконечную последовательность, а уменьшение по ней приводит к тому, что фильтр продолжает искать другой соответствующий элемент даже после того, как предикат перестает возвращать значение true.

Замените filter на take-while. Бесконечная последовательность, сгенерированная (fib), приведет к тому, что filter будет работать вечно, но перед этим он сломается из-за ArithmeticException, с которым вы столкнулись. take-while остановит дальнейшую оценку списка после того, как предикат (fn [x] (< x n)) станет ложным.

(defn up-to [n seqn]
  (take-while (fn [x] (< x n)) seqn))

(sum (up-to 100 (fib))) ;; => 232
person Jan    schedule 25.06.2012
comment
Как фильтр оценивает весь список? Я думал, что он должен был производить ленивую последовательность? - person Alex; 26.06.2012
comment
Ничего, я вижу... дело не в самом фильтре. Фильтрация бесконечной последовательности дает бесконечную последовательность, а уменьшение по ней приводит к тому, что фильтр продолжает искать другой соответствующий элемент даже после того, как предикат перестает возвращать значение true. - person Alex; 26.06.2012
comment
Понял, кажется, рассуждения Алекса более точны, чем ответы. Пожалуйста, обновите ответ, чтобы я мог отметить его как правильный. - person Chetan; 26.06.2012
comment
Четан, готово. Сейчас режет? @Alex, спасибо за ваши комментарии. - person Jan; 26.06.2012
comment
Хороший способ понять разницу между «бери-пока» и «фильтруй». - person Geoffrey; 03.08.2015

arrow_upward
5
arrow_downward

начиная с clojure 1.3.0 числа не повышаются автоматически до bigInt/bigDecimal.

чтобы исправить это, используйте +' вместо этого

ваше 100-е число Фибиначи слишком велико для целого числа

user> (nth (fib) 100)
354224848179261915075N
person Arthur Ulfeldt    schedule 25.06.2012
comment
Я не думаю, что он суммирует первые 100 чисел Фибоначчи, но числа Фибоначчи, которые меньше 100. - person Ben Voigt; 26.06.2012
comment
да, это отдельный ответ для другой проблемы, отличной от той, о которой говорится в ответе Яна. - person Arthur Ulfeldt; 26.06.2012