www.jammni.de

Gepostet:
22.06.2012 17:50

DataMap sortieren

Hallo an alle,
würde gerne wissen welche Möglichkeiten es gibt eine DataMap zu sortieren. In eine DataMap speichere ich als Keys Strings.
Diese sollen auf eine bestimmte Art lexikografisch sortiert werden. Erst Kleinbuchstaben und bei gleichem Wort, soll
das Wort mit dem größeren Buchstaben zu erst stehen. Ich verwende DataMaps, da mir gesagt wurde, dass diese auf Grund ihrer Veränderlichkeit
eine bessere Performance als Listen besitzen. Nur weiß ich nicht wie ich die vorgebebene Sortierstruktur brechen kann und eine eigene
implementieren kann. Habe schon irgendwo gelesen dass ich sie in eine Liste umformen könnte und dann diese sortieren könnte. Bringt aber finde ich nicht wirklich was da ich dann a) wieder das Performance Problem habe und b) die Liste dann eh nicht wieder in dieser Reihenfolge als DataMap abspeichern kann da dann immer wieder die vorgelegte Reihenfolge von DataMap verwendet wird.
Irgendwelche Ideen was ich machen könnte?

Zum Seitenanfang

sharufa

Gepostet:
24.06.2012 10:34

Hat jetzt noch keiner darauf geantwortet, da es keiner weiß oder weil es so trivial ist. Ich meine kann doch nicht sein, dass noch nie jemand über dieses PRoblem gestoßen ist? Ich finde auch wirklich überhaupt nichts im Internet wie man das machen könnte....

Zum Seitenanfang

Siracusa

Gepostet:
24.06.2012 19:42

Hallo,

deine Ordnungsfunktion ist mir nicht ganz klar, aber wenn du weiß, wie du diese implementieren kannst, sollte der folgende Ansatz funktionieren. Data.Map sortiert die Elemente intern nach ihrer Ordnung, benötigt also eine Ord-Instanz für die Elemente. Du kannst dir nun einen neuen Datentyp MyString erzeugen, der nur einen Konstruktor zur Verfügung stellt und selbst wieder einen normalen String speichert:

data MyString = MyString String deriving (Eq)

Für diesen Datentyp kannst du nun eine Ord-Instanz ableiten und mit der compare-Funktion entscheiden, wie zwei Elemente innerhalb der Ordnung in Beziehung stehen:

instance Ord MyString where
  compare (MyString s1) (MyString s2) = ...  -- siehe den Typ Ordering für die möglichen Resultate

Wenn du nun in deiner Map nur Elemente des Typs MyString speicherst, wird die korrekte Ordnung automatisch erzeugt.

Viele Grüße
siracusa

Zum Seitenanfang

Landei

Gepostet:
25.06.2012 08:56

Du kannst einen Schritt weiter gehen, und einen generellen Wrapper dafür schreiben:


import qualified Data.Map as M

newtype Key a = Key a
newtype SortedMap a b = SortedMap (M.Map (Key a) b)

mapNull (SortedMap m) = M.null m  
mapEmpty = SortedMap M.empty 
mapMember k (SortedMap m) = M.member (Key k) m 
mapLookup k (SortedMap m) = M.lookup (Key k) m
mapInsert k v (SortedMap m) = SortedMap $ M.insert (Key k) v m
mapSize (SortedMap m) = M.size m

Jetzt kannst du beliebige Ord-Instanzen für Key schreiben (du brauchst dafür FlexibleInstances). Hier ist ein Beispiel für eine case-insensitive Map:


{-# LANGUAGE FlexibleInstances #-}
import Data.Char

up x = map toUpper x 

instance Eq (Key String) where 
  Key x == Key y  = up x == up y
  
instance Ord (Key String) where
  compare (Key x) (Key y) = up x `compare` up y 
  
main = print $ mapLookup \"Hi\" $ mapInsert \"hi\" 1 mapEmpty 
//--> Just 1

Zum Seitenanfang

Haskell-Forum