如何使用 do-notation 写一个延续传递风格的蹦床函数？

Question

请注意以下功能：

range :: Int -> [Int]
range 0 = []
range n = (n - 1) : range (n - 1)

我们可以将其转换为蹦床 CPS 函数：

data Trampoline a = Done a | Wrap (() -> Trampoline a)

call :: Trampoline a -> a
call (Done a) = a
call (Wrap f) = call (f ())

range :: Int -> [Int]
range n = call (loop n Done) where
  loop :: Int -> ([Int] -> Trampoline [Int]) -> Trampoline [Int]
  loop 0 cont = cont []
  loop n cont = loop (n - 1) (\ tail -> Wrap (\x -> cont (n - 1 : tail)))

但是长得特别难看。是否有任何内置方法可以使用 do-notation 编写此函数，使其看起来或多或少像这样？

range n :: Int -> CPS [Int]
range 0 = do
  return []
range n = do
  tail <- range (n - 1)
  return (n - 1 : tail)

Answer 1

当然，您可以使用ContT，并且正如 Carl 在评论中指出的那样，您Trampoline是 的特化Free，因此我们可以重用它的Monad实例，或者您可以为Trampoline自己编写实例。

import Control.Monad.Cont  -- mtl
import Control.Monad.Free  -- free

call :: Free ((->) ()) a -> a
call (Pure a) = a
call (Free f) = call (f ())

type Trampoline = Free ((->) ())

range :: Int -> ContT [Int] Trampoline [Int]
range 0 = pure []
range n = do
  t <- range (n - 1)
  pure (n - 1 : t)

像这样使用，pure初始延续在哪里：

> call (runContT (range 5) pure)
[4,3,2,1,0]

基本上，只要你有一个看起来像(a -> b) -> b(或(a -> m b) -> m b)的函数，它就可以包含在Cont(resp. ContT) 中。在这里，即([Int] -> Trampoline [Int]) -> Trampoline [Int]，其中a= [Int]、m=Trampoline和b= [Int]。

(->) ()也可以替换为Reader ()，或者简单地替换为，Identity因为由于懒惰，() -> a与 just 是同构的——a尽管可能有一些性能差异，例如与后者更好地共享。

此外，FreeoverIdentity基本上只是一个列表，所以至少这个例子只是使用ContTover []or 的一种稍微复杂的方式NonEmpty， where callis Data.List.NonEmpty.head— 甚至只是一个列表本身。但是，以这种方式构建代码当然可能有正当理由。