Comparing lists - checking if one list is a segment of second one

Question

Good morning everyone (or good evening :)), I have problem with checking if one list is segment of second one. All elements of first list must be the first elements of second list.

For example

L1=[1,2,3,4]
L2=[3,4,5,6]
>false

L1=[1,2,3,4]
L2=[1,2,3,4,5,6,7,8]
>true

L1=[-1,-7,3,2]
L2=[1,2,3,4,5]
>false

I know it would be easy to use loop and then comparing elements, but i want to do it in functional way. I had idea, but it was not clever, to stick both lists (with zip, for example), then unzip it, chenge to set and compare if it has the same length then second list, but that method do not look good.

I'm new in Scala, so sorry for propably stupid question. I don't please for code, but for some advices! :)

Thanks guys!

This is a substring search problem. There are many algorithms to do so: http://stackoverflow.com/questions/3183582/what-is-the-fastest-substring-search-algorithm — tuxdna, Oct 23 '14 at 21:56
There is even a method on List that does just this: `startsWith` — Shadowlands, Oct 23 '14 at 21:59

score 0 · Answer 1 · answered Oct 23 '14 at 22:14

0

I did something like this. For now it works:

  def segment(L1: List[Int], L2: List[Int]) : Boolean = (L1, L2) match {
    case (h1::t1, h2::t2) if (h1 == h2) => segment(t1,t2)
    case(h1::t1, h2::t2) if (h1 != h2) => return false
    case nil => return true;
}

answered Oct 23 '14 at 22:14

Ojmeny

1,286
2
13
25

Just so you know: The result of this method is independent on the order in which you pass the lists (so segment(List(1,2), List(1,2,3)) == segment(List(1,2,3), List(1,2)) == true. If this is desierd, then the method is clean. Otherwise, you should add the case `(x::xs, Nil) => false`, stating that the left list should be shorter than or equal to the second. Also, if the question isn't about writing the algorithm yourself, then I'd suggest you have a look at `startsWith`, as the user Shadowlands commented. – Kulu Limpa Oct 23 '14 at 22:50

elm · Accepted Answer · 2014-10-24T06:14:40.407

An idiomatic approach to this; let

val a = (1 to 5).toList    
val b = (2 to 4).toList
val c = List(2,7,4)

Then

a.tails.collectFirst { case l if (l.startsWith(b)) => true }
res: Option[Boolean] = Some(true)

and

a.tails.collectFirst { case l if (l.startsWith(c)) => true }
res: Option[Boolean] = None

Here tails will create an iterator over each sublist from an item in the list to the last item in the list; startsWith will succeed only if our string of interest is the start of any sublist; collectFirst will deliver an Option[Boolean] at the first successful response from startsWith, else it will deliver a None that indicates no match.

In order to wrap up this idea, consider this implicit class,

implicit class RichList[A](val seg: List[A]) extends AnyVal {
  def isSegmentOf(l: List[A]) = {
    l.tails.collectFirst { case t if (t.startsWith(seg)) => true }
  }
}

Thus

b.isSegmentOf(a)
res: Option[Boolean] = Some(true)

c.isSegmentOf(a)
res: Option[Boolean] = None

Comparing lists - checking if one list is a segment of second one

2 Answers2