不识别scala中初始输入的递归函数

Question

这是Scala中函数式编程的一个练习。

实现hasSubsequence，以检查列表是否包含另一个列表作为子序列。例如，列表(1，2，3，4)将列表(1，2)，列表(2，3)和列表(4)作为子序列，等等。

我的第一次尝试如下：

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

这是错误的，因为在递归中，初始sub输入没有存储(或未识别)，而是在每次调用时被替换。

但是，如果我将该函数用作辅助函数

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

然后将其存储为一个值，并运行良好。问题是，如果我不想要任何助手函数，有什么方法可以这样做吗？

更新： per @jwvh第二个需要更正如下。

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 1

你的第二个解决方案也不正确。

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

正如@Dima所评论的，第三个参数将有助于跟踪我们是否已经启动了匹配序列。此外，如果匹配序列开始但失败，我们需要继续搜索。

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)
  }

这不是尾递归，而是没有助手函数的递归。

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

Answer 2

def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
    def isPrefix(pref: List[A], xs: List[A]): Boolean = (pref,xs) match {
      case (Cons(h1,t1),Cons(h2,t2)) => h1 == h2 && isPrefix(t1,t2)
      case (Nil,_) => true
      case _ => false
    }

    sup match {
      case Cons(h, t) => isPrefix(sub,sup) || hasSubsequence(t,sub)
      case _ => false
    }
  }