Scala: get list with the first element of three lists not repeating any element

Question

I have a scala List[List[Person]] with the following elements:

Person(Antonio)
Person(Maria)
Person(Joao)

Person(Antonio)
Person(Susana)
Person(Laura)

Person(Maria)
Person(Manuel)
Person(Joao)
Person(Laura)

How can I get a list with the first element of each list not repeated? Like this:

Person(Antonio)
Person(Susana)
Person(Maria)

It would be easy to do with var's, but I want to do it functionally.

OlivierBlanvillain · Accepted Answer · 2017-05-28T00:14:28.370

2

val l: List[List[Person]] = ...

l.foldLeft(List.empty[Person]) { case (acc, el) => 
  el.find(x => !acc.contains(x)).fold(acc)(acc.::)
}

edited May 28 '17 at 00:14

answered May 27 '17 at 23:45

OlivierBlanvillain

7,701
4
32
51

This is not quite right. Instead of returning `Person(Antonio)/Person(Susana)/Person(Maria)` it is returning `Person(Antonio)/Person(Maria)` – Duarte M. May 27 '17 at 23:49
I see, I didn't get that from your description... Updated – OlivierBlanvillain May 28 '17 at 00:14
1

Folding on an option is a bit unusual, no? Maybe `acc ++ el.find(x => !acc.contains(x)).toList`? – Joe K May 28 '17 at 00:37
Joe K's idea also works. With Olivier's solution I had to reverse the resulting list in order to get the right order, with Joe's tweak I don't have to do that. – Duarte M. May 28 '17 at 01:09
Remarkable solution. I would only add that the outer `foldLeft` could also be replaced with `fold` for potentially better [parallelization](https://stackoverflow.com/questions/16111440/scala-fold-vs-foldleft). – Leo C May 28 '17 at 01:17
@JoeK Prepending an element to a list takes linear time, appending and reversing at the end takes constant amortized time. – OlivierBlanvillain May 28 '17 at 07:11
@LeoC In this case using foldRight instead of foldLeft would not yield the same result, this problems seems inherently not parallelizable. – OlivierBlanvillain May 28 '17 at 07:14
"Folding on an option is a bit unusual, no". No. Not IMO. – The Archetypal Paul May 28 '17 at 18:41

score 0 · Answer 2 · answered May 28 '17 at 00:21

I was able to achieve this with recursion and foldLeft:

val allLists: List[List[Person]] = ...

allLists.foldLeft(List.empty[Person]){ case(outputList, list) =>
  def loop(innerList: List[Person], newPerson: Person): Person = {
    if(innerList.isEmpty) newPerson
    else if(!outputList.contains(innerList.head)) newPerson
    else loop(innerList.tail, innerList.tail.head)
  }

  outputList :+ loop(list, list.head)
}

Scala: get list with the first element of three lists not repeating any element

2 Answers2