senine 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

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