kubbe 2017-02-10 07:50:17
The problem is that I dont really know how to create my huffman tree.
cocreature 2017-02-10 07:57:37
kubbe: so you are looking for a function of type "Table k v -> Tree k v"?
cocreature 2017-02-10 07:57:57
or Table Char Int -> HuffmanTree?
kubbe 2017-02-10 07:57:57
Yes!
kubbe 2017-02-10 07:58:09
exactly. I need help with figuring that one out at the moment
cocreature 2017-02-10 08:01:08
kubbe: are you familiar with how you build a huffman tree given the letters you are trying to encode and the number of their occurences? (on a conceptual level, not in haskell)
Boomerang 2017-02-10 08:01:19
kubbe: You have to start with an empty HuffmanTree (Void) and add entries in the form of Leafs and Node one by one. To get an optimal Huffman Tree you want the two branches of each Node to have more or less the same weight. The weight is the sum of the weight from the two branches. When adding a new entry, if the current Node has the same weight as the entry put them side by side in two branches, if
Boomerang 2017-02-10 08:01:25
not recurse down one of them to add the entry and propagate the weight change back up. I think this is how the algorithm goes, I would write the code but I think this is an assignement
kubbe 2017-02-10 08:02:37
cocreature: Well, I think so yes!
cocreature 2017-02-10 08:03:28
kubbe: are the functions in the PrioQueue already implemented or do you need to implement them yourself?
cocreature 2017-02-10 08:04:01
oh nvm they are at the bottom
kubbe 2017-02-10 08:04:08
they are done! yeah
cocreature 2017-02-10 08:04:30
kubbe: well in that case, you already have all the building blocks needed for the algorithm. so where are you stuck?
kubbe 2017-02-10 08:05:08
So I guess I like need to use PQ-functions
cocreature 2017-02-10 08:05:27
kubbe: take a look at the first algorithm here https://en.wikipedia.org/wiki/Huffman_coding#Compression
kubbe 2017-02-10 08:05:28
to start to how to create the tree! like Boomerang says, that algorithm is correct
kubbe 2017-02-10 08:05:36
but I am not sure how to start the code...
cocreature 2017-02-10 08:06:19
kubbe: so let's go through this step by step. what should initially be stored in the priority queue?
Boomerang 2017-02-10 08:06:43
You can think of it as a fold of insert on an empty tree (after the priority queue)
kubbe 2017-02-10 08:07:32
in the PQ it should store a lists of tuples with 1 polymorphic value and 1 int. the poly-value is in our cases always a character
cocreature 2017-02-10 08:08:47
kubbe: you first need to decide which algorithm description you follow. the one Boomerang described is slightly different than the one described on wikipedia
Boomerang 2017-02-10 08:09:20
I didn't read Wikipedia, definitely trust it over what I said (just wrote it from memory)
kubbe 2017-02-10 08:10:32
Okey! Well, our assignment says that the character that occur the least amount of times is at the bottom of the tree. Then it should be the algorithm from wikipedia?
cocreature 2017-02-10 08:12:21
kubbe: alright, let's go with that. so you said that your priority queue contains characters (and their weight) but this is not correct. take a look at step 2.3 and think about the type of the thing you are inserting here
kubbe 2017-02-10 08:14:04
Just to make things clear: highest priority = highest int = closest to the root?
cocreature 2017-02-10 08:15:32
no, highest prriority = smallest int
cocreature 2017-02-10 08:15:48
your priority gives you a "least" operation not a "max" operation
kubbe 2017-02-10 08:16:11
But yes, I understand that step.. I think. So we are supposed to take out the 2 tuples with the highest priority, add the two INT's and then create a new NODE holding that INT?
monochrom 2017-02-10 08:16:49
w00t, min priority queue vs max priority queue?
cocreature 2017-02-10 08:17:00
kubbe: right, so you are adding a Node to your priority queue, so the type of the things it holds can't be Char
kubbe 2017-02-10 08:18:58
Hmm.. well no! But it is polymorphic so it can be anything then? It should be of type leaf then
kubbe 2017-02-10 08:19:02
not Char
cocreature 2017-02-10 08:21:42
kubbe: Leaf is not a type
Younder 2017-02-10 08:22:00
Tree is the type?
monochrom 2017-02-10 08:22:21
Yes
Younder 2017-02-10 08:22:26
Sorry for barging in.
kubbe 2017-02-10 08:22:43
Oh yeah, ofc. Tree is the type!
monochrom 2017-02-10 08:22:49
No problem, it's a long conversation, and even I only know a bit.
kubbe 2017-02-10 08:22:56
Its fine Younder
kubbe 2017-02-10 08:23:32
monochrom, this conversation havnt been so long today :D
monochrom 2017-02-10 08:24:06
I just mean more than 5 minutes
kubbe 2017-02-10 08:24:23
haha, oh
cocreature 2017-02-10 08:25:27
kubbe: alright, so what should initially be in the priority queue?
kubbe 2017-02-10 08:26:35
a bunch of trees?
cocreature 2017-02-10 08:26:53
kubbe: but which trees and with which priority?
cocreature 2017-02-10 08:27:50
remember that you are given a Table Char Int
kubbe 2017-02-10 08:30:34
cocreature: ehmm... well I guess the sub-trees that is holding the character and the priority. the priority is the same as the value of how many times the character is in the string that I input
cocreature 2017-02-10 08:32:27
kubbe: exactly, so start by writing a function "Table Char Int -> PriorityQueue HuffmanTree" that produces that initial priority queue
kubbe 2017-02-10 08:34:48
Yeah alright, so some sort of help-function in addition to the huffmanTree
monochrom 2017-02-10 08:37:13
Wait a second, PriorityQueue HuffmanTree doesn't look right.
monochrom 2017-02-10 08:38:14
Isn't it supposed to be, conceptually, Table Char Int -> PriorityQueue Char, and then PriorityQueue Char -> HuffmanTree?
cocreature 2017-02-10 08:39:11
monochrom: no, you keep removing the two huffman trees with the least weight from the queue, create a new tree and insert that back in the queue
cocreature 2017-02-10 08:39:16
once there is only one tree left you are done
cocreature 2017-02-10 08:39:34
you can ofc insert a PriorityQueue Char step in between but that's not really helpful
monochrom 2017-02-10 08:39:54
Oh, that's neat.
kubbe 2017-02-10 08:41:40
But the first line of code, my base-case in that helpfunction...
kubbe 2017-02-10 08:41:48
what is that? In haskell
cocreature 2017-02-10 08:42:56
kubbe: your basecase is the empty Table
kubbe 2017-02-10 08:43:10
I have discussed it with my grouppartner and we are not really sure where to start. Since how do I take out the huffmantrees from the Table Char Int
cocreature 2017-02-10 08:43:40
kubbe: do you know how you can pattern match on a list?
kubbe 2017-02-10 08:44:08
well yes, but not on a Table
Boomerang 2017-02-10 08:44:22
I think the point of Table is to hide the fact that it's implemented with a list, you should use the functions you created
Boomerang 2017-02-10 08:44:34
You can build your PQ using Table.iterate
cocreature 2017-02-10 08:44:39
oh right, you are probably supposed to use "iterate"
emilymhorsman 2017-02-10 08:44:51
I'm using Snap and it uses strict `Data.ByteString`s for everything (as opposed to lazy ones). I'm trying to convert an Int to a strict ByteString. I have `toStrict . toLazyByteString . intDec` which works, but I'm wondering if there's a better way.
volhovm 2017-02-10 08:45:02
Hello everyone. I wonder is there anything one can say _in general_ about lazy transformers in stack -- should they be used, or it's better to use strict versions?
