Haskell - Ghép mẫu và đệ quy

Question

Tôi mới sử dụng cả Haskell và lập trình. Câu hỏi của tôi về ràng buộc trong các hàm đệ quy, khớp với mẫu. Ví dụ, giả sử tôi có một hàm kiểm tra xem một danh sách cụ thể (x: xs) là một danh sách con của một danh sách khác, (y: ys). suy nghĩ ban đầu của tôi, sau các ví dụ trong sách giáo khoa của tôi, là:

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

này hoạt động trên dữ liệu thử nghiệm, ví dụ,

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

nơi tôi mong đợi nó đến thất bại. Tôi hy vọng nó sẽ thất bại, vì

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

tại thời điểm đó, tôi nghĩ, [3] = 3: [] sẽ được xuất hiện với (x: xs) trong sublist, và [4, 1, 2, 3 ] sẽ được khớp với (y: ys) trong danh sách con. Làm thế nào, sau đó, là danh sách phụ làm việc?

Chỉnh sửa: Nhờ mọi người ở đây, tôi nghĩ rằng tôi đã giải quyết được vấn đề của mình. Như đã nói, tôi đã ("vô thức") muốn danh sách phụ quay lại cho tôi. Sử dụng câu trả lời cuối cùng (BMeph) được đăng dưới dạng hướng dẫn, tôi đã quyết định tiếp cận vấn đề khác nhau, để giải quyết "vấn đề ràng buộc", tức là vấn đề "backtracking".

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

Nó đang làm việc vì:

• [3] là lần xuất hiện như x:xs như 3:[],
• [4, 1, 2, 3] là lần xuất hiện như y:ys như 4:[1,2,3]
• 3/=4 nên sublist (x:xs) ys được đánh giá, mà cuối cùng là True

theo dõi:

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 

kiểm tra sublist nếu người đứng đầu danh sách đều bình đẳng. Nếu có, thì nó sẽ loại bỏ chúng và tiến hành (sublist xs ys). Nếu không, nó sẽ xóa đầu khỏi danh sách thứ hai (sublist (x:xs) ys). Bằng cách này nó "thấy" liên kết sau:

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

Nói cách khác, để kiểm tra sublist [1,2,3] ys đối với một số danh sách ys nó bật các yếu tố từ ys miễn là họ không 1. Sau đó, nó bật yếu tố miễn là họ không 2. Sau đó, nó xuất hiện các yếu tố miễn là chúng không 3. Nếu [1,2,3] bị cạn kiệt, thì nó báo cáo Đúng; nếu ys bị cạn, báo cáo sẽ sai.

Answer 3

YuppieNetworking và sdcwc đã giải thích cách hoạt động của tính năng khớp. Vì vậy, sublist tìm kiếm danh sách phụ của bạn theo cùng nghĩa như subsequence (không nhất thiết phải là cùng một mục trong một hàng, có thể có bất kỳ điều gì ở giữa).

Tôi muốn lưu ý rằng bạn thường có thể tránh đệ quy rõ ràng để xóa các mục không cần thiết khỏi mặt trước của danh sách với dropWhile.Ngoài ra, tôi muốn đưa ra một ví dụ làm thế nào để kiểm tra xem hai danh sách có cùng các tiền tố (bạn cần điều này để kiểm tra xem danh sách thứ hai có chứa các mục của danh sách đầu tiên trong một hàng).

Ví dụ đầu tiên là tương tự như chức năng của bạn, nó cho phép cho các hạng mục ở giữa, nhưng nó sử dụng dropWhile để xoá các mục trước 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 

Ví dụ thứ hai sẽ cho một sublist "dày đặc":

-- 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 

Hãy lưu ý rằng danh sách thứ hai chứa tất cả phần đầu tiên trong phần đầu tôi so sánh các phần tử theo cặp (tôi nén chúng lại với nhau để thực hiện).

Nó là dễ dàng hơn để giải thích bằng ví dụ:

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 

Answer 4

Debug.Trace là bạn của bạn. Với sublist instrumented như

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 

bạn xem những gì đang xảy ra, cụ thể là nó liên tục ném đi người đứng đầu danh sách thứ hai cho đến khi nó tìm thấy một trận đấu:

*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

Một công cụ mà sẽ giúp bạn thực hiện sublist một cách chính xác là Test.QuickCheck, một thư viện tự động tạo dữ liệu thử nghiệm để sử dụng trong việc xác minh các thuộc tính mà bạn chỉ định. Ví dụ:

Ví dụ: giả sử bạn muốn sublist để xử lý xs và ys làm bộ và xác định xem tập trước có phải là tập hợp con thứ hai không. Chúng ta có thể sử dụng để xác định Data.Set khách sạn này:

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

này nói sublist nên tương đương với định nghĩa ở bên phải. Tiền tố prop_ là quy ước phổ biến để đặt tên thuộc tính thử nghiệm được sử dụng với QuickCheck.

Chạy nó cũng xác định một trường hợp thất bại:

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

Answer 5

Tôi nghĩ rằng, nơi bạn có thể hiểu lầm, đó là (khi bạn lần đầu tiên viết chức năng), bạn cho rằng trong tầm kiểm soát của bạn x /= y = sublist (x:xs) ys bạn (sub-ý thức?) giả định rằng chức năng sẽ backtrack và làm lại chức năng của bạn với đuôi của danh sách thứ hai ban đầu, không phải đuôi của bất kỳ phần nào của danh sách bạn đang sử dụng khi nó không khớp.

Một điều tốt đẹp (và đáng lo ngại) về Haskell chỉ là cách lố bịch mạnh mẽ.

Đối với một ví dụ, đây là cách những gì bạn muốn nên đã xem xét:

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

mà sẽ kiểm tra tất cả các phần của danh sách đầu tiên. Định nghĩa "chính thức" cho hàm (tra cứu "isInfixOf" trong tài liệu của bạn) có một vài hàm bổ sung về cơ bản có nghĩa là giống nhau.

Dưới đây là một cách khác để viết nó, mà trông "giải thích" cho mắt của tôi:

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