- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
by Andrew Coppin 13 Jul '07

13 Jul '07

Bulat Ziganshin wrote: > Hello Andrew, > > Sunday, July 8, 2007, 3:10:04 PM, you wrote: > >> Indeed. I'm more interested in which algorithms produce the best >> compression ratios than how to implement them fast. >> > > algorithms you are tried so far (except for bwt+mtf) is the standard > student's set :) of those, lzw is most advanced, but even this > algorithm is 20-year old > Yeah, well, naturally I'm implementing the simple ones first. ;-) Actually, LZW works surprisingly well for such a trivial little algorithm... When you compare it to the complexity of an arithmetic coder driven by a high-order adaptive PPM model (theoretically the best general-purpose algorithm that exists), it's amazing that anything so simple as LZW should work at all! >> Currently the code >> uses very general, flexible, polymorphic types all over the place, >> everything is normal lists, I'm using monadic parsing rather than >> bit-twiddling, etc etc etc. It goes alright with 100 KB files on my >> > > testing today's algorithms on such small datasets don't make much > sense because they need much more input to gather enough statistics > about data compressed. i prefer hundreds-megabytes tests and don't > know anyone with a test files smaller than 1 mb > OTOH, I'd like it to finish this month... (LZW is faster now I'm using Data.Map. But even so, 15 minutes to compress 640 KB of zeros? That's pretty slow!) > btw, in most cases, C algorithm with today's C compilers will work > faster than asm oe - because you should have very good knowledge of > COU internals to write efficient program. i dream about the days when > the same will become true for Haskell > We all do... *sigh* (Or rather, most of us dream. A tiny few people seem to be trying to actually do stuff about it...) > i never heard about lzw+huf compressors :) there are two lz families > - lz78 (lzw) which was popular in 80's and used variable-size words, > and lz77 (lzss) which together with huffman was the most popular in > 90's. compress (.Z) and pkzip 1 was lzw, while zip is lzh (i.e. > lz77+huffman) > > there is no much meaning to use huffman with lzw because many words > will have only one or two occurrences > Hmm... that's interesting. I was *sure* it said that LHA used LZW+Huffman... oh well! You say that there would be "no meaning" to using a Huffman code to encode the output from an LZW stage. But consider this: The standard approach is for the LZW encoder to spit out 9 bits/symbol initially, and than 10 bits/symbol once the table fills up a bit more, and then 11 bits/symbol after that, and so on. (Usually until some hard-coded limit is reached. Typically the encoder just resets itself at that point or something.) So we're allocating more and more bits per symbol, but this is based only on how full the table is, *regardless* of whether any of these new symbols are even in fact *used*. ;-) Now, by using a Huffman code (scanning the actual produced output rather than working adaptively) we can avoid assigning bit combinations to unused symbols. (The downside of course is that now we need a Huffman table in the output - and any rare symbols might end up with rather long codewords. But remember: Huffman *guarantees* 0% compression or higher on the payload itself. A Huffman-compressed payload can *never* be bigger, only smaller or same size. So long as you can encode the Huffman table efficiently, you should be fine...) > btw, i invite you to the http://encode.ru/forums where you will find > many compressor authors. you will be second one there who use haskell > and first one who write compression algorithms in it :) > .ru = Russia? >> OTOH, if the Gods behind GHC want to take a look and figure out whether >> there's any magic that can be added to the optimiser, I wouldn't >> complain... ;-) >> >> (Realistically though. My program takes a [Word8] and turns it into a >> [Bool] before running a parser over it. The GHC optimiser doesn't really >> stand a hope in hell of optimising that into a program that reads a >> machine word into a CPU register and starts playing with bit flips on it...) >> > > as time goes, those terrible compilers becomes smarter and smarter :) > Oh hey, I think GHC is already pretty smart. But no optimiser can ever hope to cover *every* possible case. And transforming [Bool] -> [Bool] into UArray Word8 -> UArray Word8 just seems a liiiiittle bit optimistic, methinks. ;-) > >> PPS. Does GHC make use of MMX, SSE, et al? >> > > it can do it with via-c compilation and there are plans for native > codegenerator too. The way I heard it is that it *does* native code generation, but it's "not as good" as the via-C version. (Can't imagine why... You would have thought directly implementing functional primitives would be much easier than trying to mangle them to fit C's multitude of limitations. Still, what do I know?) > but it seems that you don't know asm and believe in > advertising hype. i'm pretty sure that mmx can't help in algorithms > you implementing and you are very far from level of performance where > using mmx may give any improvement > MMX is probably useless. Some of the streaming stuff (with all the CPU cache twiddling and so on) might be useful for list processing. Frankly, it *all* seems so low-level that I can't begin to imagine how you could ever take advantage of this stuff without writing raw assembly by hand... (I read the IA32 manual one time. It was a long time ago though. I don't remember lots of detail. As for do I "know assembly"... I've programmed the 6502 and the M68000, although not extensively. My point is that I know my way round the inside of a von Neumann computers, that's all... ;-)

