Data.Map
Danh sách liên kết (còn có tên gọi “từ điển”) là những danh sách được dùng để lưu những cặp khóa-giá trị, hay khóa-trị, trong đó thứ tự không thành vấn đề. Chẳng hạn, ta có thể dùng danh sách liên kết để lưu trữ các số điện thoại, trong đó số điện thoại là giá trị và tên người là khóa. Ta không quan tâm đến thứ tự lưu trữ thế nào, chỉ cần lấy được đúng số điện thoại của từng người.
Cách tự nhiên nhất để biểu thị danh sách liên kết trong Haskell là có một danh sách các cặp. Thành phần thứ nhất trong cặp chính là khóa, còn thành phần thứ hai là giá trị. Sau đây là ví dụ một danh sách liên kết chứa các số điện thoại:
phoneBook =
[("betty","555-2938")
,("bonnie","452-2928")
,("patsy","493-2928")
,("lucille","205-2928")
,("wendy","939-8282")
,("penny","853-2492")
]Dù cho cách viết thụt đầu dòng như thế này có vẻ hơi lạ, song đây chỉ là một danh sách các cặp. Nhiệm vụ thường gặp nhất khi xử lý danh sách liên kết là tra tìm giá trị theo khóa. Ta hãy lập ra một hàm để tra tìm giá trị dựa theo khóa nào đó cho trước.
findKey :: (Eq k) => k -> [(k,v)] -> v findKey key xs = snd . head . filter (\(k,v) -> key == k) $ xs
Khá đơn giản. Hàm này nhận vào một khóa và một danh sách, lọc danh sách để chỉ giữ lại những khóa nào khớp, rồi lấy cặp khóa-trị khớp đầu tiên và trả lại giá trị. Nhưng điều gì sẽ xảy ra nếu khóa ta cần tìm không có trong danh sách liên kết? Hừm. Ở đây, nếu khóa không có trong danh sách liên kết, rút cục ta sẽ lấy phần tử đầu của một danh sách rỗng, và gây ra lỗi thực thi. Tuy nhiên, ta cần tránh cho chương trình đổ vỡ, vì vậy hãy dùng kiểu dữ liệu Maybe. Nếu tìm thấy khóa, hãy trả lại Nothing. Nếu tìm thấy, ta sẽ trả lại Just something, trong đó something là giá trị ứng với khóa đó.
findKey :: (Eq k) => k -> [(k,v)] -> Maybe v
findKey key [] = Nothing
findKey key ((k,v):xs) = if key == k
then Just v
else findKey key xsHãy nhìn vào lời khái báo kiểu. Nó nhận vào một khóa có thể so sánh [bằng hoặc khác] được, cùng một danh sách liên kết, rồi có thể tạo ra một giá trị. Nghe cũng hợp lý.
Đây là một ví dụ giáo khoa về hàm đệ quy hoạt động trên một danh sách. Có đủ cả điều kiện biên, việc chia danh sách thành đầu và phần đuôi, và các lời gọi đệ quy. Đây là dạng mẫu gấp có tính kinh điển, vì vậy ta sẽ xem cách lập nó bằng hàm gấp như thế nào.
findKey :: (Eq k) => k -> [(k,v)] -> Maybe v findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing
foldr, nhưng sẽ mất chút thời gian hình dung để đọc được cấu trúc đệ quy tường minh.ghci> findKey "penny" phoneBook Just "853-2492" ghci> findKey "betty" phoneBook Just "555-2938" ghci> findKey "wilma" phoneBook Nothing
Chạy đẹp mê ly! Nếu ta tìm đuợc số điện thoại của cô gái, ta sẽ có Just số điện thoại, còn không thì Nothing.
Ta vừa tạo lập hàm lookup từ Data.List. Nếu muốn tìm giá trị tương ứng với một khóa, ta phải duyệt suốt toàn bộ những phần tử của danh sách đến khi tìm thấy. Module Data.Map có những danh sách liên kết chạy nhanh hơn (vì bản chất chúng được lập theo cấu trúc cây) và cũng có nhiều hàm ứng dụng hơn. Từ giờ trở đi, ta sẽ coi rằng đang làm việc với ánh xạ (map) thay vì các danh sách liên kết.
Vì Data.Map xuất khẩu các hàm có tên xung đột với những hàm trong Prelude và Data.List, nên ta sẽ viết lệnh nhập chọn lọc.
import qualified Data.Map as Map
Đặt lệnh nhập nói trên vào trong một mã lệnh chương trình rồi tải mã lệnh đó từ GHCI.
Hãy tiếp tục và xem rằng Data.Map có gì cho chúng ta! Sau đây là tóm tắt cơ bản về các hàm trong đó.
Hàm fromList nhận vào một danh sách liên kết (dưới dạng danh sách) rồi trả về ánh xạ với cùng những mối liên kết đó.
ghci> Map.fromList [("betty","555-2938"),("bonnie","452-2928"),("lucille","205-2928")]
fromList [("betty","555-2938"),("bonnie","452-2928"),("lucille","205-2928")]
ghci> Map.fromList [(1,2),(3,4),(3,2),(5,5)]
fromList [(1,2),(3,2),(5,5)]Nếu có những khóa trùng nhau trong trong danh sách ban đầu, thì những thứ lặp thừa sẽ được bỏ đi. Sau đây là dấu ấn kiểu của fromList
Map.fromList :: (Ord k) => [(k, v)] -> Map.Map k v
Nó nói rằng hàm này nhận vào một danh sách những cặp kiểu k và v rồi trả về một ánh xạ trong đó chiếu các khóa có kiểu k đến kiểu v. Lưu ý rằng khi ta lập các danh sách liên kết từ danh sách thường, thì các khóa chỉ cần so sánh đồng nhất [bằng hoặc khác] được (nghĩa là kiểu của chúng thuộc về lớp Eq) nhưng trong trường hợp này thì chúng còn phải so sánh được. Đó là một điều kiện bắt buộc trong module Data.Map. Nó yêu cầu các khóa phải có thứ tự thì mới sắp xếp chúng lên cây được.
Bạn nên luôn dùng đến Data.Map cho các liên kết khóa-trị trừ khi bạn có trong tay các khóa không thuộc về lớp Ord.
empty biểu thị một ánh xạ rỗng. Nó không nhận đối số nào, và chỉ trả lại một ánh xạ rỗng.
ghci> Map.empty fromList []
insert nhận vào một khóa, một giá trị và một ánh xạ rồi trả về một ánh xạ mới gần giống ánh xạ cũ, chỉ khác là chèn thêm khóa và giá trị vào.
ghci> Map.empty fromList [] ghci> Map.insert 3 100 Map.empty fromList [(3,100)] ghci> Map.insert 5 600 (Map.insert 4 200 ( Map.insert 3 100 Map.empty)) fromList [(3,100),(4,200),(5,600)] ghci> Map.insert 5 600 . Map.insert 4 200 . Map.insert 3 100 $ Map.empty fromList [(3,100),(4,200),(5,600)]
Ta có thể tự lập riêng fromList bằng cách dùng ánh xạ rỗng, insert và một hàm gấp. Nhìn này:
fromList' :: (Ord k) => [(k,v)] -> Map.Map k v fromList' = foldr (\(k,v) acc -> Map.insert k v acc) Map.empty
Đây là một phép gấp khá trực tiếp. Ta bắt đầu bằng một ánh xạ rỗng rồi gấp nó từ phía phải, bằng việc dần chèn các cặp khóa-trị vào danh sách tích lũy.
null kiểm tra xem liệu một ánh xạ có rỗng hay không.
ghci> Map.null Map.empty True ghci> Map.null $ Map.fromList [(2,3),(5,5)] False
size báo lại kích cỡ của ánh xạ.
ghci> Map.size Map.empty 0 ghci> Map.size $ Map.fromList [(2,4),(3,3),(4,2),(5,4),(6,4)] 5
singleton nhận vào một khóa và một giá trị rồi tạo ra một ánh xạ chỉ có đúng một phần tử.
ghci> Map.singleton 3 9 fromList [(3,9)] ghci> Map.insert 5 9 $ Map.singleton 3 9 fromList [(3,9),(5,9)]
lookup hoạt động giống như Data.List lookup, chỉ khác là nó hoạt động với ánh xạ. Hàm này trả lại Just something nếu tìm thấy something tương ứng với khoá và Nothing nếu không tìm thấy gì.
member là một vị từ nhận vào một khóa và một ánh xạ rồi báo lại xem liệu khóa có nằm trong ánh xạ hay không.
ghci> Map.member 3 $ Map.fromList [(3,6),(4,3),(6,9)] True ghci> Map.member 3 $ Map.fromList [(2,5),(4,5)] False
map và filter hoạt động rất giống với các dạng tương đương dùng trong danh sách.
ghci> Map.map (*100) $ Map.fromList [(1,1),(2,4),(3,9)] fromList [(1,100),(2,400),(3,900)] ghci> Map.filter isUpper $ Map.fromList [(1,'a'),(2,'A'),(3,'b'),(4,'B')] fromList [(2,'A'),(4,'B')]
toList là hàm nghịch đảo của fromList.
ghci> Map.toList . Map.insert 9 2 $ Map.singleton 4 3 [(4,3),(9,2)]
keys và elems lần lượt trả lại danh sách các khóa và giá trị. keys là dạng tương đương của map fst . Map.toList còn elems tương đương với map snd . Map.toList.
fromListWith là một hàm nhỏ rất hay. Nó hoạt động giống như fromList, chỉ khác là nó không bỏ đi những khóa trùng lặp thừa, thay vào đó là dùng một hàm được cung cấp để quyết định xem nên làm gì với những khóa trùng lặp đó. Giả sử rằng một cô gái có thể có nhiều số điện thoại và ta có một danh sách liên kết được lập nên như sau.
phoneBook =
[("betty","555-2938")
,("betty","342-2492")
,("bonnie","452-2928")
,("patsy","493-2928")
,("patsy","943-2929")
,("patsy","827-9162")
,("lucille","205-2928")
,("wendy","939-8282")
,("penny","853-2492")
,("penny","555-2111")
]Bây giờ nếu chỉ dùng fromList để đưa số liệu trên vào một ánh xạ, thì ta sẽ đánh mất một vài số điện thoại! Vì vậy ta sẽ làm như sau:
phoneBookToMap :: (Ord k) => [(k, String)] -> Map.Map k String phoneBookToMap xs = Map.fromListWith (\number1 number2 -> number1 ++ ", " ++ number2) xs
ghci> Map.lookup "patsy" $ phoneBookToMap phoneBook "827-9162, 943-2929, 493-2928" ghci> Map.lookup "wendy" $ phoneBookToMap phoneBook "939-8282" ghci> Map.lookup "betty" $ phoneBookToMap phoneBook "342-2492, 555-2938"
Nếu tìm thấy một khóa trùng lặp thì hàm sẽ dùng đến hàm được truyền vào, để kết hợp giá trị của các khóa đó vào một giá trị khác. Ta cũng có thể bắt đầu bằng việc chuyển các giá trị trong danh sách liên kết thành các danh sách một phần tử rồi mới dùng ++ để kết hợp các con số.
phoneBookToMap :: (Ord k) => [(k, a)] -> Map.Map k [a] phoneBookToMap xs = Map.fromListWith (++) $ map (\(k,v) -> (k,[v])) xs
ghci> Map.lookup "patsy" $ phoneBookToMap phoneBook ["827-9162","943-2929","493-2928"]
Khá gọn gàng! Một trường hợp sử dụng khác là khi đang lập một ánh xạ từ danh sách liên kết gồm các số, ta tìm thấy một khóa bị trùng, và muốn giữ lại giá trị lớn nhất để cho khóa.
ghci> Map.fromListWith max [(2,3),(2,5),(2,100),(3,29),(3,22),(3,11),(4,22),(4,15)] fromList [(2,100),(3,29),(4,22)]
Hoặc là ta có thể chọn để cộng lại các giá trị có cùng khóa.
ghci> Map.fromListWith (+) [(2,3),(2,5),(2,100),(3,29),(3,22),(3,11),(4,22),(4,15)] fromList [(2,108),(3,62),(4,37)]
insertWith đối với insert thì cũng như fromListWith đối với fromList. Nó chèn một cặp khóa-trị vào trong một ánh xạ, nhưng nếu ánh xạ đó đã sẵn chứa khóa này, thì nó sẽ dùng hàm được truyền vào để quyết định xem cần làm gì.
ghci> Map.insertWith (+) 3 100 $ Map.fromList [(3,4),(5,103),(6,339)] fromList [(3,104),(5,103),(6,339)]
Chỉ có một vài hàm trong Data.Map. Bạn có thể tìm thấy danh sách đầy đủ các hàm ở tài liệu .
THis is trân quốc
ConversionConversion EmoticonEmoticon