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

Взяв три приведенные ниже функции, реализованные в Haskell и Clojure соответственно:

f :: [Int] -> Int
f = foldl1 (+) . map (*7) . filter even

(defn f [coll]
  ((comp
    (partial reduce +)
    (partial map #(* 7 %)
    (partial filter even?)) coll))

(defn f [coll]
  (transduce
    (comp
      (filter even?)
      (map #(* 7 %)))
     + coll))

когда они применяются к списку типа [1, 2, 3, 4, 5], все они возвращают 42. Я знаю, что механизмы, лежащие в основе первых двух, аналогичны, поскольку map ленив в Clojure, но третий использует преобразователи. Может ли кто-нибудь показать промежуточные шаги для выполнения этих функций?


person Fuad Saud    schedule 04.09.2016    source источник
comment
Я не думаю, что reduce является стандартной функцией Haskell. Хотя я полагаю, вы, вероятно, имеете в виду один из foldr1 или foldl1< /а>.   -  person Alec    schedule 04.09.2016
comment
Вы правы, я их перепутал.   -  person Fuad Saud    schedule 04.09.2016
comment
В зависимости от того, компилируете ли вы с оптимизацией или нет, первый подвергается слиянию потоков, поэтому он почти наверняка будет работать как один замкнутый цикл (без дополнительных промежуточных распределений). Я считаю, что преобразователи дают вам аналогичные (если не такие мощные / без накладных расходов) преимущества, поэтому третий пример должен работать примерно так же, как первый. С другой стороны, второй почти наверняка гораздо менее эффективен - вы в конечном итоге создадите промежуточные списки, которые в любом случае будут немедленно собраны мусором.   -  person Alec    schedule 04.09.2016
comment
Итак, я знал, что Haskell ведет себя так по умолчанию, но я не знал, что это называется слиянием потоков. Это хорошо знать. На самом деле я думал, что Clojure ведет себя так же, но, похоже, я ошибался? В любом случае, можно ли сказать: 1-й и 3-й — O(n), а 2-й — O(3n)?   -  person Fuad Saud    schedule 04.09.2016
comment
Ну, я бы не был так уверен в этом... преимущества и недостатки заключаются в космической сложности. Таким образом, выигрыш во времени можно наблюдать через время, которое занимает сборка мусора, что на самом деле не так уж предсказуемо.   -  person Alec    schedule 04.09.2016
comment
Вы неправильно используете обозначение большого O. Сбор мусора, безусловно, является одной из проблем; другой — использование кеша. Если вы создадите гигантский список, большая его часть выпадет из кеша, прежде чем вы будете готовы начать следующее преобразование. @ Алек, это форма короткой вырубки лесов, называемая слиянием папок и сборок. Слияние потоков обычно относится к другой технике с аналогичными целями.   -  person dfeuer    schedule 04.09.2016
comment
@FuadSaud Любая функция O(n) равна O(kn) для каждого k положительного натурального числа, поэтому между O(n) и O(3n) или O(1000n) нулевое различие. Если вы хотите сказать, что код X выполняет ровно n вычислительных шагов/распределения памяти/все, что вы хотите измерить, вы должны сказать, что код X имеет сложность n (или n+k, если хотите), а код Y имеет сложность 3n+k, где обе функции принадлежат множеству O(n), которое является тем же набором функций, что и O(3n) и O(kn) для каждого положительного k.   -  person Bakuriu    schedule 04.09.2016
comment
@dfeuer Спасибо за исправление! Где на самом деле используется потоковое слияние? В этом документе я подумал, что он применяется к спискам для GHC. Также есть это статья, в которой говорится о vector, но теперь я ни в чем не уверен! Я должен буду на самом деле прочитать источник!   -  person Alec    schedule 04.09.2016
comment
@ Алек, пакет vector - самый большой, о котором я знаю, который, к сожалению, сильно усложнен различными факторами, но я думаю, что есть еще один пакет под названием stream-fusion или что-то в этом роде.   -  person dfeuer    schedule 04.09.2016
comment
@Bakuriu спасибо за поправку, это я и хотел донести   -  person Fuad Saud    schedule 04.09.2016
comment
@dfeuer IIRC stream-fusion буквально является реализацией первой статьи по слиянию потоков, на которую я ссылался выше. И этот пакет не обновлялся с 2013 года. :S Кроме того, немного не по теме, но я только что понял, что вы тот человек, который может спросить об этом: есть ли какая-либо литература/документация по методам слияния в containers?   -  person Alec    schedule 04.09.2016
comment
@ Алек, я не думаю, что есть какая-либо документация, и я не разбираюсь в литературе. containers не имеет какой-либо общей структуры слияния; он просто реализует несколько простых законов слияния, таких как map/map, traverse/map, map/reverse и т. д. Если вам нужно больше, дайте мне знать на GitHub.   -  person dfeuer    schedule 04.09.2016


Ответы (1)


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

Версии преобразователя карты и фильтра определяются с использованием той же основной функциональности, что и версии без преобразователя, за исключением того, что они «сопрягаются» (или нет, в случае фильтра) с потоком результатов. определен в другом месте. Действительно, если вы посмотрите на источник карты, там есть явные функции построения структуры данных, в то время как вариант преобразователя не использует такие функции — они передаются через rf. Явное использование cons в версиях без преобразователя означает, что они всегда будет иметь дело с последовательностями

ИМО, основное преимущество использования преобразователей заключается в том, что у вас есть возможность определить процесс, который вы выполняете, помимо того, что будет использовать ваш процесс. Поэтому, возможно, более интересным переписыванием вашего третьего примера может быть:

(def process (comp (filter even)
                   (map #(* 7 %))))

(defn f [coll] (transduce process + collection))

Это упражнение для автора приложения, чтобы решить, когда такая абстракция необходима, но она определенно может открыть возможность для повторного использования.


Вам может прийти в голову, что вы можете просто переписать

(defn process [coll]
  ((comp
    (partial map #(* 7 %)
    (partial filter even?)) coll))

(reduce + (process coll))

И получить тот же эффект; это верно. Если ваш ввод всегда представляет собой последовательность (или всегда один и тот же тип потока / вы знаете, какой это будет поток), возможно, нет веской причины для создания преобразователя. Но здесь можно продемонстрировать силу повторного использования (предположим, что процесс — это преобразователь).

(chan 1 process)  ;; an async channel which runs process on all inputs

(into [] process coll)  ;; writing to a vector

(transduce + process coll)  ;; your goal

Мотивация преобразователей заключалась в том, чтобы перестать писать новые функции сбора для разных типов сбора. Рич Хикки упоминает о своем разочаровании в написании таких функций, как map‹ map> mapcat‹ mapcat> и т. д. в основной асинхронной библиотеке — что map и mapcat являются, уже определено. , но так как они предполагают, что работают с последовательностями (явные cons, о которых я упоминал выше), их нельзя применять к асинхронным каналам. Но каналы могут предоставлять свои собственные rf в версии преобразователя, чтобы позволить им повторно использовать эти функции.

person matrix10657    schedule 04.09.2016