haskell - 有没有一种非递归的方式来编写这个 "paginate"函数？

Question

以下函数不在标准的 Haskell 库中，所以我编写了它:

paginate _ [] = []
paginate n xs = let (h, t) = splitAt n xs in h : paginate n t

然后我想在没有显式递归的情况下重写它，但仍然很容易理解。

我试过 fix版本，它不会产生非常令人满意的结果:

paginate = fix go
  where
    go _ _ [] = []
    go v n xs = let (h, t) = splitAt n xs in h : v n t 

是否有使用 Prelude 功能的更简单的解决方案？

Answer 1

当我看到这种问题时，我喜欢思考你想要的功能的“形状”。在这种情况下，您从一个列表开始并生成一个列表列表。这是从单个值开始并生成列表的特殊情况，对应于 展开 .所以，如果你不介意导入 Data.List ，您可以使用 unfoldr 巧妙地编写您的函数.

让我们一步一步来看看如何得出这个结论。首先，如上所述，您只需要了解unfoldr并看到它可以应用。这就是一些经验(比如阅读这样的答案:))的用武之地。

接下来我们看看unfoldr的类型:

Prelude Data.List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

这个想法是我们从一个单一的“内核”值( b)开始，然后重复应用一个阶梯函数( b -> Maybe (a, b))，直到我们点击 Nothing。 .我们的起始值是我们想要分成 block 的列表，所以我们不需要在那里做任何更多的处理。这意味着我们的最后一步是实现 step 函数。

由于我们从值列表开始，我们可以替换 b与 [n] ;此外，由于我们想在最后生成一个列表列表，我们可以替换 [a]与 [[n]]因此， a与 [n] .这给了我们必须为 step 函数实现的最终类型:

[n] -> Maybe ([n], [n])

嘿，这看起来与 splitAt 的类型非常相似!

splitAt :: Int -> a -> ([a], [a])

事实上，我们可以将 splitAt 的结果包装起来。在 Just并满足我们的类型。但这遗漏了一个非常重要的部分:最后的 Nothing告诉 unfoldr停止!所以我们的辅助函数需要一个额外的 [] 的基本情况。返回正确的结果。

把它们放在一起给了我们最终的功能:

import Data.List (unfoldr)

paginate n = unfoldr go
  where go [] = Nothing -- base case
        go ls = Just (splitAt n ls)

我认为最终结果非常好，但我不确定它是否比递归版本更具可读性。

如果您不介意启用扩展( LambdaCase )，您可以通过避免命名 go 以稍微简洁的方式重写它。 :

paginate n = unfoldr $ \case
  [] -> Nothing
  ls -> Just (splitAt n ls)