Phân nhóm các loại dữ liệu bằng cách xây dựng trong Haskell

Question

Đối với loại dữ liệu này

data Val = X Int | Y Bool | Z Double deriving (Eq, Show) 

và một danh sách như

let vals = [X 1, Z 2.7, Y True, X 2, Z 3.14, Y True] 

làm thế nào để nhóm yếu tố trong vals vào danh sách này,

[[X 1,X 2],[Y True,Y True],[Z 2.7, Z 3.14]] 

Answer 1

Tôi đã làm như sau:

data Val = X Int | Y Bool | Z Double deriving (Eq, Ord, Show) 

vals :: [Val] 
vals = [X 1, Z 2.7, Y True, X 2, Z 3.14, Y True] 

valCtorEq :: Val -> Val -> Bool 
valCtorEq (X _) (X _) = True 
valCtorEq (Y _) (Y _) = True 
valCtorEq (Z _) (Z _) = True 
valCtorEq _ _ = False 

Và sau đó:

*Main Data.List> groupBy valCtorEq $ sort vals 
[[X 1,X 2],[Y True,Y True],[Z 2.7,Z 3.14]] 

Answer 2

Để thêm vào câu trả lời @ RamonSnir của, chức năng cho nhóm một kiểu dữ liệu do nhà thầu cũng có thể được xây dựng tự động bằng cách sử dụng "phế liệu soạn sẵn của bạn" khuôn khổ:

{-# LANGUAGE DeriveDataTypeable #-} 

import Data.Data 
import Data.Function (on) 
import Data.List (groupBy, sort) 

data Val = X Int | Y Bool | Z Double 
    deriving (Eq, Ord, Show, Typeable, Data) 

vals :: [Val] 
vals = [X 1, Z 2.7, Y True, X 2, Z 3.14, Y True] 

main :: IO() 
main = print $ groupBy (on (==) toConstr) $ sort vals 

hai bộ phận quan trọng là:

• lấy Typeable và Data và
• sử dụng toConstr để lấy đại diện của hàm tạo được sử dụng trong một giá trị cụ thể.

Answer 3

(Đây có lẽ cực overkill, nhưng đó là một câu hỏi thú vị để tinker xung quanh với!)

Những câu trả lời cung cấp phải chịu đựng từ 3 vấn đề nhẹ:

• gì nếu loại đang xem xét không phải là trong Ord (vì ví dụ, có một chức năng trong đó một nơi nào đó)?
• Ngoài ra, hoạt động này có phải là O (n log n) trong độ dài của danh sách không?
• Cuối cùng, ví dụ được cung cấp không đủ để xác định xem nhóm có ổn định hay không, nghĩa là: kết quả của nhóm [X 2, X 1] là [X 1, X 2] (đó là những gì bạn nhận được nếu bạn sử dụng giải pháp dựa trên sort) hoặc các phần tử được giữ trong thứ tự ban đầu của họ?

Vì vậy, đây là giải pháp chung nhất mà tôi có thể đưa ra. Nó ổn định, nó không cần Ord (trên thực tế bạn thậm chí không cần phải chạm vào kiểu dữ liệu gốc) và nó chạy trong khoảng thời gian O (n * min (n, W)) trong đó W là kích thước chữ của máy của bạn (trên tôi, nó là 64). Nghĩa là, nó tuyến tính khi danh sách dài hơn 64 phần tử thứ i (tôi nói 'về', vì các phần tử được nhóm vẫn cần phải được hoàn nguyên từ danh sách khác biệt).

{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-} 

import Data.Data 
import qualified Data.IntMap as IM 

groupByConstructor :: Data a => [a] -> [[a]] 
groupByConstructor = map ($ []) . IM.elems . IM.fromListWith (flip (.)) 
    . map (\a -> (constrIndexOf a, (a:))) where constrIndexOf = constrIndex . toConstr 

-- definition of Val as originally posed, without Ord: 
data Val = X Int | Y Bool | Z Double deriving (Eq, Show) 

deriving instance Typeable Val 
deriving instance Data Val 

-- new example: 
vals = [X 2, Z 2.7, Y True, X 1, Z 3.14, Y False, Z 0.2] 

và bây giờ groupByConstructor vals cung cấp [[X 2, X 1],[Y True, Y False],[Z 2.7, Z 3.14, Z 0.2]] như tôi nghĩ.

---

Nó không làm việc để phân loại danh sách Int s, Char s, Float s, hoặc các loại không biểu diễn như Ptr và Array.Nó có thể có thể được thực hiện một chút hiệu quả hơn bằng cách sử dụng một thuật toán sử dụng số lượng các nhà thầu có thể để đẩy liên tục tuyến tính xuống nhưng IntMap sẽ phải làm ngay bây giờ :-)