← All posts tagged log

fmap
log

Прийдумал список на продолжениях с snoc'ом за не аммортизированный O(1). head/tail/cons стоят также. Интересно, получится ли придумать такую структуру чтобы init/tail тоже стоял O(1), как в языках с мутабельностью, но при этом чтобы структура оставалась персистентной. Похоже это невозможно, но надо понять почему.

fmap

Второй день продолжаются такие глупые попытки как перехитрить природу и написать претти принтер на функторах. По-хорошему принтер это: 
newtype P doc a = P { runP :: a -> doc }; но это контравариантный функтор. Если немного порисовать стрелочки, то можно заметить что выкрутиться можно представив принтер как отношение, добавив недостающую стрелку в обратную сторону. В свою очередь, отношение можно представить как [(a, doc)], то есть получаем: 
newtype P doc a = P { runP :: [(a, doc)] }; теперь все хорошо, есть также необходимые инстансы для Applicative и Alternative, которые можно взять, вообще говоря, из mtl, так как второй вариант есть (WriterT Doc (ListT m) a). За исключением одного очевидного недостатка -- длинна итогового списка; самый неприятный, можно сказать взрыв, происходит в (<*>), ведь length (a <*> b) = length a * length b. Ну и length (a <|> b) = length a + length b, что тоже как-бы.
Inspired by "Invertible Syntax Descriptions: Unifing Parsing and Pretty Printing" хочется все-таки как-то сделать, не смотря на то, что похоже, это невозможно. (Надо наверно попытаться сделать HOAS и свой Doc, может тогда что-то получится)