CODEWITHSUNDEEP
haskellrecursionhigher-order-functions
denizen
denizen

Reputation: 469

Convert List comprehension into recursive call

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

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

Upvotes: 3

Views: 691

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 153102

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]

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

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

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.

Upvotes: 3

Chris Taylor
Chris Taylor

Reputation: 47402

Is this the kind of thing you want? The list comprehension is only being used to filter the list anyway, so we can convert to a form that manually applies a filter.

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

Upvotes: 3

Related Questions