CODEWITHSUNDEEP
haskell
Ohad
Ohad

Reputation: 1631

what does this function do in Haskell?

what does this function in Haskel do ?

I don't understand the way the recursion works here 

 f[]=[]
 f(x:xs)=x: [y|y <- f xs, x/=y]

Upvotes: 2

Views: 132

Answers (2)

meditans
meditans

Reputation: 586

f[]=[]
f(x:xs) = x : [y|y <- f xs, x/=y]

This function removes duplicates from a list. Here's how it works:

  • Base case, the list is empty, so it returns the empty list.
  • Otherwise you take the first element x, and assume (inductive hypothesis) that f xs gives you the list without duplicates. Now, the only thing you have to do is make sure that you don't insert x again. So, the list comprension means: take all the rest of the elements (which by inductive hypothesis are unique), but remove the x.

Does it feel right now?

ps. you can write the second clause also as: f(x:xs) = x : filter (/= x) (f xs)

Upvotes: 6

Santiclause
Santiclause

Reputation: 870

Seems to me that it eliminates any duplicate entries in the list.

Here's how it works:

f[] = [] means that, when the input is an empty list, the output will be an empty list.
Then, f(x:xs) = x: [y|y <- f xs, x/=y] uses what's called a list comprehension. It takes the head of the input list, and then appends the list comprehension.

The list comprehension reads like this: "y such that y is in f(xs), and y doesn't equal x"

So it's the list of elements in f(xs) that don't equal the head element.

Upvotes: 1

Related Questions