6 25

Very freaky
by Andrew Coppin 13 Jul '07

13 Jul '07

OK, so technically it's got nothing to do with Haskell itself, but... I was reading some utterly incomprehensible article in Wikipedia. It was saying something about categories of recursive sets or some nonesense like that, and then it said something utterly astonishing. By playing with the lambda calculus, you can come up with functions having all sorts of types. For example, identity :: x -> x add :: x -> x -> x apply :: (x -> y) -> (y -> z) -> (x -> z) However - and I noticed this myself a while ago - it is quite impossible to write a (working) function such as foo :: x -> y Now, Wikipedia seems to be suggesting something really remarkable. The text is very poorly worded and hard to comprehend, but they seem to be asserting that a type can be interpreted as a logic theorum, and that you can only write a function with a specific type is the corresponding theorum is true. (Conversly, if you have a function with a given type, the corresponding theorum *must* be true.) For example, the type for "identity" presumably reads as "given that x is true, we know that x is true". Well, duh! Moving on, "add" tells as that "if x is true and x is true, then x is true". Again, duh. Now "apply" seems to say that "if we know that x implies y, and we know that y implies z, then it follows that x implies z". Which is nontrivial, but certainly looks correct to me. On the other hand, the type for "foo" says "given that some random statement x happens to be true, we know that some utterly unrelated statement y is also true". Which is obviously nucking futs. Taking this further, we have "($) :: (x -> y) -> x -> y", which seems to read "given that x implies y, and that x is true, it follows that y is true". Which, again, seems to compute. So is this all a huge coincidence? Or have I actually suceeded in comprehending Wikipedia?

18 32

Re: Numbers : [Haskell-cafe] Number overflow
by Carter T Schonwald 12 Jul '07

12 Jul '07

Out of curiosity, what ever happened to the proposal a while back to refactor the Num class etc so that the operations would be grouped according to what abstract algebra notions they correspond to? My understanding was that doing this would make haskell numerics much more sensible. Eg array indexing could be done by any type that is isomorphic to natural numbers etc. cheers, -Carter ----- Original Message ---- From: Lennart Augustsson <lennart(a)augustsson.net> To: Bulat Ziganshin <Bulat.Ziganshin(a)gmail.com> Cc: haskell-cafe(a)haskell.org Sent: Thursday, July 12, 2007 4:14:31 PM Subject: Re: Re[2]: [Haskell-cafe] Number overflow Of course you should be able to specify what types you want. But it would be nice if the default was correct rather than fast. On 7/12/07, Bulat Ziganshin <bulat.ziganshin(a)gmail.com> wrote: Hello Thomas, Thursday, July 12, 2007, 3:14:57 AM, you wrote: > The differences between Int and Integer operations are mostly constant factors. well, i will be unlucky if in my real-world program Integers would be used instead of Ints. defaulting provides a great way to solve this dilemma, so good-for-anyone approach may be: default defaulting to Integer instead of Int, and use (Num a) instead of Int in all standard functions such as length. with jhc-like automatic specialization feature this should provide enough speed -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

