Есть ли какие-либо эмпирические правила о том, когда при создании монад в Haskell можно использовать стиль продолжения-прохождение против против без сожаления.
В качестве примера я собираюсь использовать простую coroutine monad. Если вы никогда не видели этого раньше, вы можете проверить статью "Трубы Coroutine" в Monad.Reader Issue 19 или pipes. Полный код для следующих примеров можно найти в этом репозитории.
-
Normal
Это обычная монада, определяемая как тип данных:
data FooM i o a = Await (i -> FooM i o a) | Yield o (FooM i o a) | Done a
Этот стиль широко используется в экосистеме Хаскелла. Одним из примеров этого стиля является
Proxy
тип данных изpipes
. -
Стиль продолжения-передачи (CPS)
Это похоже на стиль обычный, но каждый конструктор данных стал аргументом для продолжения:
newtype FooCPS i o a = FooCPS { runFooCPS :: forall r. ((i -> FooCPS i o a) -> r) -> (o -> FooCPS i o a -> r) -> (a -> r) -> r }
Этот стиль используется как в attoparsec, так и parsec.
-
Codensity
В этом стиле используется трансформатор монотонности конвертации, обернутый вокруг монады, определенной в стиле обычный. Это дает O (1) лево-ассоциативное связывание.
Трансформатор монодальности с кодировкой выглядит следующим образом:
newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b }
Наша настоящая монада может быть определена как новый тип с использованием трансформатора
Codensity
. Обратите внимание, чтоFooCodensity
используетFooM
внутренне.newtype FooCodensity i o a = FooCodensity { runFooCodensity :: Codensity (FooM i o) a }
-
Отражение без сожаления
Это стиль, обсуждаемый в статье Отражение без сожаления.
Это похоже на стиль обычный, но рекурсивные вызовы стали структурой данных с O (1) добавлением и амортизацией O (1) uncons. Это дает O (1) лево-ассоциативное связывание и монадическое отражение в монаде
FooRWR
:data FooRWR i o a = AwaitRWR (forall x. i -> FooExplicit i o x a) | YieldRWR o (forall x. FooExplicit i o x a) | DoneRWR a
Тип
FooExplicit
определяется как:type FooExplicit i o = FTCQueue (FooRWR i o)
FTCQueue
представляет собой структуру данных с O (1) добавлением и амортизацией O (1) uncons.Этот стиль используется freer-effects и extensible. Он доступен как автономная библиотека в monad-skeleton.
Когда следует использовать нормальный vs CPS vs плотность против отражения без раскаяния? Я предполагаю, что жесткий и быстрый ответ потребует бенчмаркинга данной монады и приложения, но существуют ли какие-либо эмпирические правила?
Из моих собственных исследований я встретил следующие идеи/комментарии:
-
CPS может быть быстрее, чем стиль обычный, потому что вам может не потребоваться анализ case. Хотя фактическое ускорение может варьироваться в зависимости от того, как код компилируется GHC. Codensity и отражение без раскаяния имеют некоторые накладные расходы.
Габриэль Гонсалес (авторpipes
) пишет о том, как он придерживается стиля обычного дляpipes
в this reddit thread и issue в Github.Брайан О'Салливан (автор
attoparsec
) пишет, что изменениеattoparsec
от обычного до CPS дало коэффициент 8 ускорения. В некоторых комментариях к этому сообщению также говорится о нормальном стиле vs CPS. -
Если вам нужны глубокие левые ассоциативные привязки, стиль обычный и CPS заканчивается квадратичным временем выполнения.
Вот пример из статьи "Reflection without Remorse", которая будет демонстрировать квадратичное время выполнения.
data It i a = Get (i -> It i a) | Done a sumInput :: Int -> It Int Int sumInput n = Get (foldl (>=>) return (replicate (n - 1) f)) where f x = get >>= return . (+ x)
Если
sumInput
переписывается с четкостью или отражением без раскаяния, он будет работать очень быстро.Если ваше приложение имеет глубокие лево-ассоциативные привязки, вероятно, вы должны использовать плотность или без сожаления.
Майкл Снойман (автор
conduit
) рассказывает об этом в сообщении в блоге о ускоренииconduit
.Библиотека
pipes
используется для обеспечения трансформатора плотности. -
CPS и . не поддерживают O (1) отражение.
Вот функция, которая требует монадического отражения. Этот пример адаптирован из документа "Reflection without Remorse":
data It i a = Get (i -> It i a) | Done a par :: It i a -> It i b -> It i (It i a, It i b) par l r | Done <- l = Done (l, r) | Done <- r = Done (l, r) | Get f <- l, Get g <- r = Get Done >>= \x -> par (f x) (g x)
Этот метод не может быть записан в стиле CPS или с четностью без предварительного преобразования в стиль обычный. Стиль отражения без сожаления не имеет этой проблемы.
Если вам требуется монадическое отражение, вы, вероятно, должны использовать стиль нормальный или без раскаяния.
-
Отражение без раскаяния добавляет некоторые служебные данные, но это единственный стиль, который дает как лево-ассоциативную привязку, так и отражение O (1).
бонусный вопрос: аналогичный вопрос можно задать о Free
(обычный) vs F
( CPS) из free. Когда следует использовать Free
? Когда следует использовать F
?