là có liên minh và giao cắt Haskell Prelude thực hiện?

Question

Có trong các hàm chuẩn Prelude thực hiện công đoàn và giao điểm của các bộ không?

union  :: (Eq a) => [a] -> [a] -> [a] 
intersect :: (Eq a) => [a] -> [a] -> [a] 

Nếu không, có thể ai đó có thể cho biết nếu thực hiện của tôi là hiệu quả, (tận dụng tốt các sự lười biếng và chức năng khúc dạo đầu)

unionSet :: (Eq a) => [a] -> [a] -> [a] 
unionSet as bs = foldl (\xs y -> if elem y xs then xs else xs ++ [y]) as bs 

intersectSet :: (Eq a) => [a] -> [a] -> [a] 
intersectSet as bs = let ns = [ a | a <- as, elem a bs] in [ b | b <- bs, elem b ns] 

Answer 1

Có union và intersect chức năng trên các danh sách trong các thư viện chuẩn, nằm trong số Data.List nhưng không nằm trong chính số Prelude.

Theo như hiệu quả, tôi sẽ nói "không" với tất cả những điều trên, cả của bạn và thư viện chuẩn. Thực sự không có cách nào có thể là hoạt động hiệu quả trên danh sách chỉ với một ràng buộc Eq. Điều đó nói rằng, bạn vẫn có thể tìm thấy việc thực hiện trong thông tin Data.List - xem các liên kết ở trên, mà tôi đã chỉ trực tiếp đến nguồn có liên quan.

Sửa - Là một phụ lục ngắn gọn vì lợi ích của hậu thế, hãy chắc chắn để xem câu trả lời của Don cho những gì bạn thực sự muốn để sử dụng cho mục đích này, chứ không phải là câu hỏi hẹp hơn "làm các chức năng này tồn tại tất cả các".

Answer 2

Thư viện cơ sở cung cấp các phiên bản danh sách, như camccann chỉ ra. Nếu bạn muốn một cái gì đó một chút hiệu quả hơn, hãy xem xét Data.Set, cung cấp:

union :: Ord a => Set a -> Set a -> Set a 

intersection :: Ord a => Set a -> Set a -> Set a 

với độ phức tạp O (n + m).

Answer 3

Bạn thường sẽ tìm thấy việc triển khai những gì bạn cần bằng cách tìm kiếm chữ ký. Chỉ cần thả chữ ký loại của bạn trong Hoogle ( haskell.org/hoogle/…).