27

次のようなタプルのリストがあるとします。

dic = [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]

dicの項目をグループ化してリストgrpにする方法

grp  = [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]

私は実際には Haskell の初心者です...そしてそれに恋をしているようです.. Data.ListでgroupまたはgroupBy
を使用すると、リスト内の同様の隣接アイテムのみがグループ化されます。このために非効率的な関数を作成しましたが、非常に大きなコード化された文字列リストを処理する必要があるため、メモリ エラーが発生します。より効率的な方法を見つけるのを手伝ってくれることを願っています。

4

5 に答える 5

19

これが私の解決策です：

import Data.Function (on)
import Data.List (sortBy, groupBy)
import Data.Ord (comparing)

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

これは、最初にリストを次のように並べ替えることで機能しsortByます。

[(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]     
=> [(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")]

次に、関連付けられたキーでリスト要素をグループ化しますgroupBy。

[(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")] 
=> [[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]]

次に、グループ化されたアイテムをタプルに変換しますmap:

[[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]] 
=> [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]`)

テスト:

> myGroup dic
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]
于 2012-09-13T02:08:45.813 に答える
6

また、次のようにTransformListComp拡張機能を使用できます。

Prelude> :set -XTransformListComp 
Prelude> import GHC.Exts (groupWith, the)
Prelude GHC.Exts> let dic = [ (1, "aa"), (1, "bb"), (1, "cc") , (2, "aa"), (3, "ff"), (3, "gg")]
Prelude GHC.Exts> [(the key, value) | (key, value) <- dic, then group by key using groupWith]
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]
于 2012-09-13T02:25:51.830 に答える
4

  1. リストが最初の要素でソートされていない場合、O(nlog(n)) よりもうまくいくとは思いません。

    • 簡単な方法の 1 つsortは、2 番目の部分の回答から何かを使用することです。

    • タプルの最初の要素をキーとして使用し、値を追加し続けるData.Mapようなマップから使用できます。Map k [a]

    • 独自の複雑な関数を作成できます。これは、すべての試行の後でも O(nlog(n)) かかります。

  2. あなたの例のようにリストが最初の要素でソートされている場合、@Mikhailの回答で与えられているようにgroupByのようなタスクは簡単で、foldrを使用し、他にも多くの方法があります。

folderr の使用例は次のとおりです。

  grp :: Eq a => [(a,b)] -> [(a,[b])]
  grp = foldr f []
     where 
       f (z,s) [] = [(z,[s])] 
       f (z,s) a@((x,y):xs)  | x == z = (x,s:y):xs 
                             | otherwise = (z,[s]):a
于 2012-09-13T02:16:02.970 に答える
0 
{-# LANGUAGE TransformListComp #-}

import GHC.Exts
import Data.List
import Data.Function (on)

process :: [(Integer, String)] -> [(Integer, [String])]
process list = [(the a, b) |  let info = [ (x, y) | (x, y) <- list, then    sortWith by y ], (a, b) <- info, then group by a using groupWith]
于 2016-04-12T14:27:00.083 に答える