2

特定のリストが別のリストのサブシーケンスであるかどうかを確認しようとしています:

true を返すリストの例を次に示します。

subseq "" "w"
subseq "w" "w"
subseq "ab" "cab"
subseq "cb" "cab"
subseq "aa" "xaxa"
not (subseq "aa" "xax")
not (subseq "ab" "ba")

私はこれに来ましたが、場合によっては間違った結果が得られます

subseq :: Eq a => [a] -> [a] -> Bool
subseq [] [] = True
subseq [] ys = True
subseq xs [] = False
subseq (x:xs) (y:ys) = x == y || subseq xs ( 1 `drop` ys )
4

3 に答える 3

7

高レベルと低レベルの 2 つです。最初に高レベル:

再帰的なケースが正しくありません。英語では、最初の文字が一致する場合、またはリスト 1 の最初の文字を除くすべての文字が 2 番目のリストの最初の 2 文字を除くすべての文字のサブシーケンスである場合、空でないリストは別の空でないリストのサブシーケンスであると記述しました。これは明らかに正しくありません。たとえば、最初の文字が一致していても「aaa」は「abc」のサブシーケンスではなく、「b」は「b」のサブシーケンスであっても「db」は「cab」のサブシーケンスではないためです。 .

その最後のケースへのより良いアプローチは、英語で次のように表現することです。リスト 2 の最初の文字が一致せず、リスト 1 はリスト 2 の最初の文字を除くすべての文字のサブシーケンスです。」

これは宿題のように見えるので、それを Haskell コードに変換するのはあなたに任せます。

低レベル: コード片

subseq (x:xs) (y:ys) = x == y || subseq xs ( 1 `drop` ys )

あなたが思っていることをしません。ys最初のリストを除く 2 番目のリストのすべての要素がすでに含まれています。それ以上の要素を削除する必要はありません。また、最初のケース ( subseq [] [] = True) は、2 番目のケースに引っかかるので不要ですが、大したことではありません。

于 2012-11-04T16:57:33.533 に答える
1

これはそれを行います：

import Control.Monad

subseq a b = elem a . filterM (\x-> [True,False]) $ b

（SO / sacundimに感謝します！）。

jacobm's answerからアドバイスを受けると、

subseq [] ys = True
subseq xs [] = False
subseq (x:xs) (y:ys) = x == y && (....) 
                    || x /= y && subseq (....) (....)

これはガード付きで書かれた方が良いです。

subseq (x:xs) (y:ys) 
             | x == y    = (....) 
             | otherwise = subseq (....) (....)

最初のコードは、コードではなく仕様と見なす方が適切です。非常に非効率的です。それを改善するために、融合 elemを試すことができますfilterM- これは次のように実装されている可能性があります

filterM p xs = liftM concat $ sequence [ do {t<-p x; return [x|t]} | x<-xs]

となることによって

elem xs $ filterM (\x-> [True,False]) ys                               ==
elem xs $ map concat $ sequence [ [[y|t] | t<-[True,False]] | y<-ys]   ==
elem xs $ map concat $ sequence [ [[y],[]] | y<-ys]                    ==

not.null $ filter (match [[x]|x<-xs]) $ sequence [ [[y],[]] | y<-ys]
  where
    match [] _ = True
    match _ [] = False
    match ([x]:t) ([y]:s) | x==y = match t s
    match q       (_:s)          = match q s                           == 

not.null $ [()|r<-sequence [ [[y],[]] | y<-ys], match [[x]|x<-xs] r]   ==

match2 xs ys
  where
    match2 [] _ = True
    match2 _ [] = False
    match2 (x:t) (y:s) | x==y = match2 t s
    match2 q     (_:s)        = match2 q s
于 2012-11-05T09:01:47.843 に答える