3

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
thekevin
  • 51
  • 5
  • 2
    "it always throws a compiler error" should be followed by the full error message. Posting the errors you get is very useful to potential answerers. Please remember that for future questions. – chi May 20 '19 at 11:50

1 Answers1

4

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. :)

Will Ness
  • 70,110
  • 9
  • 98
  • 181