SortedSet fold type mismatch

Question

I have this code:

def distinct(seq: Seq[Int]): Seq[Int] =
  seq.fold(SortedSet[Int]()) ((acc, i) => acc + i)

I want to iterate over seq, delete duplicates (keep the first number) and keep order of the numbers. My idea was to use a SortedSet as an acc.

But I am getting:

Type mismatch:
Required: String
Found: Any

How to solve this? (I also don't know how to convert SortedSet to Seq in the final iteration as I want distinct to return seq)

p.s. without using standard seq distinct method

Online code

Answer 1

You shouldn't use fold if you try to accumulate something with different type than container (SortedSet != Int) in your case. Look at signature fold:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

it takes accumulator with type A1 and combiner function (A1, A1) => A1 which combines two A1 elements.

In your case is better to use foldLeft which takes accumulator with different type than container:

def foldLeft[B](z: B)(op: (B, A) => B): B

it accumulates some B value using seed z and combiner from B and A to B.

In your case I would like to use LinkedHashSet it keeps the order of added elements and remove duplicates, look:

import scala.collection.mutable

def distinct(seq: Seq[Int]): Seq[Int] = {
  seq.foldLeft(mutable.LinkedHashSet.empty[Int])(_ + _).toSeq
}
distinct(Seq(7, 2, 4, 2, 3, 0)) // ArrayBuffer(7, 2, 4, 3, 0)
distinct(Seq(0, 0, 0, 0)) // ArrayBuffer(0)
distinct(Seq(1, 5, 2, 7)) // ArrayBuffer(1, 5, 2, 7)

and after folding just use toSeq

be careful, lambda _ + _ is just syntactic sugar for combiner:

(linkedSet, nextElement) => linkedSet + nextElement

Answer 2

I would just call distinct on your Seq. You can see in the source-code of SeqLike, that distinct will just traverse the Seq und skip already seen data:

  def distinct: Repr = {
    val b = newBuilder
    val seen = mutable.HashSet[A]()
    for (x <- this) {
      if (!seen(x)) {
        b += x
        seen += x
      }
    }
    b.result
  }