Треугольник ленивого Паскаля в Clojure

Я пытаюсь написать краткий, ленивый треугольник Паскаля в Clojure, повернутый так, что строки/столбцы следуют диагоналям треугольника. То есть я хочу создать следующую ленивую последовательность ленивых последовательностей:

((1 1 1 1 ...)
 (1 2 3 4 ...)
 (1 3 6 10 ...)
 ...
 )

Код, который я написал:

(def pascal
  (cons (repeat 1)
        (lazy-seq
          (map #(map + %1 %2)
               (map #(cons 0 %) (rest pascal)))
               pascal
          )))

так что каждая строка формируется путем добавления сдвинутой вправо версии самой себя к предыдущей строке. Проблема в том, что он никогда не проходит дальше первой строки, так как в этой точке (map #(cons 0 %) (rest pascal))) пусто.

=> (take 5 (map #(take 5 %) pascal))
((1 1 1 1 1))

Какой разумный способ решить эту проблему? Я довольно новичок в программировании на Clojure и совсем другом способе мышления о проблеме, с которой он связан, поэтому я был бы очень признателен за предложения от любого, кто более опытен в этом.


clojure lazy-evaluation pascals-triangle
person Luke Hewitt    schedule 09.03.2013    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Кратко и лениво

(def pascal (iterate (partial reductions +') (repeat 1)))

(map (partial take 5) (take 5 pascal))
;=> ((1 1 1 1 1) 
;    (1 2 3 4 5) 
;    (1 3 6 10 15) 
;    (1 4 10 20 35) 
;    (1 5 15 35 70))

Но слишком ленивы?

(take 5 (nth pascal 10000))
;=> StackOverflowError

Попробуй снова

(take 5 (nth pascal 10000))
;=> (0)

О-о, начни сначала и попробуй, попробуй еще раз

(def pascal (iterate (partial reductions +') (repeat 1)))
(count (flatten (map (partial take 5) (take 100000 pascal))))
;=> 500000

Теперь это все в твоей куче

(take 5 (nth pascal 100000))
;=> (1 100001 5000150001 166676666850001 4167083347916875001)
person A. Webb    schedule 09.03.2013
comment
+1. Знаете ли вы, почему второй вызов (take 5 (nth pascal 10000)) дает результат, отличный от первого? StackOverFlowError как-то нарушает последовательность? Кроме того, у вас есть символ ' после +, который, я думаю, вам не нужен. - person OpenSauce; 12.03.2013
comment
@OpenSauce Точно, это демонстрирует вызов только в первый раз и поведение результатов кэширования ленивой последовательности. То, что сгенерировало это исключение, больше не будет вызываться, а поскольку исключение было обработано REPL, фиктивный результат кэшируется. +' автоматически повышает уровень до BigInt, когда это необходимо. Если бы я взял 6 вместо 5, это было бы показано. - person A. Webb; 12.03.2013

arrow_upward
2
arrow_downward

pascal должен быть не переменной, а функцией, которая генерирует бесконечные последовательности.

Проверьте этот вопрос для использования в lazy-seq

Кстати, попробуйте это:

(defn gennext [s sum]
  (let [newsum (+ (first s) sum)]
    (cons newsum
          (lazy-seq (gennext (rest s) newsum)))))

(defn pascal [s]
  (cons s
        (lazy-seq (pascal (gennext s 0)))))

введите здесь описание изображения

(pascal (повторить 1)) дает вам исключение целочисленного переполнения, но это означает, что он создает бесконечные последовательности. Вы можете использовать +', чтобы использовать большое целое число.

person yehe    schedule 09.03.2013
comment
@А. Код Уэбба лучше, он использует редукции, которых я не знаю. - person yehe; 09.03.2013
comment
Ваше объяснение, вероятно, более полезно для ОП :). Но я бы не стал использовать seq в качестве символа привязки, так как это уже широко используемая функция. - person A. Webb; 09.03.2013