Haskell: chuyển đổi danh sách cặp khóa-giá trị (a, b) (với các phím lặp lại có thể) thành danh sách (a, [b]) được nhóm theo khóa

Question

Tôi là người mới bắt đầu sử dụng Haskell. Giả sử tôi muốn viết một hàm convertKVList lấy danh sách phẳng các cặp khóa-giá trị, trong đó một số khóa có thể được lặp lại và biến nó thành ánh xạ từ các khóa sang danh sách các giá trị trong đó tất cả các khóa là duy nhất. Ví dụ, trên một danh sách các cặp Int s, tôi muốn hành vi này:

> convertKVList [(1, 2), (1, 4), (1, 3), (2, 3)] 
[(1,[3,4,2]),(2,[3])] 

Điều này có vẻ giống như một nhiệm vụ đủ phổ biến mà có nên được một chức năng thư viện có sẵn để làm những gì tôi muốn, nhưng tôi couldn' t tìm thấy bất cứ điều gì khi tôi nhìn. Cuối cùng, có người đề nghị tôi soạn Map.toList với Map.fromListWith (++), và tôi đã kết thúc với điều này:

import Data.Map as Map (toList, fromListWith) 

convertKVList :: (Ord a) => [(a, b)] -> [(a, [b])] 
convertKVList ls = 
    (Map.toList . Map.fromListWith (++) . map (\(x,y) -> (x,[y]))) ls 

Câu hỏi của tôi là dành cho Haskellers nhiều kinh nghiệm hơn và có hai phần: Thứ nhất, là thế này thế nào bạn sẽ đi về nó, hoặc có cách nào "tốt hơn" (dễ đọc hơn, hoặc hiệu quả hơn, hoặc cả hai)?

Thứ hai, làm thế nào tôi có thể tự mình làm điều này? Tôi biết rằng tôi muốn loại này là [(a, b)] -> [(a, [b])], nhưng việc đưa nó vào Hoogle không có ích gì cả. Và tôi đã xem các tài liệu Data.Map, nhưng không phải fromListWith cũng không phải toList đã nhảy ra ngoài đặc biệt hữu ích. Vì vậy: làm thế nào bạn sẽ đi về suy nghĩ về vấn đề này? (Tôi nhận ra rằng cả hai câu hỏi này đều mang tính chủ quan, đặc biệt là câu hỏi thứ hai.)

Cảm ơn!

Answer 1

Một trong những điểm quan trọng nhất khi viết một hàm, đang cố gắng phân tách những gì cần thực hiện thành các nhiệm vụ phụ riêng biệt (thường được kết hợp với nhau bằng thành phần chức năng ở cuối). Ví dụ: trong định nghĩa bạn đã đưa ra, có ba tác vụ (theo thứ tự ứng dụng, tức là từ phải sang trái trong định nghĩa):

1. ánh xạ thành phần thứ 2 của mỗi cặp vào danh sách đơn (do đó tạo điều kiện cho việc sử dụng các Map.fromListWith)
2. tạo ra một bản đồ (mà sẽ chăm sóc của việc sáp nhập các mục với các phím tương đương)
3. lượt nó thành một danh sách

tôi muốn gửi một giải pháp khác nhau (mà là một bản sao chính xác của mã Mark được đăng trong khi đó;)). Chỉ cần làm rõ rằng hầu hết thời gian có các tuyến đường khác nhau cho cùng một mục tiêu.Trong định nghĩa của ông bạn có những nhiệm vụ riêng biệt:

1. sắp xếp danh sách bằng các phím
2. nhóm kết quả bằng phím
3. lượt nó vào một danh sách các loại mong muốn

Một lần nữa, tách các mối quan tâm (mô đun) là một nguyên tắc quan trọng. Chỉ cần cố gắng áp dụng nó cho các vấn đề nhỏ và một khi bạn đã đạt được một số kinh nghiệm, bạn sẽ có thể đưa ra các giải pháp đơn giản đáng ngạc nhiên cho các vấn đề dường như khó khăn.

Answer 2

trong khi điều này là do không có nghĩa là kinh điển:

import Data.List 
import Data.Ord 
import Data.Function (on) 

