Как реализовать карту с помощью сокращения в Clojure

В книге Clojure for the Brave and True в конце раздела, посвященного reduce, есть проблема:

Если вам нужно упражнение, которое действительно сдует волосы назад, попробуйте реализовать map с помощью reduce.

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

(defn map-as-reduce
  [f coll]
  (reduce #(cons (f %2) %1) '() (reverse coll)))

Это лучший способ сделать это? Меня особенно расстраивает тот факт, что я должен перевернуть входную коллекцию, чтобы это работало правильно. Выглядит как-то неэлегантно!


clojure map-function
person mluisbrown    schedule 13.05.2016    source источник

Ответы (6)


arrow_upward
12
arrow_downward

Помните, что вы можете эффективно вставить в конец вектора:

(defn map' [f coll]
  (reduce #(conj %1 (f %2)) [] coll))

Пример:

(map' inc [1 2 3])
;=> [2 3 4]

Одно различие между этим map' и исходным map заключается в том, что исходный map возвращает ISeq, а не только Seqable:

(seq? (map inc [1 2 3]))
;=> true

(seq? (map' inc [1 2 3]))
;=> false

Вы можете исправить это, составив приведенную выше реализацию map' с seq:

(defn map' [f coll]
  (seq (reduce #(conj %1 (f %2)) [] coll)))

Теперь самое важное отличие заключается в том, что исходный map ленив, а этот map' нетерпелив, потому что reduce нетерпелив.

person Sam Estep    schedule 13.05.2016

arrow_upward
11
arrow_downward

просто для удовольствия: карта действительно принимает более одной коллекции в качестве аргумента. Вот расширенная реализация:

(defn map-with-reduce
  ([f coll] (seq (reduce #(conj %1 (f %2)) [] coll)))
  ([f coll & colls]
    (let [colls (cons coll colls)]
      (map-with-reduce (partial apply f)
                       (partition (count colls) 
                                  (apply interleave colls))))))

в ответ:

user> (map-with-reduce inc [1 2 3])
(2 3 4)

user> (map-with-reduce + [1 2 3] [4 5] [6 7 8])
(11 14)
person leetwinski    schedule 13.05.2016

arrow_upward
7
arrow_downward

Настоящая карта вызывает seq для своего аргумента (аргументов) коллекции и возвращает ленивую последовательность, так что, может быть, это для того, чтобы немного приблизить ее к реальной карте?

(defn my-map
  [f coll]
  (lazy-seq (reduce #(conj %1 (f %2)) [] (seq coll))))

Я бы добавил это как комментарий, но у меня нет репутации. :)

person Enrique Montalvo    schedule 31.05.2016

arrow_upward
2
arrow_downward

Вы можете использовать conj для добавления к вектору вместо добавления к списку:

(defn my-map [f coll]
  (reduce (fn [result item]
              (conj result (f item)))
          [] coll))

(my-map inc [1 2 3]) => [2 3 4]
person Adam Lee    schedule 13.05.2016

arrow_upward
2
arrow_downward

Чаще всего инвертируют результат, а не ввод. Это распространенная идиома при рекурсивной обработке односвязных списков. Он сохраняет линейную сложность с этой структурой данных.

Возможно, вы захотите предложить разные реализации для других seq, например. г., векторы, возможно, основанные на conj вместо cons.

Я бы не стал слишком беспокоиться об элегантности такого рода упражнений.

person Svante    schedule 13.05.2016
comment
Я не понимаю, почему имеет значение реверсирование результата вместо ввода; сложность линейна в любом случае. - person Sam Estep; 13.05.2016
comment
@SamEstep: Да, хорошо. Просто гораздо чаще бывает обратный результат. - person Svante; 13.05.2016
comment
Я не очень понимаю ваш комментарий о предложении других реализаций для других seq; все реализации map на этой странице работают для всех входов Seqable. Если вы хотите в результате создать различные типы последовательностей, я не вижу особого смысла в этом (за исключением, возможно, производительности), когда можно было бы легко составить map с помощью vec или что-то в этом роде. - person Sam Estep; 13.05.2016
comment
@SamEstep: производительность была именно моей точкой зрения. Вам не нужно инвертировать векторы. - person Svante; 13.05.2016

arrow_upward
0
arrow_downward

Как уже указывалось. Вам не нужно реверсировать ввод. cons добавляет элемент в начало последовательности (даже в векторах), тогда как conj всегда добавляет наиболее естественным способом, он всегда добавляет элемент самым быстрым способом для коллекции. он будет добавлять слева направо для списка и слева направо для векторов.

Я заметил, что в большинстве предлагаемых ответов используется «уменьшить», поэтому позвольте мне предложить этот, используя в основном рекурсию:

(defn my-map [f coll]
 (loop [f f coll coll acc []]
   (if (empty? coll)
     acc
     (recur f (rest coll) (conj acc (f (first coll)))))))
person Lewix    schedule 13.05.2016
comment
В вопросе конкретно упоминается использование reduce, поэтому, хотя этот ответ и интересен, он никоим образом не отвечает на вопрос. - person mluisbrown; 19.05.2016
comment
@mluisbrown это правда. Я, должно быть, пропустил, что в нем специально указано использовать «уменьшить» - person Lewix; 20.05.2016