リストが別のリストのサブリストであるかどうかを確認してください。

Question

私は、あるリストが別のリストのサブリストであるかどうかをチェックする関数を書いています。私はこれを書いたが、うまくいかないが、私はこのようなものが必要だと思う。手伝ってくれてありがとう。

subList :: Eq a => [a] -> [a] -> Bool 
subList _ [] = False 
subList [] _ = True 
subList (x:xs) (y:ys) = 
    x == y = subList xs ys 
    otherwise = subList (x:xs) ys 

Answer 1

コードは動作していますが、マイナーな変更が必要です。他の人がコメントに述べたように、|パターンガードを含め、最初の関数呼び出しから=を削除する必要があります。ここでは、最後の3行はどのように見えるかです：

subList (x:xs) (y:ys) 
    | x == y = subList xs ys 
    | otherwise = subList (x:xs) ys 

これは、ほとんどの部分はあなたのコードを修正しますが、空のリスト[]がのサブリストであるので、あなたも、基本ケースsubList [] [] = Trueを追加する必要があります別の空のリスト[]は、[1]のように[1]のサブリストです。これらの変更を追加する

、あなたのコードは次のようになります。

subList :: Eq a => [a] -> [a] -> Bool 
subList [] [] = True 
subList _ [] = False 
subList [] _ = True 
subList (x:xs) (y:ys) 
    | x == y = subList xs ys 
    | otherwise = subList (x:xs) ys 

をいくつかの例では、呼び出します。

Prelude> subList [] [] 
True 
Prelude> subList [1] [1,2,3] 
True 
Prelude> subList [1] [4,2,3] 
False 
Prelude> subList [1] [] 
False 
Prelude> subList [1,2] [1,2] 
True 
Prelude> subList [1,2] [2,1] 
False 
Prelude> subList [1,2] [1,2,2,1] 
True 

しかし、このような呼び出しに問題彼らです：

Prelude> subList [1,3] [1,2,3] 
True 

は、

は、[1,3]のサブリストは[1,2,3]です。これは意図することができますが、そうでない場合は、アプローチを変更する必要があります。

もう一つのアプローチ：あなたの二つのリスト、xsとysについては

あなたが代わりに長さxsのサブリストにysを分割することができ、のがsubysを言う、とxsがsubysに存在するかどうかをチェックしましょう。これを行うにはn文字ごとにリストを分割するsplitAtを使用できます。ここでは例の機能は次のとおりです。

split_lists :: Int -> [a] -> [[a]] 
split_lists _ [] = [] 
split_lists n xs 
    | length first == n = first : restxs 
    | otherwise = restxs 
    where (first, rest) = splitAt n xs 
      restxs = split_lists n (tail first ++ rest) 

あなたがsplitAtを使用しない場合、あなたはこのような何か行うことができます：

split_lists :: Int -> [a] -> [[a]] 
split_lists _ [] = [] 
split_lists n xs = filter (\x -> length x == n) list 
    where list = take n xs : split_lists n (drop 1 xs) 

ように振る舞う：

Prelude> split_lists 3 [1,2,3,4,5,6,7,8,9,10] 
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]] 

その後、 anyを使って、サブリストに分割された2番目のリストに最初のリストが存在するかどうかを確認したり、通常の再帰を使用することができます。ここで

はanyを使った例である：ここでは

subList :: (Eq a) => [a] -> [a] -> Bool 
subList [] [] = True 
subList xs ys = any (==xs) subys 
    where subys = (split_lists (length xs) ys) 

は再帰を使った例です：次のようになりました振る舞い

subList :: (Eq a) => [a] -> [a] -> Bool 
subList [] [] = True 
subList xs ys = check_lists xs subys 
    where subys = (split_lists (length xs) ys) 

check_lists :: (Eq a) => [a] -> [[a]] -> Bool 
check_lists _ [] = False 
check_lists xs (y:ys) 
    | xs == y = True 
    | otherwise = check_lists xs ys 

：

Prelude> subList [] [] 
True 
Prelude> subList [1] [1,2,3] 
True 
Prelude> subList [1] [4,2,3] 
False 
Prelude> subList [1] [] 
False 
Prelude> subList [1,2] [1,2] 
True 
Prelude> subList [1,2] [2,1] 
False 
Prelude> subList [1,2] [1,2,2,1] 
True 
Prelude> subList [1,3] [1,2,3] 
False 
Prelude> subList [1,2] [0,1,2,3] 
True