convertKVList :: Ord a => [(a,b)] -> [(a,[b])] 
convertKVList = map (\x -> (fst $ head x, map snd x)) . groupBy ((==) `on` fst) . sortBy (comparing fst) 

nó có lợi thế là không kéo trong Data.Map. nên được asymptotically giống nhau, đã không chuẩn. Tôi nghĩ rằng bạn có thể làm sạch đoạn đầu tiên với Control.Arrow (một cái gì đó như (fst. Đầu & & & bản đồ snd)) nhưng nó không rõ ràng là sạch hơn.

Bạn không chắc chắn mình sẽ làm thế nào trừ khi biết hoặc yêu cầu #haskell.

Answer 3

Vì vậy, giải pháp của tôi lạm dụng mẫu phù hợp bởi vì tôi thực sự không biết những chức năng nào có trong thư viện chuẩn.

Ý tưởng là nếu danh sách được sắp xếp theo các khóa, thì bạn có thể thu thập các khóa-giá trị của mình khi bạn đi. Để thực hiện logic kiểm tra xem có nên thêm vào danh sách khóa-giá trị đầu tiên hoặc tạo một mục mới hay không, tôi đã sử dụng các mẫu và bộ bảo vệ để xác định các điều kiện. Và sử dụng tự do khuyết điểm để thêm các giá trị vào danh sách.

Và trong trường hợp danh sách gốc không được sắp xếp, có sortBy.

import Data.List 
import Data.Ord 

ls = [(2, 1), (1, 2), (1, 4), (1, 3), (2, 3)] 

addval [] (k, v)= [(k, [v])] 
addval ((k1, vals) : xs) (k2, v) | k1 == k2 
    = ((k1, (v : vals)) : xs) 
addval ls (k, v) = ((k, [v]) : ls) 

convert ls = foldl addval [] (sortBy (comparing fst) ls) 

Mã xấu, nhưng tránh sử dụng Bản đồ.

Answer 4

Hoogle không phải là công cụ tìm kiếm duy nhất có thể tìm kiếm các thư viện Haskell theo chữ ký loại và nó chắc chắn và không may chỉ bao gồm một phần nhỏ của Hackage. Tìm kiếm với Hayoo cho một loại chữ ký [(a,b)]->[(a,[b])] mang lên hai triển khai sau đây:

• aggregateAL
• alistCollect

Về Ông nghĩ sao về vấn đề này, vì trong chức năng của bạn, bạn đã đưa lên một mức độ datastructure cao (Map), không có nghĩa là hạ cấp xuống danh sách liên kết nguyên thủy hơn trong đầu ra, bởi vì:

1. Hầu hết các thuật toán bạn có thể sử dụng dữ liệu như vậy sẽ chỉ được hưởng lợi từ việc nhập số Map vì nó hiệu quả hơn để xử lý các cửa hàng có giá trị và nếu bạn thấy mình vẫn cần danh sách, bạn luôn có thể sử dụng các toList tại chỗ.
2. Map ngụ ý sự vắng mặt của các khóa trùng lặp ở cấp loại, điều này không kém phần quan trọng, vì trong Haskell, bạn luôn phải thực hiện các bằng chứng tối đa bằng cách sử dụng hệ thống kiểu. Nguyên tắc này chủ yếu là những gì làm cho tuyên bố "Nếu nó biên dịch, nó hoạt động" gần nhất với sự thật.

Nói cách khác đây là định nghĩa đúng đắn về chức năng của bạn:

convertKVList :: (Ord a) => [(a, b)] -> Map a [b] 
convertKVList ls = 
    Map.fromListWith (++) . map (\(x,y) -> (x,[y])) $ ls 

Hayooing cho loại chữ ký mang lại một vài kết quả đã thực hiện quá.

Liên quan đến vấn đề tiếp cận, đó là cổ điển: "Divide and conquer!". Chris cũng có một số điểm tốt trong câu trả lời của anh ấy.

Answer 5

Trông giống như một giải pháp dễ hiểu và bạn có thể làm sạch nó lên nhẹ hơn:

 
import Data.Map (toList, fromListWith) 
import Control.Arrow (second) 

