Haskell - Сопоставление с образцом и рекурсия

  sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]
= sublist [2, 3] [2, 4, 1, 2, 3]
= sublist [3] [4, 1, 2, 3]
= sublist [3] [4, 1, 2, 3]
= sublist (3:[]) (4:[1,2,3])     -- Since 3 /= 4, we take sublist (x:xs) ys
= sublist (3:[]) [1,2,3]
= sublist (3:[]) (1:[2,3])
= sublist (3:[]) [2,3]
= sublist (3:[]) (2:[3])
= sublist (3:[]) [3]
= sublist [] []
= True

sublist проверяет, равны ли главы списков. Если да, то удаляет их и продолжает (sublist xs ys). Если нет, то удаляет голову из второго списка (sublist (x:xs) ys). Таким образом "находится" следующая ассоциация:

 1 2 3
 | | |
 | | \-----\
 | |       |
 1 2 4 1 2 3

Другими словами, чтобы проверить sublist [1,2,3] ys для некоторого списка ys, он вытаскивает элементы из ys до тех пор, пока они не равны 1. Затем он вытаскивает элементы до тех пор, пока они не равны 2. Затем он вытаскивает элементы до тех пор, пока они не равны 3. Если [1,2,3] исчерпан, то он сообщает True; если ys исчерпан, то он сообщает False.

YuppieNetworking и sdcwc уже объяснили, как работает сопоставление. Итак, ваш подсписок ищет подсписок в том же смысле, что и подпоследовательность (не обязательно одинаковые элементы в строке, между ними может быть что угодно).

Я хочу отметить, что вы часто можете избежать явной рекурсии, чтобы удалить ненужные элементы из начала списка с помощью dropWhile .Также я хотел привести пример, как проверить, имеют ли два списка одинаковые префиксы (вам нужно это, чтобы проверить, содержит ли второй список элементы первого в строке).

Первый пример аналогичен вашей функции, он позволяет использовать промежуточные элементы, но использует dropWhile для удаления элементов перед ys :

-- Test:
-- map ("foo" `subListOf`) ["kungfoo", "f-o-o!", "bar"] == [True,True,False]

[] `subListOf` _ = True
(x:xs) `subListOf` ys =
  let ys' = dropWhile (/= x) ys     -- find the first x in ys
  in  case ys' of
      (_:rest) -> xs `subListOf` rest
      [] -> False

Второй пример выглядит для «плотного» подсписка:

-- Test:
-- map ("foo" `denseSubListOf`) ["kungfoo!", "-f-o-o-"] == [True,False]

[] `denseSubListOf` _ = True
_  `denseSubListOf` [] = False
xs `denseSubListOf` ys =
  let ps = zip xs ys in
  (length ps == length xs && all (uncurry (==)) ps) -- same prefix of xs and ys
  || xs `denseSubListOf` (tail ys)                  -- or search further

Обратите внимание, что для проверки того, что второй список содержит все первые, вначале я сравниваю элементы попарно (для этого я объединяю их вместе).

Проще объяснить на примере:

zip [1,2,3] [1,2,3,4,5]  -- gives [(1,1), (2,2), (3,3)], 4 and 5 are truncated
uncurry (==)             -- an equivalent of (\(a,b) -> a == b)
all                      -- gives True iff (uncurry (==)) is True for all pairs
length ps == length xs   -- this is to ensue that the right list is long enough

Думаю, вы ошиблись в том, что (когда вы впервые написали функцию) вы предположили, что в своей проверке x / = y = sublist (x: xs) ys вы (подсознательно ?) предполагал, что функция вернется к и повторно выполнит вашу функцию с хвостом исходного второго списка, а не с хвостом того фрагмента списка, который вы используете, если он не совпадает.

Одна приятная (и тревожная) вещь в Haskell - это то, насколько он смехотворно силен .

Например, вот как должно было выглядеть то, что вы хотели:

sublist   []     ys   = True
sublist   xs     []   = False
sublist (x:xs) (y:ys) |   x /= y  = False
                      | otherwise = sublist xs ys || sublist (x:xs) ys

, который проверит все части первого списка. «Официальное» определение функции (см. « isInfixOf » в вашей документации) содержит несколько дополнительных функций, которые в основном означают то же самое.

Вот другой способ записи, который мне кажется более «пояснительным»:

sublist [] ys = True
sublist xs [] = False
sublist xs ys =  (xs == take (length xs) ys) || sublist xs (tail ys)

Debug.Trace - ваш друг. С подсписком , оснащенным

sublist [] ys = trace ("A: [] "           ++ show ys) True
sublist xs [] = trace ("B: " ++ (show xs) ++ " []")   False
sublist (x:xs) (y:ys)
   | x == y = trace (info "C" "==")
              sublist xs ys
   | x /= y = trace (info "D" "/=")
              sublist (x:xs) ys
   where info tag op =
           tag ++ ": " ++ (show x) ++ " " ++ op ++ " " ++ (show y) ++
           "; xs=" ++ (show xs) ++ ", ys=" ++ show ys

, вы видите, что происходит, а именно, что он постоянно отбрасывает заголовок второго списка, пока не найдет совпадение:

*Main> sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]
C: 1 == 1; xs=[2,3], ys=[2,4,1,2,3]
C: 2 == 2; xs=[3], ys=[4,1,2,3]
D: 3 /= 4; xs=[], ys=[1,2,3]
D: 3 /= 1; xs=[], ys=[2,3]
D: 3 /= 2; xs=[], ys=[3]
C: 3 == 3; xs=[], ys=[]
A: [] []
True

Еще один инструмент, который поможет вам реализовать подсписок правильно - это Test.QuickCheck , библиотека, которая автоматически создает тестовые данные для использования при проверке указанных вами свойств.

Например, предположим, что вы хотите, чтобы подсписок обрабатывал xs и ys как наборы и определял, является ли первый подмножеством второго. Мы можем использовать Data.Set , чтобы указать это свойство:

prop_subsetOf xs ys =
  sublist xs ys == fromList xs `isSubsetOf` fromList ys
  where types = (xs :: [Int], ys :: [Int])

Здесь говорится, что подсписок должен быть эквивалентен определению справа. Префикс prop_ - это популярное соглашение для именования свойств тестов, используемых с QuickCheck.

Запуск также определяет случай отказа:

*Main> quickCheck prop_subsetOf 
*** Failed! Falsifiable (after 6 tests):                  
[0,0]
[0]