3 2

Very freaky
by Dominic Steinitz 12 Jul '07

12 Jul '07

>> >> They are just too big. The set of all sets can't exist, you know. >> > > That's news. > It was news to Frege. > How come the set of all sets doesn't exist? > Russell's paradox - see e.g. Halmos: Naive Set Theory.

1 0

Very freaky
by Dominic Steinitz 12 Jul '07

12 Jul '07

> Alexis Hazell wrote: > > On Thursday 12 July 2007 04:40, Andrew Coppin wrote: > >> I once sat down and tried to read about Category Theory. I got almost > >> nowhere though; I cannot for the life of my figure out how the > >> definition of "category" is actually different from the definition of > >> "set". Or how a "functor" is any different than a "function". Or... > >> actually, none of it made sense. > > > > Iiuc, > > > > "Set" is just one type of category; and the morphisms of the category > > "Set" are indeed functions. But morphisms in other categories need not be > > functions; in the category "Rel", for example, the morphisms are not > > functions but binary relations. > > > > A "functor" is something that maps functions in one category to functions > > in another category. In other words, functors point from one or more > > functions in one category to the equivalent functions in another > > category. Perhaps they could be regarded as 'meta-functions'. > > > > Hope that helps, > > It helps a little... > > I'm still puzzled as to what makes the other categories so magical that > they cannot be considered sets. Another example: a partially ordered set is a category. The objects are the elements and there is an arrow between two objects a & b if a <= b. An element isn't (necessarily) a set. Nothing magical here. A functor is then an order preserving function (homomorphism). This question has come up more than once so it may be worth a wiki page if anyone has time. > > I'm also a little puzzled that a binary relation isn't considered to be > a function... That's the definition of a function: a restricted relation in which there is at most one range element for a given domain element - see any book on set theory e.g. Halmos. > > From the above, it seems that functors are in fact structure-preserving > mappings somewhat like the various morphisms found in group theory. (I > remember isomorphism and homomorphism, but there are really far too many > morphisms to remember!) Sometimes but clearly the forgetful functor doesn't.

1 0

Re: [Haskell-cafe] Simple newbie question - Int and Integer
by Gregory Propf 12 Jul '07

12 Jul '07

Heh, talk about overflow behavior. Here's what GHC does on my 64 bit machine. Note: you need to turn on -fglasgow-exts to force the types this way interactively. As for the tutorials, I have like 10 of them open in different Firefox tabs to different places. Mostly I've been reading up on IO, Monads and other advanced stuff while ignoring basic things I probably should have learned first. Prelude> let i::Int = 2^62 Prelude> i 4611686018427387904 Prelude> let i::Int = 2^63 Prelude> i -9223372036854775808 Prelude> let i::Int = 2^64 Prelude> i 0 Prelude> let i::Int = 2^100 Prelude> i 0 Clearly a job for Integer. -Greg ----- Original Message ---- From: Stefan O'Rear <stefanor(a)cox.net> To: Andrew Coppin <andrewcoppin(a)btinternet.com> Cc: haskell-cafe(a)haskell.org Sent: Thursday, July 12, 2007 11:48:15 AM Subject: Re: [Haskell-cafe] Simple newbie question - Int and Integer On Thu, Jul 12, 2007 at 07:39:09PM +0100, Andrew Coppin wrote: > Gregory Propf wrote: >> So what the hell is the difference between them? Int and Integer. They >> aren't synonyms clearly. What's going on? > > Int = 32-bit integer. Int = 30 bits with undefined overflow behavior That "undefined" gives implementations the freedom to use bigger representations if convenient. GHC: 31, 32 or 64 bits (from source code) Hugs: 32 bits (only tested on a 32 bit computer) YHC: 32 or 64 bits (from source code) JHC: Buggy (maxBound :: Int is negative) Stefan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ____________________________________________________________________________________ Bored stiff? Loosen up... Download and play hundreds of games for free on Yahoo! Games. http://games.yahoo.com/games/front

1 0

