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
sieve [] = []
sieve (a:x) = a : sieve [y| y <- x, y `mod` a > 0]
sieve (a:x) = f x : map f xs where f = y `mod` a > 0
这是你需要的吗?列表推导式仅用于过滤列表,因此我们可以将其转换为手动应用过滤器的形式。
sieve [] = []
sieve (x:xs) = x : sieve (filter (\y -> y `mod` x > 0) xs)
[y| y <- x, y
mod a > 0]
与filter (\y -> y
mod a > 0) x
的等价性。(Markdown使反引号有点奇怪。) - Tom Ellisfilter
гЂ‚ењЁж ‡е‡†еғ“дёжӘЂжџӨ其定义еҚіеЏҮгЂ‚ - Tom Ellisy `mod` a
! - kqrsieve
进行递归调用。 - Chris TaylorTranslation: 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, andQ
over sequences of qualifiers.ok
is a fresh variable. The functionconcatMap
, and boolean valueTrue
, are defined in thePrelude
.
以下是这些规则如何适用于您的代码。
[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
版本已经完全没有列表推导式了,并且与原始版本完全相同。
mod
a> 0}”。 - Will Ness