www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

chrisslater

Gepostet:
15.11.2008 14:19

Listen von Listen, Rekursion auf Listen  
Hallo...Ich hab folgendes Problem:

Eine Matrix ist eine Struktur aus der Mathematik, die einer Tabelle aus Zeilen und Spalten entspricht,
in der an jeder Position eine Zahl steht. Die Zahl in Zeile i und Spalte j in einer Matrix a wird mit ai,j
bezeichnet. Mit den Mitteln von Haskell kann eine Matrix als Liste ihrer Zeilen dargestellt werden,
wobei jede Zeile eine Liste ihrer Elemente in den einzelnen Spalten ist. Im folgenden Beispiel ist eine
Matrix a mit drei Zeilen und drei Spalten gegeben. Daneben ist die Speicherung dieser Matrix als Liste
von Listen dargestellt. In dieser Matrix gilt beispielsweise: a0,2 = 4 und a2,1 = 23.
Matrix:
10 0 4
3 5 10
234 23 0

Listendarstellung:
[[10,0,4], [3,5,10], [234,23,0]]

Diese Form der Speicherung einer Matrix ist zwar sehr intuitiv, erfordert aber immer den gleichen
Speicherbedarf für eine Matrix mit n Zeilen und m Spalten. Für große Matrizen, in denen an sehr
vielen Positionen der Wert 0 steht (dünn besetzte Matrizen), ist es unter Umständen günstiger eine
ähnliche Form der Speicherung zu verwenden, wie wir sie bereits für Bitmapgrafiken genutzt haben.
Das bedeutet, dass die Matrix als Liste von 3-Tupeln gespeichert wird, wobei jede Positionen ai,j in der
Matrix, die einen Wert verschieden von 0 enthält, durch ein 3-Tupel (i, j, ai,j) in dieser Liste
repräsentiert wird. Für solche Positionen in der Matrix, die eine 0 enthalten, gibt es kein Tupel in der
Liste. Durch diese Form der Speicherung ist jedoch die Größe der Matrix nicht mehr eindeutig
bestimmt. Wir definieren deshalb den Datentypen
type SpareMatrix = ([(Int,Int,Int)],Int,Int)
in dem die Anzahl der Zeilen und Spalten der dünn besetzten Matrix explizit angegeben wird. Dabei
ist in dem 3-Tupel die zweite Komponente die Zeilenanzahl und die dritte Komponente die
Spaltenanzahl der in der ersten Komponente gespeicherten Matrix. Implementieren Sie die Funktionen
(a) toTupel :: [[Int]] -> SpareMatrix, die eine Matrix in Listenform in eine Matrix in
Tupelform konvertiert und eine Funktion
(b) toList :: SpareMatrix -> [[Int]], die eine Matrix in Tupelform in eine Matrix in
Listenform konvertiert.

Zum Seitenanfang    
 
Siracusa

Gepostet:
15.11.2008 14:55

   
Hallo,

na dann mal viel Erfolg! ;-) Was genau ist deine Frage?


Viele Grüße,

Siracusa
Zum Seitenanfang    
 
chrisslater

Gepostet:
15.11.2008 15:03

   
die Frage ist wie ich

(a) toTupel :: [[Int]] -> SpareMatrix, die eine Matrix in Listenform in eine Matrix in
Tupelform konvertiert und eine Funktion
(b) toList :: SpareMatrix -> [[Int]], die eine Matrix in Tupelform in eine Matrix in
Listenform konvertiert.
type SpareMatrix = ([(Int,Int,Int)],Int,Int)

in Haskell umsetzen kann
Zum Seitenanfang    
 
Siracusa

Gepostet:
15.11.2008 22:47

   
zu (a): Hier könntest du einer Hilfsfunktion schreiben, die nacheinander alle Elemente in der Matrix durchgeht, die aktuelle Position entsprechend ändert und prüft, ob der aktuelle Wert 0 ist oder nicht. Wenn er nicht 0 ist, dann hängst du ein neues Element der Form (i,j,wert) in die Ergebnisliste. Also etwa in dieser Form:
toTupel' :: [[Int]] -> Int -> Int -> [(Int, Int, Int)]
toTupel' [[]] i j = []
toTupel' ([] : ys) i j = ... toTupel' ys 0 (j+1) ...
toTupel' ((x:xs) : ys) i j = ...toTupel' (xs : ys) (i+1) j ...

zu (b): Hier könntest du dieses Prinzip genau umdrehen und alle Koordinatenpaare zwischen maxX und maxY durchgehen und jeweils den Wert aus dem Tupel einfügen, wenn in der Liste aus der SpareMatrix ein Tupel mit diesem Koordinatenpaar ist, sonst eine 0.


Viele Grüße,

Siracusa
Zum Seitenanfang    
 
chrisslater

Gepostet:
15.11.2008 22:55

   
vielen Dank für die Lösung....aber wäre es vielleicht möglich, dass du mir auch zeigen könntest wie der Quelltext von b aussieht....Wir haben grad erst mit Haskell angefangen und müssen schon so ne Aufgabe lösen. Wäre nett wenn du es machen könntest, wenn es nicht zu viel verlangt ist.
Zum Seitenanfang    
 
Siracusa

Gepostet:
16.11.2008 00:53

   
Also zu der (a) ist das auch nicht die Lösung, nur ein möglicher Ansatz. Und komplette Lösungen zu Aufgaben schicke ich auch nicht. Wenn du aber eine Funktion hast, die noch nicht richtig funktioniert, helfe ich dir gern beim Korrigieren.
Zum Seitenanfang