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

Question

Я новичок в Haskell и программировании. Мой вопрос о связывании в рекурсивных функциях с сопоставлением с шаблоном. Например, предположим, что у меня есть функция, которая проверяет, является ли данный список (x: xs) подсписком другого списка (y: ys). Моя первоначальная мысль, следуя примерам из моего учебника, была:

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

Это работает с тестовыми данными, например,

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]

, где я ожидал, что это не удастся. Я ожидаю, что это не удастся, так как

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]
   = sublist [2, 3] [2, 4, 1, 2, 3]
   = sublist [3] [4, 1, 2, 3]

В этот момент, как я думал, [3] = 3: [] будет сопоставлено с (x: xs) в подсписке, а [4, 1, 2, 3] будет сопоставлено с (y: ys) в подсписок. Как тогда работает подсписок?

Редактировать: Спасибо всем здесь, я думаю, что я решил свою проблему. Как уже отмечалось, я («подсознательно») хотел, чтобы подсписок вернулся для меня. Используя последний ответ ( BMeph ), опубликованный в качестве руководства, я решил по-другому подойти к проблеме, чтобы решить «проблему привязки», то есть проблему «возврата».

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

-- subseq' decides whether the list bound to (x:xs) = M is a prefix of the list
-- bound to L = (y:ys); it recurses through L and returns a Bool value. subseq
-- recurses through M and L, returning a disjunction of Bool
-- values. Each recursive call to subseq passes M and ys to subseq', which
-- decides whether M is a prefix of the **current list bound to ys**.

   let subseq' :: (Eq a) => [a] -> [a] -> Bool
       subseq' [] _ = True
       subseq' _ [] = False
       subseq' (x:xs) (y:ys) = (x == y) && subseq' xs ys
          in subseq' (x:xs) (y:ys) || subseq (x:xs) ys

Answer 1

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

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

trace:

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

Answer 2

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

Answer 3

Debug.Trace ваш друг. С 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]

Answer 4

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

Answer 5

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