So gruppieren Sie ähnliche Elemente in einer Liste mit Haskell?

Gegeben eine Liste von Tupeln, wie diese:

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

So gruppieren Sie Elemente von dic was in einer Liste grp wo

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

Ich bin eigentlich ein Neuling in Haskell...und scheint zu sein, fallen in der Liebe mit ihm..

Mit Gruppe oder groupBy in Daten.Liste wird die einzige Gruppe, ähnlich wie benachbarte Elemente in einer Liste.
Ich schrieb eine ineffiziente Funktion für diese, aber es führt in-memory-Fehler, wie ich brauche, um Verfahren eine sehr große codierten string-Liste. Hoffe, Sie würden mir helfen, einen effizienteren Weg.

Sieht aus wie eine Hausaufgabe oder so etwas. Besser, fügen Sie Ihren Ansatz und bitten der community nach Möglichkeiten, es zu verbessern, statt nur zu Fragen die Antwort.
Sorry, ich bin ein Neuling auf stackoverflow..Entschuldigung für nicht beachten von Regeln der Gemeinschaft.

InformationsquelleAutor td123 | 2012-09-13

haskell

15

Hier ist meine Lösung:
```
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)
```
Dies funktioniert so, dass zunächst die Sortierung der Liste mit 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")]
```
dann gruppieren Sie die Liste Elemente, indem Sie auf die entsprechende Taste mit 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")]]
```
und dann die Umwandlung der gruppierten Elemente Tupel mit map:
```
[[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]] 
=> [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]`)
```
Testen:
```
> myGroup dic
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]
```
- Ich danke Ihnen so sehr. Das funktioniert wirklich. Ich bin eigentlich ein Neuling in Haskell und ich wußte nicht viel über Bibliotheken. Nochmals vielen Dank für die kluge Antwort!.
- Mikhail : Hey, sind Sie sicher, dass das funktioniert sogar, wenn ähnliche eingegeben Werte nicht benachbart sind? für ein Beispiel, wenn dic = [(1,"aa"),(2,"bb"),(1,"cc")]? Ergebnis sollte sein, [(1, ["aa","cc"]), (2, "bb")].
- ^@td123 In diesem Fall sollten Sie die Liste Sortieren vorher.
- OH..ich Danke Euch So sehr.
- Ich habe aktualisiert, der code zur Unterstützung von unsortierten Listen.
InformationsquelleAutor Mikhail Glushenkov
56

Wann immer möglich, die Wiederverwendung von code für die Bibliothek.
```
import Data.Map
sortAndGroup assocs = fromListWith (++) [(k, [v]) | (k, v) <- assocs]
```
Probieren Sie es aus, im ghci:
```
*Main> sortAndGroup [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]
fromList [(1,["bb","cc","aa"]),(2,["aa"]),(3,["gg","ff"])]
```
- Wirklich Coole Lösung. Nie würde gedacht haben, aber es macht sehr viel Sinn, in Anbetracht der Art der Daten.Karte.
- Dies war nun meine Antwort. Ich habe kurz pause gab zu denken, Effizienz, obwohl ich die toList . fromListWith op Muster eine Menge, aber ich Frage mich, wie teuer die Konvertierungen in und aus Map sind im Vergleich zu Fuß über die Liste und gruppieren Sie Sie manuell.
- Diese Lösung ist O(n log n), was ist die beste man hoffen kann angesichts der Einschränkungen.
- Vielen, Vielen Dank!
- Ist nicht die Umwandlung jedes element einer Liste und dann die Verkettung der Listen ein bisschen teuer?
- Sollte es nicht, Nein; der Umwandlung in eine Liste ist sehr Billig, und voranstellen singleton-Listen, ist Billig. Wenn es sich herausstellt, dass dies mit dem anfügen singleton-Liste statt, es ist einfach zu beheben: verwenden Sie einfach fromListWith (flip (++)) statt fromListWith (++).
- Follow-up: Wie wissen wir, ob es ist, voranstellen oder Anhängen? Es scheint nicht, eine offensichtliche Weise, zu wissen, dass.
- Vergleichen Sie die Leistung von fromListWith (++) [((), [()]) | x <- [1..10000]] mit der Leistung der fromListWith (flip (++)) [((), [()]) | x <- [1..10000]]. 😉 (Spoiler: (++) ist die richtige, nicht flip (++).)
- Das funktioniert zwar, fühlt sich ein bisschen wie ein hack zu mir. Gibt es nicht eine "richtige by design" - Ansatz anwendbar ist, auf einer größeren Skala?
- Sorry, ich kann nicht zur Rechenschaft gezogen werden für Ihre Gefühle. Wenn Sie ein sachlicher Grund nicht zu mögen diese Lösung, ich würde glücklich sein, zu diskutieren, mögliche mitigations-und Ihre Nachteile.
- Fair genug. Ich wollte nur wissen, ob es einen Weg gibt, zu wissen, diese Informationen, ohne zu Experimentieren. Wie konzeptionell.
- href="http://hackage.haskell.org/package/containers-0.5.10.2/docs/src/Data-Map-Internal.html#fromListWith" >Lesen Sie die Quelle, natürlich.
- es ist ein docs-Mangel. es sollte erwähnt haben, die Reihenfolge, wie es bereits für insertWith / insertWithKey, die die fromListWith - Funktion verwendet jedenfalls, zu urteilen, die Quelle.
InformationsquelleAutor Daniel Wagner

Du kannst auch TransformListComp - Erweiterung, zum Beispiel:

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"])]

InformationsquelleAutor Fedor Gogolev

4
1. Wenn die Liste nicht sortiert ist, die auf das erste element, ich glaube nicht, dass Sie tun können, besser als O(nlog(n)).
  - Eine einfache Möglichkeit wäre, nur sort und dann alles verwenden, was aus der Antwort der zweite Teil.
  - Können Sie aus Data.Map eine Karte wie Map k [a] um erste element der Tupel-Taste und halten auf hinzufügen, um die Werte.
  - Schreiben Sie Ihre eigene komplexe Funktion, die auch nach all den versuchen noch O(nlog(n)).
2. Wenn die Liste ist sortiert nach dem ersten element, wie der Fall in deinem Beispiel, dann ist die Aufgabe trivial, für so etwas wie groupBy-wie in der Antwort von @Mikhail oder verwenden foldr und es gibt zahlreiche andere Möglichkeiten.
Beispiel für die Verwendung von foldr ist hier:
```
  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
```
- Danke für die info...ich werde die Daten verwenden.Karte.
InformationsquelleAutor Satvik

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

InformationsquelleAutor Hari Krishna

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.