Блог

Я только что добрался до главы 14 книги по Хаскеллу в реальном мире и вчера задавался этим вопросом.

В примере монады регистратора функция привязки реализована следующим образом:

 -- (>>=) :: Logger a -> (a -> Logger b) -> Logger b
    m >>= k = let (a, w) = execLogger m
                  n      = k a
                  (b, x) = execLogger n
              in Logger (b, w    x)
  

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

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

Если я ошибаюсь, пожалуйста, помогите предоставить правильный анализ и обозначение big oh.

Если я прав, я надеюсь, что люди, у которых больше опыта / понимания с Haskell и книгой, могут рассказать мне о некоторых причинах выбора этой реализации и почему это нормально. В предыдущей главе книги есть раздел, в котором говорится, что такой способ добавления списка плох, и учит нас технике составления списка различий. Почему это здесь не используется?

Кстати, мне нравится книга, это будет книга, которую я буду читать от корки до корки с давних пор.

Это стандартное (наивное) кодирование монады записи, специализированное для вывода списка. Он работает достаточно хорошо для большинства применений, используя экземпляр monoid для списков:

 instance Monoid [a] where
        mempty  = []
        mappend = (  )
  

Альтернативы с большей сложностью включают логику в dlists или, что еще эффективнее, текстовый моноид или моноид конструктора.

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

 log 0 >> (log 1 >> (log 2 >> log 3))
  

тогда сложность линейна. Однако, если он ассоциируется с левым:

 ((log 0 >> log 1) >> log 2) >> log 3
  

тогда сложность квадратична. Здесь это просто «перенаправление» к свойствам базового моноида [],( ) .

Я полагаю, что причина такого изложения заключается в простоте. Хотя это может быть неэффективно, совершенно очевидно, что происходит. Однако, как отвечали другие, это всего лишь Writer монада над списком monoid. Вы можете получить, Writer заменив [] на mempty и на `mappend` , а затем вы можете создать его с помощью [] or DList или чего угодно, что вы хотите. Таким образом, использование конкретных форм не намного понятнее, IMO.

Для сравнения, пакет библиотеки monad платформы Haskell «mtl» получает Writer из пакетов «transformers». Реализация Writer для всех типов Monoid находится в исходном коде рядом здесь. Экземпляр использует mappend вместо ( ):

 instance (Monoid w, Monad m) => Monad (WriterT w m) where
    return a = WriterT $ return (a, mempty)
    m >>= k  = WriterT $ do
        ~(a, w)  <- runWriterT m
        ~(b, w') <- runWriterT (k a)
        return (b, w `mappend` w')
    fail msg = WriterT $ fail msg