CODEWITHSUNDEEP
haskellfilterlist-comprehensionhigher-order-functions
thekevin
thekevin

Reputation: 51

Custom Filter Function with Predicate using List Comprehension

I need to develop my own filter function similar to how filter works in Haskell but by using list comprehension and a predicate. So I would put lcFilter (>3) [1,2,3,4,5,6,10,444,3] in ghci and it would print all numbers greater than 3.

My code is based on a recursion example which I'm good at but I can't seem to convert to list comprehension. It seams no matter what I put in [x | x<-xs, p] it always throws a compiler error. I know the p part is wrong. I've tried ==p, xs==p and just about everything else I could think of. This makes me think some other part might be wrong but I'm really not sure.

Here is the code for my function lcFilter. I'm not sure if some or all of it is wrong so I'm posting the whole thing.

lcFilter :: (a -> Bool) -> [a] -> [a]
lcFilter _ [] = []
lcFilter p (x:xs) = [x | x<-xs, p]

If I type lcFilter (>3) [1,2,3,4,5] it should print [4,5] just like the standard Haskell filter function.

Upvotes: 3

Views: 677

Answers (1)

Will Ness
Will Ness

Reputation: 71065

It is as simple as 

      [x | x <- xs, p x]

Since p :: a -> Bool, and xs :: [a], to get a Boolean we need to apply the function to an argument; and by the list comprehension semantics we have x :: a.

The application rule of type inference is

            x :: a
          p   :: a -> b
         ---------------
          p x ::      b

And you don't need the pattern matching, list comprehension will take care of that.

So overall, it is

lcFilter :: (a -> Bool) -> [a] -> [a]
lcFilter p xs = [x | x <- xs, p]

List comprehensions are fun. One rule they follow is

    [ ... | x <- (xs            ++                ys), .... ]  ===
    [ ... | x <-  xs, ....  ]   ++   [ ... | x <- ys , .... ]

As a consequence, we also have

    [ ... | x <- ([y]           ++                ys), .... ]  ===
    [ ... | x <-  [y], .... ]   ++   [ ... | x <- ys , .... ]  ===
    [ ...{x/y} | ....{x/y}  ]   ++   [ ... | x <- ys , .... ]

where {x/y} means "replace x by y throughout". Thus, a list [a,b,...,n] is transformed by your definition into 

    [  a,           b,          ...,    n        ]             ===>
    [  a | p a] ++ [b | p b] ++ ... ++ [n | p n  ]

This can be further understood in terms of / serve as a nice illustration to / the concepts of monads, or of monoids, but we'll leave that for another day. :)

Upvotes: 4

Related Questions