スカラの初期入力が再帰関数で認識されない

Question

これはの機能プログラミングで、です。

は、リストに別のリストがサブシーケンスとして含まれているかどうかをチェックします。たとえば、 List（1,2,3,4）は、List（1,2）、List（2,3）、およびList（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 

としての機能を使用した場合

しかし、それが値として格納され、正常に動作しています。質問は、私はヘルパー機能を必要としない場合、これを行う方法はありますか？

更新： @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

2番目の解決策も正しくありません。

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

@Dimaがコメントしたように、3番目のパラメータは一致シーケンスを開始したかどうかを追跡するのに役立ちます。また、一致シーケンスが開始されても失敗する場合は、検索を続行する必要があります。

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