Hallo an alle,
hoffe es kennt sich hier der eine oder andere mit Haskell aus. Im Haskell Forum ist leider sehr wenig los, deswegen hoffe ich mal dass ich hier evtl. richtig bin.
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?

Hi, hier findet sich sicher einer, der sich deiner Frage annimmt. Eine kurze Sache dennoch vorweg:

Hast du das Performanceproblem konkret oder hast du nur mal davon gehört? Wenn ja, kannst du ein Beispiel posten, dass dieses Problem offenbart?

An sich sind Listen schon effizient, wenn die Reihenfolge eben das wichtigste Merkmal ist. Meines Wissens sind auch Data.Map-Typen in Haskell nicht "veränderbar", aber da kann ich mich irren. Maps sind halt schneller, wenn du schnellen Lookup von Einzelelementen brauchst, Listen sind schneller, wenn du häufig über die gesamte Liste iterieren musst (da dir die Reihenfolge wichtig ist, gehe ich mal davon aus, dass das der Fall ist). Dafür sind Listen halt langsamer, wenn du darin suchen musst. Bei sortierten Listen kannst du allerdings auch an dieser Stelle mit ein paar Tricks ne ganze Menge sparen.

Insofern ist die Frage, ob das eine besser oder das andere schlechter ist, wahrscheinlich schwer zu beantworten, vor allem da Data.Map ja eine ganze Menge Funktionen anbietet, um aus assoziativen Listen Maps zu erstellen und umgekehrt wieder Listen. Als ersten Schritt wäre es wahrscheinlich sinnvoll, einfach mal das zu wählen, was man für den jeweiligen Einsatzzweck am häufigsten braucht und ansonsten zur Not in den anderen Typ zu konvertieren. Wenn man dann ein echtes Problem damit kriegt, kann man an der Stelle weiteroptimieren. Versteck das Ganze am besten hinter einen guten Interface.

Gruß,
Skade

Nur zur Klarstellung - ich nehme mal an, du willst sagen, dass du nachträglich neue Elemente hinzufügen oder entfernen willst? Ja, dann ist die Liste keine gute Wahl, denn diese Operationen wären damit schlimmstenfalls O(n).

Um die Sortierreihenfolge zu verändern, brauchst du eine andere Ord-Instanz für deinen Key. Da du den von String (noch) nicht überschreiben kannst, heißt das, dass du den Key-Typ ändern musst. Das ist nicht wirklich kompliziert:
newtype MyString = MyString { fromMyString :: String }
deriving (Eq, Show)
instance Ord MyString
(MyString s1) `compare` (MyString s2) = ...

Durch Verwendung von newtype wird das Ganze zu einem reinen Compile-Time-Konstrukt, dieser Wrapper kostet dich also nichts in Sachen Performance. Mit deriving kannst du so viele Instanzen übernehmen, wie du unverändert behalten möchtest.

Die interessantere Frage ist, ob du jetzt die Bilbiotheks-Funktionen so verpackst, dass sie jeweils String nach MyString konvertieren - oder ob du gleich überall MyString verwenden solltest. Ich würde zu letzterem raten