在 Haskell 中什么时候使用 CPS vs codensity vs reflection

Question

对于何时使用 continuation-passing style vs codedensity vs reflection without remorse 是否有任何经验法则 在 Haskell?

中创建 monad 时

例如，我将使用一个简单的协程 monad。如果您以前从未见过此内容，则可能需要查看 Monad.Reader Issue 19 or the pipes library. The full code for the following examples can be found in this repository 中的 "Coroutine Pipelines" 文章。

正常

这只是一个定义为数据类型的普通 monad:
```
data FooM i o a
  = Await (i -> FooM i o a)
  | Yield o (FooM i o a)
  | Done a
```
这种风格在 Haskell 生态系统中被广泛使用。这种风格的一个例子是来自 pipes.

Proxy

连续传递样式 (CPS)

这类似于 normal 样式，但每个数据构造函数都已成为延续的参数：

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 and parsec.

代码密度

此样式使用 codensity monad transformer 包裹在 normal 样式中定义的 monad。这给出了 O(1) 左关联绑定。

代码密度单子转换器如下所示：
```
newtype Codensity m a = Codensity
  { runCodensity :: forall b. (a -> m b) -> m b
  }
```
我们实际的 monad 可以使用 Codensity 转换器定义为新类型。注意 FooCodensity 如何在内部使用 FooM。
```
newtype FooCodensity i o a = FooCodensity
  { runFooCodensity :: Codensity (FooM i o) a
  }
```
此样式被conduit in the ConduitM类型使用。
反省无悔

这是论文中讨论的样式 Reflection without Remorse。

这类似于 normal 风格，但递归调用已成为具有 O(1) 追加和分摊 O(1) 非cons 的数据结构。这为 FooRWR monad 提供了 O(1) 左关联绑定和 monadic 反射：
```
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) 非成本的数据结构。

此样式被freer-effects and extensible packages. It is available as a standalone library in monad-skeleton使用。

什么时候应该 normal vs CPS vs codensity vs 没有反射remorse被利用了？我想一个硬性的快速答案需要对给定的 monad 和应用程序进行基准测试，但是是否有 任何经验法则?

根据我自己的研究，我发现了以下 ideas/comments：

CPS 可能比 normal 风格更快，因为您可能不必进行案例分析。尽管实际加速可能会因 GHC 编译代码的方式而异。 代码密度和无悔反思有一些开销。

Gabriel Gonzalez（pipes 的作者）在 this reddit thread and this issue 上写到他如何坚持 pipes 的正常风格 this reddit thread and this issue =229=].

Bryan O'Sullivan（attoparsec 的作者）写了如何将 attoparsec 从 normal 样式更改为 CPS给了一个factor of 8 speedup。关于 post 的一些评论还谈到 normal 风格与 CPS.
如果需要深左关联绑定，normal 样式和 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用代码密度或无悔反射重写，它将运行非常快。

如果您的应用程序具有深度左关联绑定，您可能应该使用 codensity 或 reflection without remorse.

Michael Snoyman（conduit 的作者）在关于 speeding up conduit.
的博客 post 中谈到了这一点
pipes 库 used to provide 一个密码变换器。
CPS 和 codensity 不支持 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)
```
如果不首先转换回 normal[，则无法以 CPS 或 codensity 样式编写此方法=175=]风格。 反省无悔风格没有这个问题

如果你需要 monadic 反射，你可能应该使用 normal 风格或 没有悔意的反射。

无悔的反射增加了一些开销，但它是唯一同时提供 O(1) 左关联绑定和反射的样式。

奖励问题：关于 Free (normal style) vs F (CPS) from the free 包可以问类似的问题。什么时候应该使用Free？什么时候应该使用F？

Answer 1

这个问题可以分为两部分，如何表示数据类型以及如何将它们组合在一起。

数据类型

您列出的样式仅使用 2 种数据类型样式，"normal" 样式和延续传递样式。它们的不同之处在于选择哪些对象作为语言的原语。

在普通样式中，数据类型及其构造函数被选为原始类型。数据类型是产品（持有多个值）的总和（具有多个构造函数）

data Sum a b = Left a | Right b
data Product a b = Product a b

语言的主要对象是这些数据类型和函数；这些函数解构数据以查看其中的内容并查看它的作用。

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l _ (Left a)  = l a
either _ r (Right b) = r b

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry f (Product a b) = f a b

