[kepler-dev] Re: filtering from a list

[Bertram Ludaescher]

I forgot to mention: The crux of the declarative solution is the
'foldl' higher-order function.  Don't have a good reference right now,
but try 'google foldl foldr'.

For the procedural solution, we'll need sth else I think.

Bertram

PS This is has to do with the Kepler/SPA PIW workflow..


>>>>> "BL" == Bertram Ludaescher <ludaesch at sdsc.edu> writes:
BL> 
BL> Xiaowen:
BL> 
BL> Regarding your question yesterday, i.e., how to take the first N
BL> elements from a list that pass a certain filter, here is a preliminary
BL> solution in Haskell. Note that it has the inefficiency that it
BL> first filters the whole list, then takes N elements of the result.
BL> 
BL> I can only think declaratively at this hour ... my procedural brain
BL> needs another hour to wake up (but then I'll be at the SPA meeting
BL> already ;-)
BL> 
BL> Here is the program:
BL> 
BL>     -- Some sample integer list
BL>     my_list = [1..30] 
BL> 
BL>     -- Test whether an integer x is even
BL>     my_test x = even x
BL> 
BL>     -- Given a predicate 'test' and a list (queue) 'ys',
BL>     -- .. add a given 'x' to 'ys', if 'test(x)' is true
BL>     add_if test ys x  = if (test x) 
BL>                         then ys++[x]
BL>                         else ys
BL> 
BL>     -- Given a 'test' and a 'list' return the filtered 'list',
BL>     -- ... i.e., containing only elements passing the 'test' 
BL>     my_filter :: (a -> Bool) -> [a] -> [a]
BL>     my_filter test list = (foldl (add_if test) [] list)
BL> 
BL>     -- Now apply my_filter on my_list using my_test
BL>     go = my_filter my_test my_list
BL> 
BL>     -- Take only the first N elements: 
BL>     goN n = (take n go)
BL> 
BL> 
BL> Here is the trace:
BL> 
BL> 
BL>     Hugs session for:
BL>     c:\Program Files\Hugs98\lib\Prelude.hs
BL>     c:\my\Haskell\kepler.hs
BL> 
BL> Infer the type of 'my_test'
>> :t my_test
BL>     my_test ::  a -> Bool
BL> (it's a test on an element of type (a)lpha returning a Boolean
BL> 
BL> What's the type of add_if?
>> :t add_if
BL>     add_if :: (a -> Bool) -> [a] -> a -> [a]
BL> 
BL> What's the type of my_filter?
>> :t my_filter
BL>     my_filter :: (a -> Bool) -> [a] -> [a]
BL> 
BL> Now do the filter operation:
>> go
BL>     [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30] :: [Integer]
BL> 
BL> What's the type of goN
>> :t goN
BL>     goN :: Int -> [Integer]
BL> (it takes a number (the count of elements to return) and returns a
BL> list of results)
BL> 
BL> So here, finally, how to pick the first 3:
>> goN 3
BL>     [2,4,6] :: [Integer]
BL> 
BL> 
BL> Again, this still has the disadvantage of filtering even after the
BL> first N elements are found...
BL> 
BL> More later...
BL> 
BL> Bertram