如何使用do-notation来编写延续传递风格的跳床函数？

Question

注意以下函数：

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

我们可以将其转换为trampoline 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，正如卡尔在评论中指出的，你的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中。ContT)。这里是([Int] -> Trampoline [Int]) -> Trampoline [Int]，其中a = [Int]、m = Trampoline和b = [Int]。

(->) ()也可以替换为Reader ()，或者只是Identity，因为由于懒惰，() -> a与a-albeit同构，可能存在一些性能差异，例如与后者更好的共享。

此外，Identity上的Free基本上只是一个列表，所以至少这个例子只是在[]或NonEmpty上使用ContT的一种稍微复杂的方式，其中call是Data.List.NonEmpty.head-or，甚至只是一个列表。但当然，以这种方式构建代码可能有合理的理由。