从非递归的不可遍历构建列表

Question

我可以通过映射（map、mapM) 或折叠 (foldl, foldM) 另一个可遍历的数据结构。

然而，我经常遇到需要使用 Num 类型类（例如 Integer）的成员构建可遍历数据结构的情况。

这里我通常的做法是使用递归操作来构建列表——例如：

foo :: Integer -> [Integer] -> [Integer]
foo n fs
  | m < 2 = fs
  | rem m 2 == 0 = foo (m - 1) (m:fs)
  | otherwise = foo (m - 1) fs
  where m = abs n

此函数returns可被二整除且介于 2 和 n（含）之间的整数的绝对值。

使用上面的例子，有没有一种不使用递归从不可遍历构建列表的惯用方法？

Answer 1

由于您要从 2 到 n，并过滤掉值，因此使用专为此设计的 filter 函数：

foo :: Integer -> [Integer]
foo n = filter (\x -> x `mod` 2 == 0) [2..n]

Answer 2

您正在寻求一种不使用递归从不可遍历对象构建列表的方法，但我认为这真的不是您想要的。毕竟，任何遍历都会使用递归——你认为map和foldl是如何实现的？我认为你问的更精确的问题是是否有一个众所周知的函数或内置方式来表达所谓的“数字折叠”，其中递归是“幕后”或隐式的，而不是显式的在您的 foo 示例中。

好吧，一个简单的实现方法是自己编写一个 foldNum 函数。例如：

foldNum :: Num n => (n -> a -> a) -> n -> a
foldNum f n = f n (foldNum f (n - 1))

那么，你可以定义foo为：

foo :: Integer -> [Integer]
foo = reverse . foldNum go . abs
  where
    go n a | n < 2        = []
           | rem n 2 == 0 = n:a
           | otherwise    = a

如果您对此有点失望，我理解原因：使用 foldNum 的这个定义并没有真正节省多少。事实上，我上面给出的定义 甚至没有内置的基本情况 。折叠数字的问题在于有很多方法可以做到！您可以在每一步中减去或添加任何数量，并且没有明确的停止位置（零似乎是一个自然的停止位置，但这仅适用于非负数）。一种方法是尝试使我们的 foldNum 更加通用。怎么样：

foldNum :: (n -> a -> a) -> (n -> Bool) -> (n -> n) -> a -> n -> a
foldNum f stop step a n
  | stop n = a
  | otherwise = foldNum f stop step (f n a) (step n)

现在，我们可以将 foo 写成：

foo :: Integer -> [Integer]
foo = foldNum (\x a -> if even x then x:a else a) (< 2) (subtract 1) [] . abs

也许这就是您要找的东西？

脚注：正如列表可以向左或向右折叠（foldl 和 foldr）一样，我们也可以用两种不同的方式折叠数字。您可以通过将上述 foldNum 定义的最后一行替换为 ::

来看到这一点

  | otherwise = f n $ foldNum f stop step a (step n)

例如，对于 foo，这两者之间的区别在于结果列表的顺序。

Answer 3

我认为您可能正在寻找 Data.List 中的库函数 unfoldr。它有签名：

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

它从 b 类型的值生成一个列表 [a]，它是不可遍历的。它通过将其第一个参数重复应用于 b 值来获取新的 a 值以添加到列表中并为下一次调用更新 b 值来运行，直到它获得 Nothing 结束列表。

请注意，它不允许您跳过某些 b 而不生成任何 a，也不允许您为单个 b 生成多个 a .但是，您可以通过返回列表的列表然后连接来解决该限制。因此，您的 foo 示例将如下所示：

foo = concat . unfoldr step
  where step n | m < 2 = Nothing  -- time to stop
               | rem m 2 == 0 = Just ([m], m-1)  -- return one element
               | otherwise    = Just ([], m-1)   -- return no elements
          where m = abs n

在许多更现实的场景中，您不需要 concat 列表的列表。例如：

import Data.List

bar :: Int -> [[Int]]
bar n = unfoldr step 1
  where step k | k > n     = Nothing
               | otherwise = Just (replicate k k, k + 2)

main = do
  print $ bar 10
  -- [[1],[3,3,3],[5,5,5,5,5],[7,7,7,7,7,7,7],[9,9,9,9,9,9,9,9,9]]

从非递归的不可遍历构建列表

Building a list from a non-traversable without recursion

haskell

recursion

enums

traversable