How to write a recursion function in haskell

Question

How can I write a function in Haskell which takes a list and a number and it removes all the elements greater than that number and returns the list.

remove [5, 4, 3, 9, 1 ] 5 should return [5,4,3,1]

I wrote the following method which is becoming infinite loop some where when it hits the greater than the given number. I am getting out [5,4,3 and then program is not ending.

remove l1 x = if (null l1 == True)
                then l1
                else if (head l1 > x)
                       then remove (drop 0 l1) x
                       else ((head l1) : remove (tail l1) x)

This is first time I am trying Haskell programs, please suggest me what I am doing wrong here.

Thanks

Answer 1

Well, you're off to a decent start, but it's important to note that you are not taking the most "Haskell" approach to this.

Let me show you a few different approaches to this problem:

Approach 1: Recursive Function

First and foremost, we could write a recursive function (as you are) to solve this.

To do this we first accommodate for a base-case (one that will not, under normal circumstances, allow for an infinite loop). This should work:

remove [] _ = []

This simply says that if we are to remove elements from an empty list, we end up with an empty list. It's that simple. The _ means that we don't care what value x is.

Now we must define our other cases. For this, I would use guards (I'm sure there are other approaches, base-case added also for completion):

remove [] _ = []
remove (x:xs) y
 | x > y     = remove xs y
 | otherwise = x : remove xs y

So, the first line (remove (x:xs) y) is saying that our function will take a list (where x is the head/first value and xs is the rest).

The second line is saying that, if x is greater than y, consider the rest of the elements, and we don't consider x to be a part of our final solution.

The third line (otherwise catches all cases if hit, and is like an else in an if/elseif/else conditional block in other languages). If we get to this point, we know that it is not true that x > y so we consider the rest of our values (xs) and we include x, but we're done with x for now.

Now, this approach works decently, but there is a simpler one:

Approach 2: List Comprehensions

Using list comprehensions we can build a very simple, powerful solution:

remove xs y = [x | x <- xs, not (x > y)]

If you have ever studied set-theory (specifically set-builder notation) this should look oddly familiar to you. Let's walk through what each part means.

• [...] - Something in brackets simply means we are constructing a list

• x |... - Means that our list will contain xs such that (the | means "such that")...

• x <- xs, - x is an element of xs and (the comma means "and")...

• not (y > x) - It is not true that y is greater than x

As you can see, this second approach almost exactly imitates your problem's description. This is truly the power of Haskell, words and abstraction tend to, nearly, map directly into Haskell code.

Approach 3: Using filter

As the below comment states a third alternative would be to define it as such:

remove y = filter (<=y)

Where filter will only keep elements that are less than or equal to y. (Credit to Daniel Wagner for this approach).

Answer 2

You can use pattern matching in function args and filter with guards:

remove []    x = []
remove (h:t) x | h > x = remove t x
               | otherwise = h : remove t x

Also you can use function filter, it do what you need:

remove l x = filter (<= x) l