Реальный мир Haskell книга - асимптотическая сложность примера монады Logger - PullRequest
Новая
       12

Реальный мир Haskell книга - асимптотическая сложность примера монады Logger

3 голосов
/ 12 апреля 2011

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

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

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

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

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

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

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

Ответы [ 3 ]

5 голосов
/ 12 апреля 2011

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

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

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

2 голосов
/ 12 апреля 2011

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

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

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

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

, тогда сложность является квадратичной.Это просто «переадресация» свойств лежащего в основе моноида, здесь [],(++).

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

1 голос
/ 12 апреля 2011

Для сравнения, пакет библиотеки монад на платформе Haskell "mtl" получает Writer из пакетов "трансформеры". Реализация Writer для всех типов моноидов находится в источнике около здесь . Экземпляр использует 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
...