将列表理解转换为递归调用 [英] Convert List comprehension into recursive call

问题描述

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

我想将此代码转换为递归实现或使用诸如map和filter之类的高阶函数.我不知道该怎么办.

I want to convert this code to recursive implementation or using higher order functions such as map and filter. I can't figure out how do I do this.

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

I have tried this way but it wont seem to work

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

推荐答案

除了克里斯的精妙答案(归结为了解代码在做什么并理解正确的翻译")外，还有更多的机制您可以翻译.列表理解的行为是在Haskell报告中指定的:

In addition to Chris' fine answer, which boils down to "understand what the code is doing and intuit the correct translation", there is a much more mechanical translation you can do. The behavior of list comprehensions is specified in the Haskell Report:

翻译:列表理解满足这些身份，可以用作对内核的翻译:

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]

其中， e 覆盖整个表达式， p 覆盖模式， l 覆盖列表值表达式， b 覆盖布尔表达式，声明列表中的 decls ，限定词中的 q 和限定词序列中的 Q . ok 是一个新变量.函数 concatMap 和布尔值 True 在 Prelude 中定义.

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.

以下是这些规则适用于您的代码的方式.

Here's how those rules would apply to your code.

[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 的第二个子句似乎是无效代码，因此:

After this process, you're left with no list comprehensions. Then we can start applying other transformations we know about; for example, the second clause of ok here seems to be dead code, so:

= { 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 版本完全没有列表理解，其行为与原始版本完全相同.

Whether you can make the intuitive leap from this version of the code to filter is of course another question entirely! But it's not necessary to make that leap: this concatMap version has no list comprehensions left at all and behaves exactly the same as the original.

这篇关于将列表理解转换为递归调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！