Scala find duplicate in list

Question

So lets say i have a list like this:

List(Person(List(Name("Frank"), Age(50))),Person(List(Name("Peter"), Age(40))),Person(List(Name("Frank"), Age(20))))

How do i write a function that returns true if all names are unique, and false if there are duplicate names. E.g., this will return true:

List(Person(List(Name("Frank"), Age(50))),Person(List(Name("Peter"), Age(40))),Person(List(Name("Bob"), Age(20))))

And the upper example List will return false.

I have tried this:

sealed abstract class PersonFeatures
case class Person(list: List[PersonFeatures]) extends PersonFeatures
case class Age(num: Int) extends PersonFeatures
case class Name(value: String) extends PersonFeatures

val datlist = List(Person(List(Name("Frank"), Age(50))),Person(List(Name("Peter"), Age(40))),Person(List(Name("Frank"), Age(20))))

def findDoubles(checklist: List[Person]): List[Person] = {
  checklist.foldLeft(List[Person]()) { 
    case (uniquePersons, Person(List(name, age))) if uniquePersons.contains(Person(List(name, _))) => {
      throw new IllegalArgumentException("Double name found"); 
    }
    case (uniquePersons, person) => uniquePersons :+ person 
  }
}

val result = findDoubles(datlist)
println(result)

But it throws this error:

type mismatch;
 found   : List[Any]
 required: Playground.this.PersonFeatures

can you show us some code for your attempt at solving it yourself? — Seth Tisue
– Seth Tisue, Commented Mar 1, 2018 at 21:56
yes sure thing, here is my code: scastie.scala-lang.org/km7Y09ErRoiUPam8o1mkgA I'm quite new to Scala so it's probably totally butchered. So far i've tried just returning the list if nothing is wrong, but throwing an error if duplicates are found. — GSerum_
– GSerum_, Commented Mar 1, 2018 at 22:05
thanks — normally the expectation on Stack Overflow is that you put code in the question itself. (You can still edit your question after you initially posted it.) — Seth Tisue
– Seth Tisue, Commented Mar 1, 2018 at 22:34
And don't forget the primitive classes (here: Person, Age, Name), so that not every user, willing to help, has to retype them by inferring, how they look like, to make sure the code works not only in principle, but really. — user unknown
– user unknown, Commented Mar 1, 2018 at 22:49
@userunknown The OP posted a comment with a link to their code, including the Person, Name & Age classes. — Mike Allen
– Mike Allen, Commented Mar 1, 2018 at 23:10

Xavier Guihot · Accepted Answer · 2018-03-01 22:37:34Z

You can modify your code with the following to make it compile:

def findDoubles(checklist: List[Person]): List[String] = {
  checklist.foldLeft(List[String]()) { 
    case (uniquePersons, Person(List(Name(name), _))) if uniquePersons.contains(name) =>
      throw new IllegalArgumentException("Double name found");
    case (uniquePersons, Person(List(Name(name), _))) => name :: uniquePersons
}

}

But it seems quite complex for your requirements.

Here is an alternative:

case class Name(name: String)
case class Age(age: Int)
case class Person(smthg: List[Any])

val list = List(
  Person(List(Name("Frank"), Age(50))),
  Person(List(Name("Peter"), Age(40))),
  Person(List(Name("Frank"), Age(20))))

val names = list.flatMap {
  case Person(smthg) => smthg.collect { case Name(name) => name }
}

println(names)
> List(Frank, Peter, Frank)
println(names.distinct.length == result.length)
> false

First, we extract the names from all elements:

val names = list.flatMap {
  case Person(smthg) => smthg.collect { case Name(name) => name }
}

smthg.collect is applied on List(Name("Frank"), Age(50)). It filters elements which are of type Name (in order to filter out Age elements) and extract the actual age from Age(age).

Since smthg.collect outputs a List, we flatten it (list.flatMap {...}).

And thus we get this list: List(Frank, Peter, Frank)

Then, in order to find out if the list has duplicates, a simple way is to transform the list with distinct which only keep one instance of each element and compare it with the list produced just before:

names.distinct.length == result.length

Oh yeah that works, i made it into a function for simplicity, you are my hero of the day :)

acopeland · Accepted Answer · 2018-03-02 16:17:56Z

1

You can convert your list into a map of names to people, using the feature that such a map will have duplicate keys removed.

I agree with Mike Allen that you should not use Lists with different types, but instead should use a case class. You can then write a function as follows:

final case class Person(name: String, age: Int)

val datlist = List(Person("Frank", 50), Person("Peter", 40), Person("Frank", 20))

