[kepler-dev] filtering from a list

[Bertram Ludaescher]

Xiaowen:

Regarding your question yesterday, i.e., how to take the first N
elements from a list that pass a certain filter, here is a preliminary
solution in Haskell. Note that it has the inefficiency that it
first filters the whole list, then takes N elements of the result.

I can only think declaratively at this hour ... my procedural brain
needs another hour to wake up (but then I'll be at the SPA meeting
already ;-)

Here is the program:

    -- Some sample integer list
    my_list = [1..30] 

    -- Test whether an integer x is even
    my_test x = even x

    -- Given a predicate 'test' and a list (queue) 'ys',
    -- .. add a given 'x' to 'ys', if 'test(x)' is true
    add_if test ys x  = if (test x) 
                        then ys++[x]
                        else ys

    -- Given a 'test' and a 'list' return the filtered 'list',
    -- ... i.e., containing only elements passing the 'test' 
    my_filter :: (a -> Bool) -> [a] -> [a]
    my_filter test list = (foldl (add_if test) [] list)

    -- Now apply my_filter on my_list using my_test
    go = my_filter my_test my_list

    -- Take only the first N elements: 
    goN n = (take n go)


Here is the trace:


    Hugs session for:
    c:\Program Files\Hugs98\lib\Prelude.hs
    c:\my\Haskell\kepler.hs

Infer the type of 'my_test'
    > :t my_test
    my_test ::  a -> Bool
(it's a test on an element of type (a)lpha returning a Boolean

What's the type of add_if?
    > :t add_if
    add_if :: (a -> Bool) -> [a] -> a -> [a]

What's the type of my_filter?
    > :t my_filter
    my_filter :: (a -> Bool) -> [a] -> [a]

Now do the filter operation:
    > go
    [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30] :: [Integer]

What's the type of goN
    > :t goN
    goN :: Int -> [Integer]
(it takes a number (the count of elements to return) and returns a
list of results)

So here, finally, how to pick the first 3:
    > goN 3
    [2,4,6] :: [Integer]


Again, this still has the disadvantage of filtering even after the
first N elements are found...

More later...

Bertram