您可以创建一种等效语言，其中将通用量化类型视为原始类型而不是数据类型。在这种情况下，您可以根据通用量化来定义数据类型。总和由它们的 either 函数表示，在 return 类型上普遍量化。产品由它们的 uncurry 函数表示，在 return 类型上普遍量化。需要语言扩展 (RankNTypes) 来以这种方式表示数据类型，这暗示了为什么要调用第一种样式 "normal".

{-# LANGUAGE RankNTypes #-}

newtype Product a b = Product (forall r. (a -> b -> r) -> r)

product :: a -> b -> Product a b
product a b = Product (\f -> f a b)

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry both (Product f) = f both

newtype Sum a b = Sum (forall r. (a -> r) -> (b -> r) -> r)

left :: a -> Sum a b
left a = Sum (\l r -> l a)

right :: b -> Sum a b
right b = Sum (\l r -> r b)

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l r (Sum f) = f l r

这是两种风格之间的主要区别之一。在普遍量化的风格中，没有任何构造函数。数据的所有结构都必须存储在函数的闭包中，这正是构造函数 left、right 和 product 的替换位置。在普遍量化的风格中，你不能构造任何不必要的中间对象；不存在供您构建的对象。您仍然可以构建不必要的中间闭包。至少你会欺骗探查器告诉你你周围没有一堆对象。

您的 FooM 数据类型，在这里重复，也可以用连续传递样式表示。

data FooM i o a
  = Await (i -> FooM i o a)
  | Yield o (FooM i o a)
  | Done a

它将由我定义的 matchFoo 函数表示。

matchFoo :: ((i -> FooM i o a) -> r) -> (o -> FooM i o a -> r) -> (a -> r) -> r
matchFoo a _ _ (Await f) = a f
matchFoo _ y _ (Yield o next) = y o next
matchFoo _ _ d (Done a) = d a

通用量化的 FooM 标识具有 matchFoo 函数的 FooM，通用限定其 return 类型。

newtype FooCPS i o a = FooCPS
  { runFooCPS
      :: forall r.
         ((i -> FooCPS i o a) -> r)
      -> (o -> FooCPS i o a -> r)
      -> (a -> r)
      -> r
  }

await :: (i -> FooCPS i o a) -> FooCPS i o a
await f = FooCPS (\a _ _ -> a f)

yield :: o -> FooCPS i o a -> FooCPS i o a
yield o next = FooCPS (\_ y _ -> y o next)

done :: a -> FooCPS i o a
done a = FooCPS (\_ _ d -> d a)

破解问题2

为了将相同的数据类型用于将它们重新组合在一起的所有方式，我们将用其基本仿函数替换 FooM。基本仿函数是普通数据类型，递归被类型变量替换。

data FooF i o a next
  = Await (i -> next)
  | Yield o next
  | Done a
    deriving (Functor)

您可以等价地定义延续传递样式中的基函子。

newtype FooFCPS i o a next = FooFCPS
  { runFooCPS
      :: forall r.
         ((i -> next) -> r)
      -> (o -> next -> r)
      -> (a -> r)
      -> r
  }
  deriving (Functor)

将它们组合在一起

正常

我们可以通过定义

立即恢复FooM

newtype FooM i o a = FooM (FooF i o a (FooM i o a))

如果您已经定义了 fixed point of a functor:

newtype Fix f = Fix (f (Fix f))

然后FooM可以通过

恢复

newtype FooM i o a = FooM (Fix (FooF i o a))

延续传球风格

可以立即从普遍量化的传球风格中恢复传球风格FooFCPS

newtype FooCPS i o a = FooCPS (Fix (FooFCPS i o a))

代码密度

代码密度转换器适用于 FooM 或 FooCPS。

无悔反省

我们可以根据基本函子定义反射而无需在 FooRWR.

中重现数据类型 FooM

newtype RWR f a = RWR { runRWR :: f (RWRExplicit f a) }

newtype RWRExplicit f a = RWRExplicit (forall x. FTCQueue (RWR f) x a)

然后用

恢复FooRWR

newtype FooRWR i o a = FooRWR {runFooRWR :: RWR (FooF i o a) a}

奖金观察

免费

Free 和 F 都可以与基本函子 FooF 或 FooFCPS.

一起使用

Monad 变形金刚

基仿函数也可用于构建 monad 转换器。有一个 .

如果不首先转换回正常样式就不能用 CPS 编写 par 的说法需要一些限定，因为所有数据类型都可以用通用量化的连续传递样式类型替换。

在 Haskell 中什么时候使用 CPS vs codensity vs reflection

when to use CPS vs codensity vs reflection without remorse in Haskell

reflection

monads

continuations

haskell

free-monad

数据类型

破解问题2

将它们组合在一起

奖金观察