1

我可以通过映射 ( , ) 或折叠 ( , ) 另一个可遍历的数据结构来构建作为类型类成员的数据结构Traversable（例如Listor ）。MapmapmapMfoldlfoldM

但是，我经常遇到需要使用类型类的成员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（含）之间的整数的绝对值。

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

4

3 回答 3

3

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

于 2020-12-21T18:28:04.427 回答
2

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

foo :: Integer -> [Integer]
foo n = filter (\x -> x `mod` 2 == 0) [2..n]
于 2020-12-21T17:18:07.830 回答
1

我认为您可能正在寻找的是unfoldr来自Data.List. 它有签名：

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

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

请注意，它不允许您跳过某些bs 而不生成任何as 或让您a为单个 s 生成多个 s b。但是，您可以通过返回列表列表然后连接来解决该限制。因此，您的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]]
于 2020-12-21T23:10:41.290 回答