通過構造在Haskell

分組數據類型鑑於這種數據類型通過構造在Haskell

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

和一個列表，諸如

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

如何分組vals元件插入此列表，

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

來源

2014-10-22 elm

我有以下幾種：

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

然後：

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

來源

2014-10-22 06:04:02

不幸的是，這不是OP要求的。目的是按照他們的建設者而不是平等來分組價值。 – 2014-10-22 06:33:54

@PetrPudlák你是非常正確的，我使用了錯誤的文件，並沒有閱讀輸出......我會編輯。 – 2014-10-22 06:36:59

@PetrPudlák謝謝！ – 2014-10-22 06:39:36

要添加到@ RamonSnir的答案，該功能通過構造分組數據類型也可以自動使用「廢你的樣板」的框架結構：

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

兩個重要的部分是：

獲得Typeable和Data和
使用toConstr來獲取在特定值中使用的構造函數的表示形式。

來源

2014-10-22 06:47:39

（這可能是極端矯枉過正，但它是一個有趣的問題進行修補與周圍！）

所提供的答案，從3個輕微問題的困擾：

，如果什麼類型在考慮不在Ord（因爲例如，那裏有一個功能在那裏）？
另外，如果這個操作在列表的長度上是O（n log n）？
最後，所提供的示例不足以確定分組是否應該穩定，即：如果分組[X 2, X 1]的分組結果爲[X 1, X 2]（如果您使用基於sort的解決方案，您會得到結果），還是應該將元素保持原來的順序？

所以這裏是我能想出的最通用的解決方案。它是穩定的，它不需要Ord（事實上，你甚至不需要觸摸原始數據類型），它運行在大約O（n * min（n，W））時間，其中W是機器的字大小（在我的，這是64）。也就是說，一旦列表長度超過64個元素（我說「約」，因爲分組元素仍然需要從差異列表中重組），它就是線性的。

{-# 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]

現在groupByConstructor vals給[[X 2, X 1],[Y True, Y False],[Z 2.7, Z 3.14, Z 0.2]]，因爲我認爲它應該。

它不排序的Int S，Char S，Float S，或非表示的類型，如Ptr和Array列出工作。通過使用可能的構造函數來推動線性常數進一步下降的算法，可能會更有效一些，但IntMap現在必須做:-)

來源

2014-10-22 19:36:22 yatima2975

通過構造在Haskell

回答

相關問題