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

Это работает, потому что:

• [3] соответствует x:xs как 3:[],
• [4, 1, 2, 3] соответствует как y:ys как 4:[1,2,3]
• 3/=4 поэтому sublist (x:xs) ys оценивается, что в конечном итоге истинно

след:

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] [1, 2, 3]
   = sublist [3] [2, 3]
   = sublist [3] [3]
   = sublist [] [] = True

  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 исчерпан, он сообщает "Ложь".

_1 _ это твой друг. С sublist в инструменте

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

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

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

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

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

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

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

Я думаю, где вы можете ошибиться, заключается в том, что (когда вы впервые написали функцию) вы предположили, что в своей проверке 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)

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

Хочу отметить, что часто можно избежать явной рекурсии, удалив ненужные элементы в начале списка с помощью 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