www.jammni.de

1 2

Gepostet:
19.05.2005 19:52

lesen sehen und staunen ;)



---mergesort zum sotieren

--mergesort::([a]->[a]->[a])->[a]->[a]

mergesort merge xs
		  | length xs<2 = xs
		  | otherwise
			        = merge (mergesort merge first) (mergesort merge second)
			         where
			         first = take half xs
			         second =drop half xs
			         half =(length xs) `div` 2

----end mergesort

---zum zusammenfassen der tupel also [(a,1),(a,1)] wird zu [(a,2)] und sortieren der liste die kleinen zahlen immer vorne

amerge::[(Char,Int)]->[(Char,Int)]->[(Char,Int)]
amerge xs []=xs
amerge [] ys=ys
amerge ((p,n):xs) ((q,m):ys)
			    |(p==q)    = (p,n+m):amerge xs ys
			    |(p<q)     = (p,n)  :amerge xs ((q,m):ys)
			    |otherwise = (q,m)  :amerge ((p,n):xs) ys
-----

---freqmerge sortiert die liste von tupeln zunächst nach der anzahl, die buchstaben die einmal vorkommen sind vorne
---und bei selber anzahl der buchstaben werden die buchstaben die im alphabeth weiter vorne sind nach vorn sortiert
freqmerge :: [(Char,Int)]->[(Char,Int)]->[(Char,Int)]
freqmerge xs []=xs
freqmerge [] ys=ys
freqmerge ((p,n):xs) ((q,m):ys)
				|(n<m ||(n==m && p<q)) =(p,n):freqmerge xs ((q,m):ys)
				| otherwise =(q,m):freqmerge((p,n):xs) ys




--deine hauptfunktion
add2list::[Char]->[(Char,Int)]
add2list=mergesort freqmerge . mergesort amerge . map start
         where start ch =(ch,1)

ps: du mußt im code scrollen
die hilfsfunktionen sind aus haskell the art of funktionalprogramming...also benenne alles noch schön um ...du kriegst ja schließlich ne note drauf

falls du noch fragen hast ich erklär dir den code gerne

gruß jacke

Zum Seitenanfang

Bidrohi

Gepostet:
19.05.2005 20:50

ok ich habe ma dein tips übernommen(nochmals danke im icq)
aber es ergeben sich da immer wieder probleme mit den typen deklarationen(scheint meine schwäche zu werden TT)

makeZeichenliste :: String -> [Char]
makeZeichenliste xs = mklist xs []

mklist :: String -> [Char] -> [Char]
mklist [] liste = liste
mklist (x:xs) liste = mklist xs (add2list x liste)

---mergesort zum sotieren

--mergesort::([a]->[a]->[a])->[a]->[a]

mergesort merge xs
| length xs<2 = xs
| otherwise
= merge (mergesort merge first) (mergesort merge second)
where
first = take half xs
second =drop half xs
half =(length xs) `div` 2

----end mergesort

---zum zusammenfassen der tupel also [(a,1),(a,1)] wird zu [(a,2)] und sortieren der liste die kleinen zahlen immer vorne

amerge::[(Char,Int)]->[(Char,Int)]->[(Char,Int)]
amerge xs []=xs
amerge [] ys=ys
amerge ((p,n):xs) ((q,m):ys)
|(p==q) = (p,n+m):amerge xs ys
|(p<q) = (p,n) :amerge xs ((q,m):ys)
|otherwise = (q,m) :amerge ((p,n):xs) ys
-----

---freqmerge fehlt
freqmerge :: [(Char,Int)]->[(Char,Int)]->[(Char,Int)]
freqmerge xs []=xs
freqmerge [] ys=ys
freqmerge ((p,n):xs) ((q,m):ys)
|(n<m ||(n==m && p<q)) =(p,n):freqmerge xs ((q,m):ys)
| otherwise =(q,m):freqmerge((p,n):xs) ys

--frequency
add2list::[Char]->[(Char,Int)]
add2list =mergesort freqmerge . mergesort amerge . map start
where start ch =(ch,1)

--ende

data HTree = Blatt Char Int | Knoten HTree Int HTree
deriving (Eq, Show)

makeBlatt :: Char -> HTree
makeBlatt (c,n) = Blatt c n

list2tree :: [Char] -> [HTree]
list2tree xs = map makeBlatt xs

