CODEWITHSUNDEEP
scalalistrecursionpattern-matching
Michael
Michael

Reputation: 33

How can I remove duplicates from a list in Scala with pattern matching?

As homework i have to write a function that will remove duplicates from a list. It should be recursive and with pattern matching. I am not allowed to use list functions like head,tail,contains,etc... .
For sorted lists i came up with this solution: 

def remove(u:List[Int]):List[Int] = {
  u match { case Nil => u
  case hd::hd2::tl => if(hd == hd2) remove(hd2::tl) else hd :: remove(hd2::tl)
  case hd::tl => hd :: remove(tl)
  }
}

How can i do it for unsorted lists?

Upvotes: 3

Views: 1162

Answers (2)

akuiper
akuiper

Reputation: 214957

I would probably go about sorting the list firstly so that we can apply the O(n) complexity pattern matching method but in order to keep the order you will need to index the list so that you can recover the order later, this can be done with the zipWithIndex method. And also since the data type changes from List[Int] to List[(Int, Int)], you will need to define another recursive remove function inside the original one:

def remove(u: List[Int]): List[Int] = {
    val sortedU = u.zipWithIndex.sortBy{ case (x, y) => x}
    def removeRec(su: List[(Int, Int)]): List[(Int, Int)] = {
        su match {
            case Nil => su
            case hd :: Nil => su
            case hd :: hd2 :: tail => {
                if (hd._1 == hd2._1) removeRec(hd2 :: tail)
                else hd :: removeRec(hd2 :: tail)
            }
        }
    }
    removeRec(sortedU).sortBy{case (x, y) => y}.map{ case (x, y) => x}
}

val lst = List(1,2,3,1,3,3)

remove(lst)
// res51: List[Int] = List(2, 1, 3)

Note: This follows OP's pattern and is not tail-recursive. And if you want a tail recursive version, you can follow @Dima's nice explanation.

Upvotes: 1

Dima
Dima

Reputation: 40500

I won't do your homework for you, but hope, this will help.

  1. You want to make your function tail-recursive. That means that the recursive call appears in the very last position of the function, so that the jvm can clear up the previous call from the stack before invoking it (it makes it execute very much like a loop, without requiring additional space on stack). In your original solution it is statements like this, that make it not tail-recursive: hd :: remove(tl): you have to invoke the recursive call, and then prepend hd to its result. The then part breaks the idea of tail recursion, because jvm has to remember on stack the place to return to after the recursive call is finished.

This is typically avoided by carrying the final result of the function through the recursion as an argument:

  def remove(u: List[Int], result: List[Int] = Nil): List[Int] = u match {
     case Nil => result
     case a :: b :: tail if a == b => remove(b :: tail, result)
     case head :: tail => remove(tail, head :: result) 
  }

(Note, that both recursive invocations here are in the tail position - there is nothing left to do after the call returns, so the previous entry can be cleared from the stack prior to invoking the recursion).

  1. You need another recursive function - contains - that tells whether a given element is contained in a list. Once you have that, just replace the second case clause above with something like 

    case head :: tail if contains(head, result) => remove(tail, result)

and your job is done!

  1. If you want to preserve the original order of elements of the list, you will need to reverse it afterwards (replace case Nil => result with case Nil => result.reverse) ... If you are not allowed to use .reverse here too, that's going to be another nice exercise for you. How do you reverse a list (tail-)recursively?

Upvotes: 6

Related Questions