是否有一种非递归方式来编写这个"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.我们的起始值是我们要分成块的列表,因此我们不需要在那里进行任何更多的处理.这意味着我们的最后一步是实现步骤功能.

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

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

嘿,看起来非常类似于splitAt!

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

事实上,我们可以只是包装的结果splitAt在Just和satify我们的类型.但这留下了一个非常重要的部分:最终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)