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

Question

我可以构建一个属于 Traversable 的数据结构类型类(例如 List 或 Map )，通过映射( 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

此函数返回可被 2 整除且介于 2 和 n(含)之间的整数的绝对值。

使用上面的例子，是否有一种惯用的方法可以在不使用递归的情况下从不可遍历的对象构建列表？

Answer 1

您要求一种不使用递归从不可遍历对象构建列表的方法，但我认为这真的不是您想要的。毕竟，任何遍历都会使用递归——您认为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，这两者之间的区别在于结果列表的顺序。