Насколько эффективна писательская монада для списков? - PullRequest
Новая
       36

Насколько эффективна писательская монада для списков?

0 голосов
/ 14 декабря 2018

Реализация монады писателя Haskell в списках (Writer [w] a) будет использовать ++ для добавления элементов.Поэтому, если я напишу этот код в монаде автора списка: 

do
  tell [a, b, c]
  tell [d]

Списки будут добавлены с [a, b, c] ++ [d].После работы в OCaml я усвоил, что списки должны создаваться с помощью оператора cons (:) вместо оператора конкатенации (++), поскольку последний является O (n) в первом аргументе.

Моя рабочая нагрузка добавляет одно «сообщение» к монаде писателя за раз, поэтому вторым аргументом ++ обычно будет одноэлементный список.

В Haskell лень сделает монаду составителя списков более эффективной, чем внетерпеливый язык, как OCaml?Если нет, то какой будет эффективная альтернатива моей рабочей нагрузке?

1 Ответ

0 голосов
/ 15 декабря 2018

Связанные слева (++) s неэффективны, потому что крайние левые списки просматриваются несколько раз, по одному для каждого включающего (++).Связанные справа (++) хороши (по крайней мере, их нельзя сделать более эффективными, если использовать (:) напрямую).

Стандартный WriterT преобразователь (и (,) писатель) связывают их вызовы(++) таким же образом, как связаны их привязки.Таким образом, из-за расширения предыдущего обсуждения, (>>=) s, связанные с левой стороной, будут проблематичными, тогда как связанные с правой стороной - это нормально.В частности, это означает, что стоимость абстракции .Если в рефакторинге вытащить первые две строки блока do ниже: 

x = do
    tell a
    tell b
    tell c

в отдельное определение, возможно потому, что они часто встречаются: 

y = do
    tell a
    tell b

x = do
    y
    tell c

Этот рефакторинг повторно связывает одну привязку слева и поэтому стоит немного больше.

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

do
    tell (Endo ([a,b,c]++))
    tell (Endo ([d]++))

Это волшебным образом перекроет ваши (++) с направо (вау! Поражает меня каждый раз, когда я заново выясняю, как это работает).Стоимость состоит в том, что каждое наблюдение в списке различий (то есть преобразование из списка различий в стандартный список) является дорогостоящим (тогда как при предыдущем выборе пустых списков множественные наблюдения стоили не более одного наблюдения).Если у вас есть только один потребитель, скажем, вызов верхнего уровня на runWriterT, который раз и навсегда сгладит список - это не проблема асимптотически, но если вы обнаружите, что звоните listen или pass и проверяетесписок различий часто, вы можете не захотеть выбирать это.

Если ни один из этих компромиссов не звучит для вас хорошо, третий вариант - использование пальчиков, например, Seq, для которых наблюдение бесплатно.(в отличие от списков различий) и конкатенация на обоих концах - это время журнала в более коротком аргументе (в отличие от стандартных списков, где оно является линейным в первом аргументе), но для которых константы достаточно высоки, что вы можете заметить это во многих случаях.

...