gewicht :: HTree -> Int
gewicht (Blatt c n) = n
gewicht (Knoten li n re) = n

verschmelzen :: HTree -> HTree -> HTree
verschmelzen b1 b2
| n1 >= n2 = Knoten b1 (n1+n2) b2
| otherwise = Knoten b2 (n1+n2) b1
where n1 = gewicht b1
n2 = gewicht b2

insTreeInList :: HTree -> [HTree] -> [HTree]
insTreeInList b [] =
insTreeInList b (x:xs)
| gewicht b <= gewicht x = b:x:xs
| otherwise = x:insTreeInList b xs

mkHTree :: [HTree] -> [HTree]
mkHTree [b] = [b] -- Stoppfall
mkHTree (b1:b2:bs) = mkHTree (insTreeInList b bs)
where b=verschmelzen b1 b2

makeHuffmantree :: [Char] -> HTree
makeHuffmantree xs = head (mkHTree (list2tree xs))

kodieren :: String -> (String,HTree)
kodieren xs = (kodieren1 xs htree,htree)
where htree = makeHuffmantree (makeZeichenliste xs)

kodieren1 :: String -> HTree -> String
kodieren1 [] b = []
kodieren1 (x:xs) b = (code b x)++kodieren1 xs b

code :: HTree -> Char -> String
code (Blatt c n) x
| c==x = []
| otherwise = error "Zeichen nicht in Baum enthalten"
code (Knoten li n re) x
| member x li = '1':code li x
| otherwise = '0':code re x
where member a (Blatt c n) = (a==c)
member a (Knoten li c re) = (member a li) || (member a re)

hier wird der fehler
ERROR "C:\WINDOWS\Desktop\hugs\wuff3.hs":8 - Type error in application
*** Expression : add2list x liste
*** Term : add2list
*** Type : [Char] -> [(Char,Int)]
*** Does not match : a -> b -> c
ausgegeben...ich weiß nun zwar den grund aber net wie ich es beheben kann

Smilie

wär nett wenn man mir mit den ganzen typen helfen könnte...komm zwar mit den algorithmen klar aber net mit den engen typen und wie man mit denen umgeht

Zum Seitenanfang

Jacke

Gepostet:
20.05.2005 12:10

was soll den makezeichenliste machen? eigentlich doch dasselbe wie add2list oder?wozu brauchst du die funktion dann?

also add2list macht aus einen string eine liste von tupeln
ein beispiel
add2list "lalalalalaaaaaaaaaa"
rückgabe [(l,5),(a,14)]

oder soll makezeichenliste daraus [[l],[a]] machen? also ne liste aus chars
das würde dann so gehen:

makeZeichenliste :: String -> [Char]
makeZeichenliste xs = mklist (add2list xs) []
---das add2list macht aus xs die sotierte tupeliste

---und mklist macht aus der sortierten tupelliste nur noch diesselbe liste aus chars
mklist :: [(Char,Int)] -> [Char]->[Char]
mklist [] liste=liste
mklist ((x,n):xs) liste= mklist xs (liste++x)

gruß jacke Smilie

Zum Seitenanfang

Bidrohi

Gepostet:
20.05.2005 15:45

hm : / da kommen jetzt meine mathematischen schwierigkeiten...also ich brauche am ende um daraus einen huffmantree zu machen die liste der charakter mit ihrer haufigkeit...links das kleinste rechts das größte....
was man sich jetzt da oben gedacht hat war , das bei makezeichenliste einfach nur mkliste aufgerufen wird mit dem string und einer leeren liste nun wird in der funtkion mkliste diese liste mit den char aufgefüllt mit der form von add2liste, also das ihre haufigkeit mitgezählt wird....solange bis die String liste leer ist. am ende hat man dann ne char liste mit der man mit der funktion makehuffmantree einen baum bastelt

makeHuffmantree :: [Char] -> HTree
makeHuffmantree xs = head (mkHTree (list2tree xs))

list2tree :: [Char] -> [HTree]
list2tree xs = map makeBlatt xs

makeBlatt :: Char -> HTree
makeBlatt (c,n) = Blatt c n

sodass man dann weiter macht mit mkHTree die die einzelnen Blätter zu dem baum verschmilzt etc.

Zum Seitenanfang

Jacke

Gepostet:
21.05.2005 23:02

