将列表推导式转换为递归调用

Question

sieve [] = []
sieve (a:x) = a : sieve [y| y <- x, y `mod` a > 0]

我希望将这段代码转换成递归实现或使用诸如map和filter的高阶函数。我无法弄清楚该如何做。

我已经尝试过这种方法，但似乎不起作用。

sieve (a:x) = f x : map f xs where f = y `mod` a > 0

- denizen

---

你接近了：“筛子（a：xs）= a：filter f xs，其中{f y = ymoda> 0}”。 - Will Ness

Answer 1

这是你需要的吗？列表推导式仅用于过滤列表，因此我们可以将其转换为手动应用过滤器的形式。

sieve []     = []
sieve (x:xs) = x : sieve (filter (\y -> y `mod` x > 0) xs)

- Chris Taylor

---

请注意，Chris的答案直接源于[y| y <- x, y mod a > 0]与filter (\y -> y mod a > 0) x的等价性。（Markdown使反引号有点奇怪。） - Tom Ellis

@bddesai89пәљдҢ еЏҮд»ӨйЂљиү‡йЂ’еҢ’жқӨе®һзҺ°filter。在标准еғ“дё­жӘЂжџӨ其定义еҚіеЏҮгЂ‚ - Tom Ellis

@TomEllis：它只找出奇数，而不是质数。 - denizen

如果您在代码周围使用双反引号，就可以在代码中包含反引号。y `mod` a！ - kqr

@bddesai89 抱歉，是我的错 - 我忘记了对sieve进行递归调用。 - Chris Taylor

Answer 2

除了Chris的精彩回答，即“理解代码正在做什么并直觉地进行正确的翻译”，您还可以进行更机械化的翻译。列表推导式的行为在 Haskell报告中有明确规定：

Translation: List comprehensions satisfy these identities, which may be used as a translation into the kernel:

[e | True]         =  [e]
[e | q]            =  [e | q, True]
[e | b, Q]         =  if b then [e | Q] else []
[e | p <- l, Q]    =  let ok p = [e | Q]
                          ok _ = []
                      in concatMap ok l
[e | let decls, Q] =  let decls in [e | Q]

where e ranges over expressions, p over patterns, l over list-valued expressions, b over boolean expressions, decls over declaration lists, q over qualifiers, and Q over sequences of qualifiers. ok is a fresh variable. The function concatMap, and boolean value True, are defined in the Prelude.

以下是这些规则如何适用于您的代码。

[y | y <- x, y `mod` a > 0]
= { fourth equation }
let ok y = [y | y `mod` a > 0]
    ok _ = []
in concatMap ok x
= { second equation }
let ok y = [y | y `mod` a > 0, True]
    ok _ = []
in concatMap ok x
= { third equation }
let ok y = if y `mod` a > 0 then [y | True] else []
    ok _ = []
in concatMap ok x
= { first equation }
let ok y = if y `mod` a > 0 then [y] else []
    ok _ = []
in concatMap ok x

在此过程之后，您将不再拥有列表推导式。然后我们可以开始应用我们知道的其他转换；例如，这里的ok的第二个子句似乎是死代码，因此：

= { dead code elimination }
let ok y = if y `mod` a > 0 then [y] else []
in concatMap ok x
= { inlining }
concatMap (\y -> if y `mod` a > 0 then [y] else []) x

你是否能够从这个版本的代码中直观地跳转到filter，当然是另一个完全不同的问题！但是没有必要进行这样的跳转：这个concatMap版本已经完全没有列表推导式了，并且与原始版本完全相同。

- Daniel Wagner