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

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

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

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

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