我有以下函数把一个列表分成两半：

halve :: [a] -> ([a], [a])
halve xs =
  go xs xs
  where
    go (x : xs) (_ : _ : ys) =
      mapFst (x :) $ go xs ys
    go xs _ =
      ( []
      , xs
      )
    mapFst f (x, y) =
      ( f x
      , y
      )

我希望这在元组的第一个元素上实现懒惰计算。也就是说，要把第一半计算到深度n，就需要把输入列表计算到深度2n+2。

对我来说，上面的代码真的看起来像是在做这个，但我还是用Hspec写了一个测试：

{-# Language ScopedTypeVariables #-}

spec :: Spec
spec = do
  context "halving" $ do
    describe "halve" $ do
      it "should be lazy on the first argument" $ property $
        \ (x :: List Int)
        ->
          let
            bufferDepth =
              2
            tailEnd :: Int -> List Int
            tailEnd 0 =
              error "read too deep"
            tailEnd n =
              undefined : tailEnd (n-1)
          in
            take (length x) (fst $ halve $ x ++ x ++ tailEnd bufferDepth) `shouldBe` x

现在上面的代码无法通过这个测试。

  1) List.halving.halve should be lazy on the first argument
       uncaught exception: ErrorCall
       read too deep
       CallStack (from HasCallStack):
         error, called at test/ListSpec.hs:72:15 in main:ListSpec
       (after 2 tests and 2 shrinks)
         [0]

事实上，似乎无论把 bufferDepth 增大到多少，测试都以同样的方式失败。这让我觉得它根本就不是懒惰的。它需要先把整个输入评估完，才能评估第一半的第一个元素。

然而我对为什么会这样感到束手无策。这到底是怎么造成的？

解决方案

你可能写了：

mapFst f (x, y) = (f x, y)

要让它继续推进，它必须知道它的第二个参数实际上是一个应用于参数的 (,) 构造器。但要知道这一点，你的 go 必须把递归推到底部的基本情况，然后把来自底部的结论向上传递，最终确认调用是一个 (,)。试试这个：

mapFst f ~(x, y) = (f x, y)
-- OR
mapFst f xy = let (x, y) = xy in (f x, y)
-- OR
mapFst f xy = (f (fst xy), snd xy)

这些版本返回的东西显然是一个 (,) 构造器，而不先检查它们的第二个参数；随后再检查第二个参数以决定 (,) 的字段取值。