这段代码如何翻译成 Haskell？

Question

我正在与 Haskell 以及使用递归来迭代事物的想法作斗争。

例如，如何

// this might seem silly but I need to do it
list1 = empty list
list2 = list of numbers
for i from 0 to N // N being a positive integer
    for each number in list2
        if number == i, add to list1

转化为“功能范式”？任何指导将不胜感激。

Answer 1

抱歉，但我忍不住使用更好的算法...

let goodNumber n = (0 <= n && n < N)
let list1 = sort (filter goodNumber list2)

---

编辑：事后看来，这有点矫枉过正，因为OP首先试图实现排序算法。

Answer 2

一步一步进行：

list2 = 数字列表

我们将其视为给定的，因此 list2 仍然只是一个数字列表。

for i from 0 to N // N 是正整数

在 Haskell 中执行此操作的正确方法通常是使用列表。惰性意味着仅在使用时才计算值，因此从 0 到 N 遍历列表最终与此处的循环相同。因此，只要 [0..n] 就可以了；我们只需要弄清楚如何处理它。

对于 list2 中的每个数字

给定“for every”，我们可以推断出我们需要遍历整个 list2 ；我们还不知道我们用它做什么。

如果 number == i，则添加到 list1

我们正在构建 list1，因此理想情况下我们希望它成为表达式的最终结果。这也意味着在每个递归步骤中，我们希望结果是“到目前为止”的 list1。为此，我们需要确保在进行过程中传递每个步骤的结果。

因此，开始讨论它的实质：

filter 函数查找列表中与某个谓词匹配的所有元素；我们将在这里使用 filter (== i) list2 来查找我们想要的内容，然后将其附加到上一步的结果中。因此，每个步骤将如下所示：

step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2

处理内部循环。退一步来说，我们需要对列表 [0..n] 中的每个值 i 运行此函数，并传递 list1 值一起迈出每一步。这正是折叠函数的用途，在本例中 step 正是我们左折叠所需的：

list2 :: (Num a) => [a]
list2 = -- whatever goes here...

step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2

list1 :: (Num a) => a -> [a]
list1 n = foldl step [] [0..n]

如果您想知道递归在哪里，请使用 filter和 foldl 正在为我们做这件事。根据经验，当有更高级别的函数可以为您执行递归时，通常最好避免直接递归。

---

也就是说，这里的算法在很多方面都很愚蠢，但我不想深入探讨这一点，因为它似乎会分散你对实际问题的注意力，而不是有帮助。

Answer 3

let list1 = sort [a | a<-list2, a>=0, a<=N]

a<-list2 选取 list2 的每个数字
a>=0, a<=N 检查所选号码是否满足所有这些条件
如果满足条件，则将 a 放入新列表中
一旦 list2 的所有元素都被检查并放入一个新列表中，我们就对此进行排序
结果列表被分配给list1