Как реализовать функцию отложенного отображения карты? - PullRequest
Новая
       59

Как реализовать функцию отложенного отображения карты?

2 голосов
/ 23 ноября 2010

Я пытаюсь реализовать функцию «сокращения карты».То есть он должен возвращать последовательность, состоящую из результата применения f к первым двум элементам coll, за которым следует результат применения f к этому результату и третьего элемента в coll и т. Д.

(def c [[0 0 0 0] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1]])

(defn- sum-vector [v1 v2]
  (map + v1 v2))

(defn reduce-map [f coll & acc]
  (if (< (count coll) 2)
    (if (empty? acc) coll acc)
    (let [head (apply f (take 2 coll))
          tail (drop 2 coll)]
      (recur f (conj tail head) (conj acc head)))))

Например, вызов этой функции следующим образом: 

(reduce-map sum-vector c)

должен вернуть: 

[[1 0 0 0] [1 1 0 0] [1 1 1 0] [1 1 1 1]]

(На самом деле, он, вероятно, должен вернуть первый элемент без измененийтакже, чтобы лучше подражать map, но я могу исправить это позже.)

Правильно, теперь, это - то, что это возвращает: 

((1 1 1 1) (1 1 1 0) (1 1 0 0) (1 0 0 0))

Как я "push "в конце (ny) seq?

Если я заменим reduce-map на recur, это то, что он возвращает: 

(((1 1 1 1) ((1 1 1 0) ((1 1 0 0) ((1 0 0 0))))))

В чем разница между recur и истинной рекурсией в моем коде выше?

И, есть ли встроенный, или лучший, или более идиоматический, способ реализации reduce-map?

Наконец, я бы хотел, чтобы последовательность вывода была ленивой.Я просто заверну все это в lazy-seq?

1 Ответ

10 голосов
/ 23 ноября 2010

Это звучит немного похоже на reductions.

Что касается «нажатия» в конце seq: в общем случае у seqs нет «конца», ср.(iterate inc 0).

Что касается «толкания» в конце списка: списки не предназначены для этого.Используйте вектор.Заполните свой аккумулятор [], а не nil.

Что касается lazy-seq: используйте "истинную" рекурсию вместо recur.Вот пример: 

(defn integer-seq
  [start]
  (lazy-seq
    (cons start (integer-seq (inc start)))))
...