CODEWITHSUNDEEP
scala
B.Mr.W.
B.Mr.W.

Reputation: 19648

Scala Use :: to removeDuplicates

I am reading the book programming in Scala from Martin O. and there is one example there to remove duplicates totally confused me: 

def removeDuplicates[A](xs: List[A]): List[A] = {
   if (xs.isEmpty) xs
   else
       xs.head :: removeDuplicates(
           xs.tail filter (x => x != xs.head)
       )
}

println(removeDuplicates[String](List("a", "a", "b", "a", "c")))

gives me: 

List(a,b,c)

I know that .head will give you the very first element of the List while .tail give you the rest of the List. And I can understand that xs.tail filter (x => x != xs.head) will return a list containing the elements which don't equal to the head.

My Google search leads me to this cons operator however, I am still having a hard time mapping Martin's words to this example. And anyone help me understand how this :: works in this function?

Upvotes: 1

Views: 83

Answers (2)

JimN
JimN

Reputation: 3150

A peculiarity in Scala is that operators ending in : (colon) are right-associative, and they are dispatched to the object on the right, with the parameter being on the left. For example: a :: list (infix notation) is equivalent to list.::(a) (method notation).

Have a look at the documentation for :: (cons). It constructs a linked list from an element and another list. Note that a :: b :: c :: Nil is equivalent to List(a, b, c), but note that the construction is happening from right to left, as Nil.::(c).::(b).::(a).

The example you gave uses recursion, which is based on a base case and an inductive case. The base case says that an empty list has no duplicates. The inductive case says that, assuming you have a removeDuplicates method which can remove all duplicates from a list, you can construct a new (sometimes larger) duplicate-free list by adding a value to the beginning, as long as you've remove that value from the remainder of the list first.

Upvotes: 1

Carcigenicate
Carcigenicate

Reputation: 45806

This is a very common pattern in functional programming.

Realize that removeDuplicates evaluates to a list, which the cons operator takes on its right side. The end result is a list where it's tail doesn't contain its head.

Every recurse, we add the head of the remaining list to the new list that we're constructing using the cons operator. We see if the current head exists in the rest of the list, and filter them out.

Look up what a the map method is. If you get how it works, this should click. They aren't exactly the same, but it involves building a list using the cons operator.

Upvotes: 0

Related Questions