Re: [Haskell-cafe] Simple newbie question - Int and Integer
by Gregory Propf 12 Jul '07

12 Jul '07

Thanks, I didn't see it in the tutorials I've been reading but I'm sure it's there and I just missed it. ----- Original Message ---- From: Brent Yorgey <byorgey(a)gmail.com> To: Gregory Propf <gregorypropf(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Sent: Thursday, July 12, 2007 11:14:22 AM Subject: Re: [Haskell-cafe] Simple newbie question - Int and Integer To be more precise, Int represents a machine-sized integer value, so it is limited in size but doing math with Int values translates directly into math on the processor. Integer can store integer values of arbitrary size, which is useful sometimes but is of course a lot slower, since the pieces of an Integer value have to be stored in some sort of list, and specialized code is used to do arithmetic with Integers by operating on the pieces and combining the results. How have you been learning Haskell? I'm guessing this is probably covered in most tutorials. -Brent ____________________________________________________________________________________ Expecting? Get great news right away with email Auto-Check. Try the Yahoo! Mail Beta. http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html

1 0

Re: [Haskell-cafe] Very freaky
by Andrew Coppin 12 Jul '07

12 Jul '07

Bernie Pope wrote: > > On 12/07/2007, at 4:43 AM, Andrew Coppin wrote: > >> Bernie Pope wrote: >>> >>> This reminds me of a little joke that Conor McBride had in a post a >>> while ago: >>> >>> unJust :: Maybe wmd -> wmd >> >> Oh, very good! >> >> I must write that down somewhere... > > I tell it to my Haskell students each semester and it usually gets a > giggle. I also ask them why is it possible to write jokes in Haskell's > types, which often leads to some interesting discussions about logic > and the nature of jokes etc. I told it to the guys on the POV-Ray forum. Sadly, I think most of them have by now set up filters to delete all posts containing words such as "Haskell"...

1 0

unresolved overloading
by Crediné Menezes 12 Jul '07

12 Jul '07

I have written this code in Haskell which gives an unresolved overloading error. g x = [2] ++ [3,5..truncate(sqrt x)] p n = fp n (g n) fp n [ ] = True fp n (x:xs) = if (mod n x) == 0 then False else fp n xs when I submit g 103 I get: [2,3,5,7,9] :: [Integer] when I submit: fp 103 (g 103) I get True :: Bool But when I submit : p 103 I get ERROR - Unresolved overloading *** Type : (RealFrac a, Floating a, Integral a) => Bool *** Expression : p 103 I know why, there is no type that is at the same time: RealFrac, Floating and Integral; but I don´t know how to solve. What kind of type casting or type definition can I use to fix the error? Thanks, Crediné Menezes

4 3

Floating phi, round and even Fibonnaci numbers
by Brian L. Troutwine 12 Jul '07

12 Jul '07

I'm rather new to Haskell and need, in typical newbie style, a bit of help understanding the type system. The Nth even Fibonacci number, EF(n) can be defined by the recursive relation EF(0) = 2, EF(n) = [EF(n-1) * (phi**3)], where phi is the golden ratio and [] is the nearest integer function. An infinite lazy list of this sequence would be nice to have for my Project Euler, er, project. Defining phi thusly, > phi :: (Floating t) => t > phi = (1+sqrt(5))/2 With phi in place, if I understood types properly (and if I understand iterate correctly as I think), the lazy list should be a relatively quick matter. > even_fibs :: (Num t) => [t] > even_fibs = iterate (\x -> round(x * (phi**3))) 2 Dynamically typed even_fibs :: (Floating t, Integral t, RealFrac t) => [t], assuming I pass -fno-monomorphism-restriction to ghci. That's not at all the type I assumed even_fibs would take, as can be seen from above. So, I went on a bit of sojourn. Having seen the sights of the Haskell Report section 6.4, the marvels of the references cited in the wiki's article on the monomorphism restriction and the Gentle Introduction's chapter 10 I must say I'm rather more terribly confused than when I started out, possibly. Can someone explain where my type statements have gone wrong?

4 8