这段代码如何翻译成 Haskell？

Question

我正在苦恼Haskell，以及使用递归迭代事物的想法。

例如，如何使用递归来遍历一个列表或计算阶乘。 在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

将其翻译为“函数式范式”？任何指导都将不胜感激。

- user686605

Answer 1

抱歉，我无法不使用更好的算法来帮助您……

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

---

编辑：事后看来，这有点过度了，因为提问者一开始就尝试实现一个排序算法。

- hugomg

Answer 2

一步一步地进行：

list2 = list of numbers

我们将视其为一个事实，所以list2仍然只是一个数字列表。

for i from 0 to N // N being a positive integer

在Haskell中正确的做法通常是使用一个列表。惰性求值意味着只有在使用时才会计算值，因此从0到N遍历列表最终得到的结果与您在此处的循环相同。所以，只需要使用[0..n]即可解决问题；我们只需要找出该怎么处理它。

for each number in list2

鉴于使用“for each”，我们可以推断出需要遍历整个list2；但我们还不知道如何处理它。

if number == i, add to 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都已经为我们做了。通常情况下，当有更高级别的函数可以代替时，最好避免直接使用递归。

话虽如此，这里的算法有多个愚蠢之处，但我不想深入讨论，因为这似乎会分散你的注意力，而不是对你的实际问题有所帮助。

- C. A. McCann

---

为什么不使用concatMap而是在显式的连接步骤上进行折叠？ - bdonlan

请注意，在这种情况下，您可以使用列表推导式：[number | i <- [1..N]，number <- list2，i == number]，这是您伪代码的直接翻译。 - ysdx

因为我认为该问题是在寻找使用函数式风格的一般方法，而不是直接实现，而fold是更通用的方法。整个连接字符串的操作本身就很愚蠢，如果我要改进算法，我会远远超过仅仅使用concatMap。 - C. A. McCann

@chrislegend：我的解决方案的一般形式确实很通用，正如我之前的评论所述。然而，我怀疑在实践中你实际上正在做的事情需要完全不同的方法，因为Haskell列表基本上是链表，对于索引和搜索非常低效（与迭代和堆栈算法相比，它们非常有效）。 - C. A. McCann

@chrislegend：换句话说，我担心你可能从代码片段中削减了太多的含义，而真正的转换到函数式（特别是类似Haskell的）风格需要在实际代码的更高层面上进行。 - C. A. McCann

Answer 3

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

a<-list2 会挑选出 list2 中的每个数字 a>=0, a<=N 检查所选数字是否符合所有这些条件 如果条件都满足，就将 a 放入一个新列表中 一旦 list2 的所有元素都经过了这样的检查并放入了新列表中，我们对其进行排序 排序后的列表被赋值给 list1

- user946443