何时在Haskell中使用CPS vs密度与反射无悔

Question

在Haskell中创建monad 时,是否有任何关于何时使用延续传递样式与密度和反射而没有悔恨的经验法则？

举个例子,我将使用一个简单的协程monad.如果您以前从未见过这个,可能需要查看Monad.Reader Issue 19中的"Coroutine Pipelines"文章或管道库.可以在此存储库中找到以下示例的完整代码.

1. 正常

   这只是一个定义为数据类型的普通monad:

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

   这种风格被广泛用于Haskell生态系统.这种风格的一个例子是Proxy来自的数据类型pipes.

2. 延续传球风格(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.

3. Codensity

   此样式使用包围在正常样式中定义的monad 的密码单元monad变换器.这给出了O(1)左关联绑定.

   密码monad转换器如下所示:

   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
     }
   

   此类型由管道中的ConduitM类型使用.

4. 没有悔恨的反思

   这是反思无悔的论文中讨论的风格.

   这类似于普通样式,但递归调用已成为一个数据结构,其中O(1)追加并且摊销O(1)uncons.这给了Monad的O(1)左关联绑定和monadic-reflection 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.

   此类样式由更自由的效果和可扩展包使用.它作为monad-skeleton中的独立库提供.

---

什么时候应该使用正常 vs CPS vs 密度与没有悔恨的反射？我想一个快速而快速的答案需要对给定的monad和应用程序进行基准测试,但有没有经验法则？

根据我自己的研究,我发现了以下想法/评论:

• CPS可以比正常样式更快,因为您可能不需要进行案例分析.虽然实际加速可能会根据GHC编译代码的方式而有所不同. 没有悔恨的密码和反思有一些开销.

  Gabriel Gonzalez(作者pipes)写了关于他如何在这个reddit线程和Github上的这个问题上坚持正常风格.pipes

  布赖恩·奥沙利文(笔者attoparsec)写道如何改变attoparsec从正常的风格,以CPS给了8加速的因素.关于该帖子的一些评论也谈到了正常风格与CPS.

• 如果您需要深度左关联绑定,则正常样式和CPS最终会出现二次运行时.

  以下是"无需思考的反思"论文中的一个例子,它将展示二次运行时间.

  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用密码或反射重写没有悔恨,它将运行得非常快.

  如果您的应用程序具有深度左关联绑定,您可能应该使用密码或反射而无需悔恨.

  Michael Snoyman(作者conduit)在一篇关于加速 的博客文章中谈到了这一点conduit.

  该pipes库用于提供密度变换器.

• CPS和密度不支持O(1)反射.

  这是一个需要monadic反射的函数.这个例子改编自"没有悔意的反思"论文:

  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或密码度样式编写此方法.没有悔恨风格的反思没有这个问题.

  如果你需要monadic反射,你应该使用正常的风格或反射,而不是悔恨.

• 没有悔恨的反射增加了一些开销,但它是唯一同时给出O(1)左关联绑定和反射的样式.

奖金问题:可以从免费套餐中询问类似的问题Free(正常风格)与F(CPS).什么时候应该使用？什么时候应该使用？FreeF

Answer 1

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

数据类型

您列出的样式仅使用2种数据类型,"普通"样式和延续传递样式.它们的不同之处在于选择哪些对象作为语言的基元.

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

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函数表示,通常在返回类型上量化.产品由它们的uncurry功能表示,通常在返回类型上量化.语言扩展(RankNTypes)以这种方式表示数据类型的需要暗示了为什么要调用第一个样式"正常".

{-# 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的东西FooM用它的matchFoo功能来识别a ,它的返回类型普遍合格.

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)

将它们组合在一起

1. 正常

我们可以FooM通过定义立即恢复

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

如果您已经定义了仿函数的固定点:

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

然后FooM可以通过恢复

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

2. 延续传球风格

延续传递方式可以立即从普遍量化的方式中恢复 FooFCPS

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

3. Codensity

密度变换器适用于FooM或FooCPS.

4. 没有悔恨的反思

我们可以定义没有碱函子而言自责反射而不再现的数据类型FooM中FooRWR.

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变换器.在这个问题和答案中有一个关于构建MachineT变压器(与之密切相关FooM)的详细讨论.

该权利要求par不能在CPS被写而无需首先转换回普通样式需要一些资格,因为所有的数据类型可以用普遍量化延续传递风格类型来代替.