// Determine if people names are unique.
def haveUniqueNames(personList: List[Person]): Boolean = {

  val personMap = personList.map(person => person.name -> person).toMap
  (personMap.size == personList.size)
}

answered Mar 2, 2018 at 16:17

acopeland

764 bronze badges

Comments

Mike Allen · Accepted Answer · 2018-03-06 12:58:55Z

Firstly, from looking at your code, I have to point out that it's very bad practice to have different types in the same list. The PersonFeatures trait does nothing to help you here. I would recommend that you make a Person a case class and not a List of two completely different types (Name and Age). Aside from anything else, this will improve the structure of the data and simplify the solution. (If you must go this way, a library like Shapeless, which supports heterogeneous lists, is a far better approach than using a List[List[Any]].)

So, here's how I would take this:

import scala.annotation.tailrec

final case class Person(name: String, age: Int)

val datlist = List(Person("Frank", 50), Person("Peter", 40), Person("Frank", 20))

// Determine if people names are unique.
def haveUniqueNames(pl: List[Person]): Boolean = {

  // Helper function.
  @tailrec
  def headUnique(rem: List[Person], seen: Set[String]): Boolean = {

    // If we've reached the end of the list, return true; we didn't find a duplicate.
    if(rem.isEmpty) true

    // Otherwise, if the person at the head of the list has a name we've already seen,
    // return false.
    else if(seen.contains(rem.head.name)) false

    // Otherwise, add the head person's name to the set of names we've seen,
    // and perform another iteration starting with the next person.
    else headUnique(rem.tail, seen + rem.head.name)
  }

  // Start off with the full list and an empty set.
  headUnique(pl, Set.empty)
}

// Check if names are unique.
haveUniqueNames(datlist)

Or, alternatively, if efficiency isn't as important as brevity:

datlist.map(_.name).distinct.size == datlist.size

user unknown · Accepted Answer · 2018-03-01 23:55:53Z

Nobody knows, what Person and Age is. :)

Can you transfer this example to your case?

val la = List (List (1, 2), List (3, 2), List (1, 4))
// la: List[List[Int]] = List(List(1, 2), List(3, 2), List(1, 4))

val lb = List (List (1, 2), List (3, 2), List (4, 1))
// lb: List[List[Int]] = List(List(1, 2), List(3, 2), List(4, 1))

la.groupBy (_(0)).size == la.size 
// res229: Boolean = false

lb.groupBy (_(0)).size == lb.size 
// res230: Boolean = true

Ok. This can be abstracted. There is List of something, and depending on a predicate of these somethings, we want to find uniqueness.

def unique [T, A] (l: List[T], f: T => A): Boolean = {
    l.groupBy (element => f(element)).size == l.size 
}

For my example, T is a List of Integers (the inner lists) and A is just the Attribute, of T, which is selected by a function from T to A. If we group over the result of that function, the size should be unchanged, if the attribute is unique.

unique (lb, (l:List[Int]) => l(0))

Here the function is the Indexing into the inner List of ints. Now that we know the Person/Age/Name-definitions, we can test that too:

unique (datlist, (p:Person) => p.list(0))
// res254: Boolean = false

unique (datlist, (p:Person) => p.list(1))
// res255: Boolean = true

I'm a bit unhappy, that the solution doesn't reveal, that the names are not unique, while the ages are - not that the results are bogus, but that we access it with list index, not attribute name. But maybe there is a good reason, to write it like that, which is here off topic. But as far as I can tell, a Person with the attributes initialized in a different order would make this method fail. So what we really need is a method from Person to Name, not from Person to first PersonAttribute in Person.list.

This can be tried by pattern matching, but I'm not convinced of the Person design in general. Shall people without name really be possible? Person with 2 names? Or how should this be prevented from your Design?

However, ignoring the critique of the design, we can implement a verbose solution, which handles reordered Features (what I called Attributes):

unique (datlist, (p:Person) => p.list.filter (pf=> isFeatureByName (pf, "Name")))
//res259: Boolean = false1def isFeatureByName (pf: PersonFeatures, featurename: String) = (pf, featurename) match {
         case (Age (_), "Age")    => true
         case (Name (_), "Name")    => true
         case (Person (_), "Person")    => true
         case _ => false
     }

unique (datlist, (p:Person) => p.list.filter (pf=> isFeatureByName (pf, "Age")))
// res258: Boolean = true

unique (datlist, (p:Person) => p.list.filter (pf=> isFeatureByName (pf, "Name")))
// res259: Boolean = false

But how would this work with missing features, Persons without name or age, or possibly two names, two ages? I guess it is obvious, that this design needs a rethinking.

Collectives™ on Stack Overflow

Scala find duplicate in list

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related