CODEWITHSUNDEEP
listscalascala-collections
Aslan986
Aslan986

Reputation: 10324

Check for the presence of a sub-list

Can you provide me a performing (possibly idiomatic) way to check if a list A is a sublist of a given list B?

E.g.

isSubList(List(1,2), List(1,2,3,4)) // => true
isSubList(List(1,2), List(5,6,7,8)) // => false

Upvotes: 12

Views: 14676

Answers (3)

Ende Neu
Ende Neu

Reputation: 15783

One way would be to use forall and contains:

scala>   List(1, 2).forall(List(1, 2, 3, 4).contains)
res3: Boolean = true

scala>   List(1, 2).forall(List(5, 6, 7, 8).contains)
res4: Boolean = false

scala>   List(1, 2).forall(List(5, 6, 2, 9).contains)
res5: Boolean = false

Note that this approach doesn't consider ordering:

scala>   List(1, 2).forall(List(2, 1).contains)
res6: Boolean = true

Probably you could use also Sets and intersect, but I think this way is preferable.

Upvotes: 26

rarry
rarry

Reputation: 3573

One more solution:

def isSubList[A](short: List[A], long: List[A]): Boolean =
    long.tails exists (_.startsWith(short))

However, it would be much more efficient if lists were converted to streams first:

def isSubList[A](short: List[A], long: List[A]): Boolean = {
    val sLong = long.toStream
    val sShort = short.toStream
    sLong.tails exists (_.startsWith(sShort))
}

This way, not all tails have to be generated. Also startsWith is evaluated in a short circuit fashion

Upvotes: 2

grotrianster
grotrianster

Reputation: 2468

If order matters you can use containsSlice, which check whether collections contains a given sequence as a slice

def isSubList[A](l1:List[A], l2:List[A]) = l2.containsSlice(l1)

Upvotes: 23

Related Questions