这段代码将如何转换为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 = 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

鉴于"为每个人",我们可以推断出我们需要遍历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

处理内循环.向后退一步,我们需要为i列表中的每个值运行此值[0..n],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正在做的是我们.根据经验,当有更高级别的函数为您执行时,通常最好避免直接递归.

也就是说,这里的算法在很多方面都是愚蠢的,但我不想进入那个,因为它似乎会分散你的实际问题,而不是它会有所帮助.