convertKVList :: Ord a => [(a, b)] -> [(a, [b])] 
convertKVList = toList . fromListWith (++) . map (second (:[])) 

Về làm thế nào bạn có thể đi lên với điều này một mình: giả sử bạn bắt đầu với Data.Map, sau đó bạn muốn sử dụng bản đồ để kết hợp các giá trị với các khóa bằng nhau. Tài liệu cho Data.Map trên Hackage nói a là loại giá trị và k cho khóa.

Biết điều này, bạn có thể tìm kiếm a -> a -> a để tìm các hàm có thể kết hợp hai giá trị trong một Map k a để tạo giá trị a mới. Điều này thu hẹp API xuống một số chức năng như insertWith, fromListWith và fromAscListWith.

Tương tự như vậy, để chuyển đổi của bạn Map k a-[(k, a)], bạn có thể tìm kiếm tài liệu cho Map k a -> [(k, a)] và chỉ tìm thấy một vài chức năng như assocs, toList, toAscList, và toDescList. Lưu ý rằng trong trường hợp của bạn, [(k, a)] được khởi tạo đến [(Int, [Int])].

Một điều tôi thấy hữu ích khi hiểu các thư viện Haskell chuẩn là xem nguồn trên Hackage. Việc xem các chức năng nào được thực hiện theo cách khác sẽ giúp API cảm thấy nhỏ hơn và tôi có thể thấy các chức năng nào là các khối xây dựng cơ bản.

Answer 6

Tôi nghi ngờ rằng không nhúng vào đột biến và đơn lẻ ST, bạn sẽ không cải thiện được giải pháp Map.fromListWith (hoặc các lựa chọn thay thế tương đương đáng kể như sử dụng HashMap.fromListWith). Tôi chỉ đi với điều đó. Về cơ bản, với đột biến, bạn có thể thực hiện nhóm này trong thời gian gần bằng tuyến tính bằng cách sử dụng bảng băm có thể thay đổi với a làm các khóa và danh sách có thể thay đổi là b làm giá trị. Nếu không có đột biến, tuy nhiên, nó sẽ tồi tệ hơn, bởi vì mỗi chèn vào một cây tìm kiếm cân bằng là O (log n); Điều này là do "chèn" có nghĩa là xây dựng một bản sao mới của mỗi nút cây dẫn đến một phần tử chèn vào của bạn. Và bạn cần phải chèn n - cung cấp cho bạn chính xác giới hạn O (n * log n) rằng Map.fromListWith có chức năng. Sắp xếp danh sách liên kết trước thời hạn không cải thiện về cơ bản điều này, bởi vì sắp xếp cũng là O (n * log n).

Vì vậy, để cải thiện trên O (n * log n), bạn cần cấu trúc dữ liệu với đột biến. Tôi vừa làm nhanh Google và đặt cược tốt nhất là triển khai thuật toán bắt buộc chuẩn bằng cách sử dụng thư viện hashtables (mà tôi chưa bao giờ thử, vì vậy tôi không thể xác minh cho nó). Để sử dụng điều này, bạn sẽ cần phải hiểu Control.Monad.ST và Data.STRef. Đơn vị ST là một kỹ thuật mà GHC cung cấp khi sử dụng đột biến "nội bộ" trong hàm thuần túy - nó sử dụng một số phần mở rộng hệ thống kiểu để đảm bảo rằng các tác dụng phụ không thể được quan sát bên ngoài các hàm đang được đề cập. HaskellWiki has some examples, nhưng nó có thể mất một số nghiên cứu và thực hành để cảm thấy thoải mái với điều này.

Những điều khác tôi muốn giới thiệu, nếu bạn cảm thấy như bạn muốn hiểu Data.Map hoặc tương tự thư viện tốt hơn, là nhìn vào Chris Okasaki của thuần túy chức năng Cấu trúc dữ liệu cuốn sách (hoặc his dissertation (PDF) that the book is based on). Nó dựa trên tiêu chuẩn ML thay vì Haskell, cấu trúc dữ liệu không giống nhau, và nó có thể là một chút khó đọc, nhưng đó là một cuốn sách cơ bản.