 senine -4 years ago 52
Scala Question

# recursive function not recognizing initial input in scala

This is an exercise in Functional Programming in Scala.

Implement hasSubsequence for
checking whether a List contains another List as a subsequence. For instance,
List(1,2,3,4) would have List(1,2), List(2,3), and List(4) as
subsequences, among others.

My first try is as below:

``````def go[A](l: List[A], sub:List[A]): Boolean =
(l, sub) match {
case (_,Nil) => true
case (Nil,_) => false
case (a :: as, x :: xs) if a == x => go(as, xs)
case (a :: as, _) => go(as, sub)
}                                                 //> go: [A](l: List[A], sub: List[A])Boolean
go(List(1,2,0), List(1,0))                        //> res6: Boolean = true
``````

This is wrong as in recursion the initial
`sub`
input was not stored (or not recognized) but replaced at each call.

However, if I used the function as a helper function

``````def hasSubsequence[A](l: List[A], sub: List[A]): Boolean ={
def go[A](l: List[A], a:List[A]): Boolean =
(l, a) match {
case (_,Nil) => true
case (Nil,_) => false
case (a :: as, x :: xs) if a == x => go(as, xs)
case (a :: as, _) => go(as, sub)
}
go(l,sub)
}                                                 //> hasSubsequence: [A](l: List[A], sub: List[A])Boolean
hasSubsequence(List(1,2,0), List(1,0))            //> res5: Boolean = false
``````

Then it is stored as a value and works fine. Question is, are there ways of doing this if I don't want any helper functions?

Update: per @jwvh the second one need to be corrected as below.

``````def hasSubsequence[A](l: List[A], sub: List[A]): Boolean ={
def go[A](l: List[A], a:List[A]): Boolean =
(l, a) match {
case (_,Nil) => true
case (Nil,_) => false
case (a :: as, x :: xs) if a == x => go(as, xs)
case (a :: as, _) if a == sub.head => go(a::as, sub)
case (a :: as, _) => go(as,sub)
}
go(l,sub)
}                                                 //> hasSubsequence: [A](l: List[A], sub: List[A])Boolean
hasSubsequence(List(1,2,0), List(1,0))            //> res0: Boolean = false
hasSubsequence(List(1,1,2,0), List(1,2))          //> res1: Boolean = true
`````` jwvh
Answer Source

Your 2nd solution isn't correct either.

``````hasSubsequence(List(1,1,2,0), List(1,2))  // res0: Boolean = false
``````

As @Dima has commented, a 3rd parameter would help keep track of whether we have started a match sequence or not. Also, we need to continue the search if the match sequence starts but fails.

``````def hasSubsequence[A]( l      : List[A]
, sub    : List[A]
, inMatch: Boolean = false ): Boolean =
(l, sub) match {
case (_,Nil) => true
case (Nil,_) => false
case (a :: as, x :: xs) if a == x =>
hasSubsequence(as, xs, true) || hasSubsequence(as, sub)
case _ =>
!inMatch && hasSubsequence(l.tail, sub)
}
``````

This is not tail recursive but it is recursive without a helper function.

``````hasSubsequence(List(1,2,0), List(1,0))    // res0: Boolean = false
hasSubsequence(List(1,2,0), List(1,2))    // res1: Boolean = true
hasSubsequence(List(1,2,0), List(2,0))    // res2: Boolean = true
hasSubsequence(List(1,1,2,0), List(2,1))  // res3: Boolean = false
hasSubsequence(List(1,1,2,0), List(1,2))  // res4: Boolean = true
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download
Latest added