Zitat:
also ich brauche am ende um daraus einen huffmantree zu machen die liste der charakter mit ihrer haufigkeit...links das kleinste rechts das größte....

also

(i) die funktion add2list funktioniert hier folgendermassen als erstes paaren wir jeden char mit einer 1
[('a',1),('b',1),('a',1),('c',1),('b',1),('a',1)]

(ii) als nächstes sortieren wir die liste von char und vereinigen die counts der gleichen chars
[('a',3),('b',2),('c',1)]

(iii) als nächstes sortieren wir die liste nach der häufigkeit der chars
[('c',2),('b',2),('a',3)]

die funktion add2list benutz zwei verschiedene sortieralgorithmen um das ergebnis zu liefern einen der auf der sortierung der chars beruht und einen der auf der sortierung der häufigkeit beruht...

---mergesort zum sotieren

--mergesort::([a]->[a]->[a])->[a]->[a]

mergesort merge xs
| length xs<2 = xs
| otherwise
= merge (mergesort merge first) (mergesort merge second)
where
first = take half xs
second =drop half xs
half =(length xs) `div` 2

----end mergesort

---zum zusammenfassen der tupel also [(a,1),(a,1)] wird zu [(a,2)] und sortieren der liste die kleinen chars immer vorne (ii)

amerge::[(Char,Int)]->[(Char,Int)]->[(Char,Int)]
amerge xs []=xs
amerge [] ys=ys
amerge ((p,n):xs) ((q,m):ys)
|(p==q) = (p,n+m):amerge xs ys
|(p<q) = (p,n) :amerge xs ((q,m):ys)
|otherwise = (q,m) :amerge ((p,n):xs) ys
-----

---freqmerge (iii) sortiert nach der häufigkeit der chars
freqmerge :: [(Char,Int)]->[(Char,Int)]->[(Char,Int)]
freqmerge xs []=xs
freqmerge [] ys=ys
freqmerge ((p,n):xs) ((q,m):ys)
|(n<m ||(n==m && p<q)) =(p,n):freqmerge xs ((q,m):ys)
| otherwise =(q,m):freqmerge((p,n):xs) ys

--frequency
add2list::[Char]->[(Char,Int)]
add2list =mergesort freqmerge . mergesort amerge . map start
where start ch =(ch,1) --(i)

also die funktionen die ich dir gegeben hab machen also soweit das richtige ;)
gruß jacke

Zum Seitenanfang

Bidrohi

Gepostet:
22.05.2005 16:49

ok bin jetzt endlich weiter un von sortieren weg ^^....naja kommt das machen eines baums -.-

so

makeZeichenliste :: String -> [Char]
makeZeichenliste xs = mklist (add2list xs) []

mklist :: [(Char,Int)] -> [Char]->[Char]
mklist [] liste=liste
mklist ((x,n):xs) liste= mklist xs (liste++[x])

---mergesort zum sotieren

--mergesort::([a]->[a]->[a])->[a]->[a]

mergesort merge xs
| length xs<2 = xs
| otherwise
= merge (mergesort merge first) (mergesort merge second)
where
first = take half xs
second= drop half xs
half = (length xs) `div` 2

----end mergesort

---zum zusammenfassen der tupel also [(a,1),(a,1)] wird zu [(a,2)] und sortieren der liste die kleinen zahlen immer vorne

amerge::[(Char,Int)]->[(Char,Int)]->[(Char,Int)]
amerge xs []=xs
amerge [] ys=ys
amerge ((p,n):xs) ((q,m):ys)
|(p==q) = (p,n+m):amerge xs ys
|(p<q) = (p,n) :amerge xs ((q,m):ys)
|otherwise = (q,m) :amerge ((p,n):xs) ys

---freqmerge fehlt
freqmerge :: [(Char,Int)]->[(Char,Int)]->[(Char,Int)]
freqmerge xs []=xs
freqmerge [] ys=ys
freqmerge ((p,n):xs) ((q,m):ys)
|(n<m ||(n==m && p<q)) =(p,n):freqmerge xs ((q,m):ys)
| otherwise =(q,m):freqmerge((p,n):xs) ys

--frequency

add2list::[Char]->[(Char,Int)]
add2list =mergesort freqmerge . mergesort amerge . map start
where start ch =(ch,1)

--ende

