CODEWITHSUNDEEP
listhaskellfilter
user3556115
user3556115

Reputation: 143

haskell, sieve a list with multiple filters

Given the type

sieve :: [a -> Bool] -> [a] -> [[a]]

I have to write a function, which filters a list using a list of functions [a->Bool]. Each filter must only sieve through what the filters before left over. It gives back a list of lists, each list representing what was caught by the sieve. The last list is what has not been caught by any of the filters. e.g.

sieve [(<3),(>7),odd] [1..10] gives back [[1,2],[8,9,10],[3,5,7],[4,6]]

I know sieve must start this way...

sieve fs xs = concat $ filter () ...

My problem is: Before I can go to the complicated part of the work, the step by step filtering, I don't get how to access each of the functions in the function list and use it on the [a] list. If it was one function it would be easy with (filter f xs)

I tried a lot and don't get it.

Can someone please help and possibly give a little hint how to manage the one after another filter system? Any hint is welcome.

EDIT:

I now have this: It is the way I think it should work but I have a problem negating the boolean function... Can you help?

    sieve :: [a -> Bool] -> [a] -> [[a]]
    sieve [] xs = [xs]
    sieve (f:fs) xs = (filter f xs) : (sieve fs (filter nf xs))

            where nf = not f

This does not work because I may not use (not f) like this. Any idea?

EDIT: FINAL SOLUTION

partition p xs = (filter p xs, filter (not . p) xs)

    sieve :: [a -> Bool] -> [a] -> [[a]]
    sieve [] xs = [xs];
    sieve (f:fs) xs = p1 : (sieve fs p2)
    where p1 = fst (partition f xs)
          p2 = snd (partition f xs)

Upvotes: 1

Views: 897

Answers (1)

Lee Duhem
Lee Duhem

Reputation: 15121

You want to do something for each element of a list and accumulate the results when you do that, this is exactly what fold functions are for:

import Data.List (partition, foldl')

sieve fs xs = let (p1, p2) = fold fs xs in p2 ++ [p1]
    where fold fs xs = foldl' step (xs, []) fs
          step (lst, rs) f = let (r1, r2) = partition f lst in (r2, rs++[r1])

To implement it by using recursion, what you need to do is filtering the list left behind by the filter before it, and collect results when you do this:

import Data.List (partition)

sieve [] xs = [xs]
sieve (f:fs) xs = let (p1, p2) = partition f xs
                   in p1 : sieve fs p2

Upvotes: 1

Related Questions