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?
I won't do your homework for you, but hope, this will help.
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).
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!
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?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.
.sortBy, by in the world would you not be able to just do .distinct in the first place??? Or, at least, throw things into a Set?
.distinct()? It eventually depends. Implementing the .sortBy is a little bit overkill. :(