data HTree = Blatt Char Int | Knoten HTree Int HTree
deriving (Eq, Show)

makeBlatt :: Char -> HTree
makeBlatt (c,n) = Blatt c n

list2tree :: [Char] -> [HTree]
list2tree xs = map makeBlatt xs

gewicht :: HTree -> Int
gewicht (Blatt c n) = n
gewicht (Knoten li n re) = n

verschmelzen :: HTree -> HTree -> HTree
verschmelzen b1 b2
| n1 >= n2 = Knoten b1 (n1+n2) b2
| otherwise = Knoten b2 (n1+n2) b1
where n1 = gewicht b1
n2 = gewicht b2

insTreeInList :: HTree -> [HTree] -> [HTree]
insTreeInList b [] =
insTreeInList b (x:xs)
| gewicht b <= gewicht x = b:x:xs
| otherwise = x:insTreeInList b xs

mkHTree :: [HTree] -> [HTree]
mkHTree [b] = [b] -- Stoppfall
mkHTree (b1:b2:bs) = mkHTree (insTreeInList b bs)
where b=verschmelzen b1 b2

makeHuffmantree :: [Char] -> HTree
makeHuffmantree xs = head (mkHTree (list2tree xs))

kodieren :: String -> (String,HTree)
kodieren xs = (kodieren1 xs htree,htree)
where htree = makeHuffmantree (makeZeichenliste xs)

kodieren1 :: String -> HTree -> String
kodieren1 [] b = []
kodieren1 (x:xs) b = (code b x)++kodieren1 xs b

code :: HTree -> Char -> String
code (Blatt c n) x
| c==x = []
| otherwise = error "Zeichen nicht in Baum enthalten"
code (Knoten li n re) x
| member x li = '1':code li x
| otherwise = '0':code re x
where member a (Blatt c n) = (a==c)
member a (Knoten li c re) = (member a li) || (member a re)

k nun hab ich bei
makeBlatt :: Char -> HTree
makeBlatt (c,n) = Blatt c n
das problem

Type error in explicitly typed binding

*** Term : (c,n)
*** Type : (a,b)
*** Does not match : Char

klar verstehe ich er kann nicht damit umgehen das es tupel sind ich weiß auch den grund...klar....ich hab ja jetzt die version in der diese sortiererei ne char liste macht, aber da Blatt wieder mit den Tupeln arbeitet (glaub ich) vom typ Char,Int kommt halt dieser fehler....aber andersrum mit der methode oben kommt ich auch net weiter da Makehuffmantree [Char] braucht

Zum Seitenanfang

Jacke

Gepostet:
22.05.2005 17:41

makeBlatt :: (Char,Int) -> HTree
makeBlatt (c,n) = Blatt c n

gruß jacke

Zum Seitenanfang

Bidrohi

Gepostet:
22.05.2005 19:27

joar hab ich auch versucht klappt aber net

ERROR "C:\WINDOWS\Desktop\hugs\wuff3.hs":63 - Type error in application
*** Expression : map makeBlatt xs
*** Term : makeBlatt
*** Type : (Char,Int) -> HTree
*** Does not match : Char -> HTree

Zum Seitenanfang

Jacke

Gepostet:
23.05.2005 12:39

makeBlatt :: Char -> HTree
makeBlatt (c,n) = Blatt c n

list2tree :: [Char] -> [HTree]
list2tree xs = map makeBlatt xs<---das problem liegt hier

wenn du ne liste von chars in nen baum umwandlen willst geht das natürlich nich da ein blatt aus der häufigkeit und nen Int besteht

makeBlatt :: (Char,Int) -> HTree
makeBlatt (c,n) = Blatt c n

list2tree :: [(Char,Int)] -> [HTree]
list2tree xs = map makeBlatt xs

eigentlich willst du ja das richtige machen vergibst aber dafür die falschen typen...

gruß jacke

Zum Seitenanfang

Bidrohi

Gepostet:
24.05.2005 19:58

juhuh jetzt hab ich allle fehler rausbekommen, thx ^^.......aber omg dieses Huffman verfahren staucht schon, besonders die typen, da bin ich durcheinander gekommen, naja zum glück gibt es nette studenten wie dich die nem kleinem abi anwärter aushelfen :) , werd aber weiter üben an was anderem ...ma schaun

Zum Seitenanfang

vorherige Seite

1 2

Haskell-Forum