Archive for July, 2006


Since Jordan did a post on his implementation of LZW I figured I had to as well. I’ll try to make mine more of show off of Haskell’s cool features as well. One of my favorite features of Haskell is the pattern matching in function definitions. Take the first function of my LZW program:

compress [] w dict = dict
compress str w dict =
let k = [(head str)]
wk = (w++k)
c = myfind wk dict in
if c /= -1 then
compress (tail str) wk dict
compress (tail str) k (dict_append dict wk)

This will match against a str that is sent to compress. If that string is empty, [], it will simply return the final dict, if it contains characters it continues with the algorithm. Jordan went into how the algorithm works so I’ll show you the rest of my code and describe how it works.

myfind s [] = -1
myfind (x:[]) _ = -2
myfind s ((c,w):xs) = if w == s then c else myfind s xs

dict_append [] (x:[]) = []
dict_append [] s = [(256, s)]
dict_append dict s = dict++[((length dict)+256, s)]

myfind takes a string and the dictionary. Then, tests to see if the string is already in the dictionary. If it is it’ll return the code associated with that string. This is where pattern matching comes into play. ((c, w):xs) will put the two values of the lists first tuple in variables c and w respectively. Then, I can test if the string argument, s, is the same as w. If the string argument sent to myfind is only a single character, (x:[]), it will return -2, if myfind is called with an empty dictionary it returns -1.

The last function needed is dict_append. This simply adds the string and its code to the dictionary, which is simply a list of tuples (code, string). If the dictionary is empty, [], and the string is only a single character, (x:[]) it does not add anything. If the dictionary is empty but the string is a full string it adds it as the first element. If the dictionary is not empty and the string is full it appends the tuple to the list, ++, finds the code, (length dict)+256, and creates a tuple of that code and the string.

Pretty simple uh? Haskell allows us to do this program in an amazingly small amount of code. Now all you have to do is call compress like:

compress “^WED^WE^WEE^WEB^WET” “” []

and it’ll return the final dictionary for compression. I know this threw a lot at you at once, but I hope it can impress you with the power of Haskell. Dealing with tuples and lists is amazingly simple and the pattern matching not only makes manipulating data structures easier but it makes the code a lot smaller.


Read Full Post »

Tilda 0.09.3

Tilda 0.09.3 is out. You can find the source here. If you want a distro specific package it can already be found in gentoo, more distro will follow, simple google search should find you .debs and .rpms. The Changelog contains all the enhancements/fixes.

Read Full Post »