July 2007 - Haskell-Cafe

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

13 Jul '07

> AC> I'm still puzzled as to what makes the other categories so magical > AC> that they cannot be considered sets. > > They are just too big. The set of all sets can't exist, you know. > That's news. How come the set of all sets doesn't exist? > Well, you mentioned that you have some knowledge of group theory, so > let me give you three examples of adjoint functors (don't worry, it > won't hurt) - two from the group theory and one related to Haskell. > > 1) Consider the category Set of all sets - it's objects are sets and > it's morphisms (=arrows) are functions between sets. Also, there is a > category Grp of groups - with groups as objects and homomorphisms as > morphisms. Then, the trivial mapping G: Grp -> Set, which maps each > group to it's base set (and each homomorphisms to itself - as a > function from one base set to another) is a functor (it is called > "forgetting functor", I guess, since it "forgets" the group > structure). > > There is a very natural functor F: Set -> Grp. Namely, F maps each set > X to the free group, with generators corresponding to elements of X. > By definition, each function f:X->H, where H is a group, can be > extended to the homomorphism f*:F(X)->H. That means that there is a > natural bijection between functions X->H (more precisely, from X to > G(H), since these functions aren't related to the group structure on > H) and homomorphisms F(X)->H: > > Set(X,G(H)) ~ Grp(F(X),H) > > Here by Grp(H1,H2) I denote the set of morphisms (=homomorphisms) from > H1 to H2; the same notation is used for Set. > > That means exactly that F is LEFT ADJOINT to G (or, equivalently, G is > right adjoint to F). > > Their composition GF is a monad on the category Set. GF(X) is the set > of all elements of the free group, generated by X. For a in X, > return(x) is an element of the free group, corresponding to x. And if > we have a map X->GF(Y) and an element of GF(X), we can remember that > GF(Y) carries some group structure, so our map is in fact a map from X > to some group, which extends to a homomorphism from F(X) to F(Y), > which is a map from GF(X) to GF(Y), which maps our chosen element of > GF(X) to an element of GF(Y) - that gives us (>>=). > That almost made sense most of the way through... but... ooouch... x_x > 2) There is a category Ab of abelian groups (and homomorphisms). Of > course, there is a trivial functor G: Ab -> Grp, which maps each > abelian group to itself. There is also a functor F: Grp -> Ab; it maps > each group H to it's "abelianization": F(H) = H/[H,H]. F is also left > adjoint to G: there is a bijection between homomorphisms H -> A, where > A is abelian, and homomorphisms H/[H,H] -> A. Again, there composition > GF: Grp -> Grp is a monad (on Grp this time). > > There are many other constructions that happen to be adjoint functors; > and that is a kind of generalization that makes mathematics so useful > and exciting. These constructions include all kinds of "free" > structures - free modules, algebras etc.; discrete and codiscrete > topological spaces, and many others. > > 3) Let X be a set. I'll denote here the set of all functions from X to > Y by X->Y, and the product XxY (small x stands here for the "times" > sign) by (X,Y), sticking to the Haskell notation. Then the functor > (X ->): Set -> Set which maps each set Y to the set X->Y, is right > adjoint to the functor (,X), mapping each set Y to (Y,X): there is a > bijection between functions from Z to (X->Y) and functions from (Z,X) > to Y. This bijection is called "currying". The composition of this > functors is - as always - monad: it maps Y to X->(Y,X). And this is a > kind of monad we are familiar with: it's the State monad. Summarizing, > we have the following: State monad exists because of currying. > Again... that almost makes some sort of sense... but this is REALLY making my head hurt!

7 7

xkcd #287 "NP-Complete"
by Albert Y. C. Lai 13 Jul '07

13 Jul '07

http://xkcd.com/c287.html import Data.Array import Control.Monad -- exactly n v -- items in v that sum to exactly n -- returns list of solutions, each solution list of items exactly :: (Real a) => a -> Array Int a -> [[a]] exactly 0 v = return [] exactly n v = do i <- indices v guard (v!i <= n) liftM (v!i :) (exactly (n - v!i) (v `without` i)) -- for solutions that use items multiple times, -- change (v `without` i) to v -- v `without` i -- new array like v except one shorter with v!i missing without :: Array Int a -> Int -> Array Int a without v i = ixmap (lo, hi-1) f v where (lo, hi) = bounds v f j | j >= i = j+1 | otherwise = j play = exactly 1505 menu menu = listArray (1,6) [215, 275, 335, 355, 420, 580] test = exactly 10 (listArray (1,5) [1,1,2,3,4]) It disappoints me that there is no solution if each item is used at most once. However, do change the code to allow multiple uses, then there are many solutions.

6 13

function unique
by Alexteslin 13 Jul '07

13 Jul '07

Hi, i am a beginner to Haskell and i have a beginner's question to ask. An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work. unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1] elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el] //This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

14 33

Lazy Lists and IO
by Ronald Guida 13 Jul '07

13 Jul '07

Hi Everyone, A few weeks ago, I started learning Haskell (and functional programming) on my own from the wealth if information on the internet. I recently read the paper "Why Functional Programming Matters" [1] and it led me to wonder how to input a lazy list. Suppose I have a function "f" that reads a lazy list, such that "f" only consumes as much of the list as it needs to. Laziness allows me to apply "f" to an infinite list without creating an infinite loop. Now I want to connect the console to "f", such that the list of inputs to "f" comes from the console, one item at a time. To create a specific example, lets suppose I want to read and accumulate the contents of a list, and I want to stop when the sum reaches or exceeds a specified cutoff. I can write this as a function that reads elements from an infinite list: > accumUntilCutoff :: Integer -> [Integer] -> (Integer, [Integer]) > accumUntilCutoff cutoff xs = accumHelper cutoff 0 id xs > where > accumHelper :: {- cutoff -} Integer -> > {- sum so far -} Integer -> > {- elements so far -} ([Integer] -> [Integer]) -> > {- remaining list -} [Integer] -> > {- outputs -} (Integer, [Integer]) > accumHelper cutoff sum elems [] = (sum, elems []) > accumHelper cutoff sum elems (x:xs) = > if sum < cutoff > then accumHelper cutoff (sum + x) (elems . (x:)) xs > else (sum, elems []) Example: GHCi> accumUntilCutoff 20 [1..] ==> (21,[1,2,3,4,5,6]) GHCi> accumUntilCutoff 20 ([1..6] ++ repeat undefined) ==> (21,[1,2,3,4,5,6]) [This demonstrates that accumUntilCutoff is lazy) Alternatively, I can write a function that (1) prompts the user to enter numbers until the running sum reaches the cutoff, and then (2) returns the results in the IO monad. > readUntilCutoff :: Integer -> IO (Integer, [Integer]) > readUntilCutoff cutoff = readHelper cutoff 0 id > where > readHelper :: {- cutoff -} Integer -> > {- sum so far -} Integer -> > {- elements so far -} ([Integer] -> [Integer]) -> > {- outputs -} IO (Integer, [Integer]) > readHelper cutoff sum elems = do > if sum < cutoff > then do > putStr "Enter an integer: " > ln <- getLine > let x = read ln > readHelper cutoff (sum + x) (elems . (x:)) > else return $ (sum, elems []) Example: GHCi> readUntilCutoff 20 Enter an integer: 1 Enter an integer: 2 Enter an integer: 3 Enter an integer: 4 Enter an integer: 5 Enter an integer: 6 ==> (21,[1,2,3,4,5,6]) Here's my puzzle: I am dis-satisfied with the fact that I have to embed IO code in the middle of accumulation code. Is there some way to separate "readUntilCutoff" into two parts (e.g. functions), such that one part would look extremely similar to "accumUntilCutoff", while the other part would handle the user interaction associated with getting the next number? Thank you -- Ron Reference: [1] http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html

12 27

CGI test
by Andrew Coppin 13 Jul '07

13 Jul '07

Greetings. Can somebody write a trivial (as in: small) program so I can test my CGI stuff without having to actually install and configure Apache? (Basically, I'd like something I can compile into a small binary, so when I double-click it, it will listen on port 80, and when it gets a HTTP request, it tries to find a program with that name, and run it as a CGI script. And that's all. Nothing fancy; if I want fancy Apache can do a propper job...) Actually, might be a useful thing to have in a library somewhere.

6 7

reading existential types
by Andrea Rossato 13 Jul '07

13 Jul '07

Hi, I have a problem I cannot solve. I have a data type that I need to be readable, and the read instance derivable. I need it readable because it is going to be a data type for configuring at run time an application, and I want the application to read it when booting up. On the other side, I also need an existential type to be used within this data type: it is a list that must be polymorphic somehow. Since instances for existentially qualified types cannot be derived I thought to create a type that could be easily read. But I'm not able to write the parser, and I'm not sure if this is my fault or just a limitation I'm trying to futilely overcome. Below there's a piece of code that shows the problem. I'd like to be able to use MT to build a list like: [MT (T1a,1), MT (T1b,3)] And I'd like to read str with: read $ show str No way, and the code below compiles. Substituting return (m) with return (MT m) leads to error messages like: Ambiguous type variable `e' in the constraints What am I getting wrong? Is just the parser or there's something deeper? Thanks for your kind attention. All the best Andrea the code: ---------------------------------------------------------------- {-# OPTIONS -fglasgow-exts #-} module Test where import Text.Read import Text.ParserCombinators.ReadPrec data MyData = MD { rec1 :: String , rec2 :: String , rec3 :: [MyType] } deriving (Read,Show) data MyType = forall e . (MyClass e, Show e, Read e) => MT (e,Int) instance Show MyType where show (MT a) = "MT " ++ show a class MyClass c where myShow :: c -> String data TipoA = T1a | T2a | T3a deriving(Show,Read,Eq) instance MyClass TipoA where myShow T1a = "t1a" myShow T2a = "t2a" myShow T3a = "t3a" data TipoB = T1b | T2b | T3b deriving(Show,Read,Eq) instance MyClass TipoB where myShow T1b = "t1b" myShow T2b = "t2b" myShow T3b = "t3b" str :: MyData str = MD {rec1 = "Ciao", rec2 = "Ciao Ciao", rec3 = [MT (T1a,1), MT (T1b,3)] } instance Read MyType where readPrec = readMT readMT :: ReadPrec MyType readMT = prec 10 $ do Ident "MT" <- lexP parens $ do m <- readPrec return (m)

3 6

Re: [Haskell-cafe] Very freaky
by Dan Piponi 13 Jul '07

13 Jul '07

On 7/12/07, Andrew Coppin <andrewcoppin(a)btinternet.com> wrote: > Stefan O'Rear wrote: > > On Thu, Jul 12, 2007 at 07:19:07PM +0100, Andrew Coppin wrote: > > > >> I'm still puzzled as to what makes the other categories so magical that > >> they cannot be considered sets. I thought I'd dive in with a comment to explain why category theory is an important subject and why it often crops up in Haskell programming. The key thing is this: in many branches of mathematics people draw what are known as commutative diagrams: http://mathworld.wolfram.com/CommutativeDiagram.html So what do these diagrams represent? The letters at the 'vertices' (known as objects) often represent sets and the arrows represent functions. But in different branches of mathematics the same diagrams appear with the objects and arrows having a quite different interpretation. For example you could use a diagram like 1 -> 2 to mean 1<2. Or you could use X -> Y to mean X implies Y. Or in {1,2} -> {4,5,6} the arrow might mean containment and so on. But here's a remarkable fact: you can often take a definition in one branch of mathematics and write it diagrammatically. You can then reinterpret that diagram in a different branch of mathematics as different definition. Sometimes the new definition isn't interesting, but often it is. So now you can define things in multiple branches of mathematics at the same time. It gets better. Statements of theorem can also sometimes be written in purely diagrammatic language so a theorem that holds in one branch of mathematics turns out to be an interesting theorem in another. Sometimes the entire proof can be written diagrammatically meaning you can solve problems in different branches of mathematics at the same time. This whole 'multidisciplinary' subject is known as Category Theory. To a good approximation (and there is a certain amount of choice over which approximation you pick) Haskell also forms a category. The objects are types and the arrows are functions. But as I've also hinted above, objects can represent propositions and arrows can represent implication. So that suggests theorems about logic might carry over to theorems about Haskell. They do, as has been mentioned in another thread. But that's a special case of a much wider phenomenon where constructions in different parts of mathematics can feed into Haskell. So knowing category theory can help you to bring to bear mathematical knowledge from other fields when writing Haskell code. A big example of that payoff has been the notion of a monad. But there are many more. It also works the other way too. As you acquire a grasp of Haskell you get insight into other parts of mathematics and computer science, even if you don't yet know it! Haskell has certainly helped me this way. (And I should confess that this is one of my primary motivations for learning it.) -- Dan

3 2

RE: [Haskell-cafe] Looking for final year project - using Haskell, or another functional language
by Re, Joseph (IT) 13 Jul '07

13 Jul '07

If you meant just non-graphic uses of a gpu, I don't know much in that area, but I do know of a very neat graphics related (but irregular on standard gpus) topic; ray tracing. First off, a basic idea of what ray tracing is: http://en.wikipedia.org/wiki/Ray_tracing Second, for great reasons why ray tracing is useful and probably neccessary for the future, Dr. Kavita Bala gave a talk in 2005 (abstract: http://www.acm.uiuc.edu/conference/2005/speakers.php#KavitaBalaAbstract video: http://www.acm.uiuc.edu/conference/2005/video/UIUC-ACM-RP05-Kavita-Bala. wmv). I don't recall if she explicitly says it, but applying her "feature" emphasis approach to procedurally generated textures (which should scale in resolution perfectly) would be a way for a modern engine to really shine. During the same conference Dr. Peter Shirley gave the talk "Real Time Ray Tracing on the Desktop: When and How?" (abtract: http://www.acm.uiuc.edu/conference/2005/speakers.php#PeteShirleyAbstract video: http://www.acm.uiuc.edu/conference/2005/video/UIUC-ACM-RP05-Peter-Shirle y.wmv) Shirley decides in that video that a hardware based solution is what he should shoot for, and his group joins the Saarland University Graphics Group. [Note: if you are willing to watch both of these I recommend watching Dr. Shirley's first. Also, note that some videos have delayed starts.] Shortly thereafter, their groups make a number of advancements in ray tracing, and they created a working RPU (http://graphics.cs.uni-sb.de/SaarCOR/) on a FPGA board that is capable of rendering basic scenes in realtime as well as come out with a software solution that does roughly the same called OpenRT (http://www.openrt.de/) Both implementations scale accross multiple processors very well due to inherent parallelism in ray tracing. My guess is that a realtime engine (and a good game) using software ray tracing will help it gain popularity, but then dedicated boards made from the FPGA designs will take over shortly thereafter ("High end graphics cards from NVIDIA provide 23 times more programmable floating point performance and 100 times more memory bandwidth as our prototype"). Concurrently there has also been work of doing ray tracing on existing GPUs. Here's a neat paper from someone at my university, on structures for using a gpu for ray tracing, "Fast GPU Ray Tracing of Dynamic Meshes using Geometry Images" (http://graphics.cs.uiuc.edu/geomrt/geomrt2006.pdf) I'm unaware if he applies any of the breakthrough techniques learned from OpenRT's research (since it's very recent), but if not, that would certainly be a viable topic to explore within the realm of GPGPU-ish work. Getting a really performance optimized haskell implementation of OpenRT or bindings to an existing library (http://liris.cnrs.fr/~bsegovia/yacort/ or http://xfrt.sourceforge.net/) would be very cool, especially when combined with a shader dsl, a procedural generation library+dsl, overall graphics engine, and *dreams on*. At that point, someone could easily write the world's most beautiful nethack with little artistic skill. ----------------- Non-graphics related GPGPU uses: ATI's Stream Computing: http://ati.amd.com/technology/streamcomputing/index.html NVIDIA's CUDA: http://developer.nvidia.com/object/cuda.html Both of these allow you to code in "the standard C language" and "low level assembly language layer and driver interface". A number of open source GPGPU libraries (BrookGPU http://graphics.stanford.edu/projects/brookgpu/index.html and Sh http://libsh.org/) shoot for "C++". One would think that given how well programming GPUs lends itself to a functional language, clearly, they must be appealing to the lowest common denominator, but their language for the "hardcore" is some god awful assembly language... [defense] I get that they're performance nuts, but when's the last time you wrote a large and meaningful application in assembly (not a single inlined assembly function) by hand, that beat using your compiler (it terms of developer+system execute time)? If you can answer, my guess is either you're working on a compiler, or yours is broken. [/defense] Writing a real language for general progamming on GPUs would be pretty cool, although you'd have to then think of something to do with it as otherwise it might be a short project (rough guess considering the existing work in the area). Did either of these help? -- Joseph Re ________________________________ From: wp [mailto:walter1003@gmail.com] Sent: Thursday, July 12, 2007 6:41 PM To: Re, Joseph (IT) Subject: Re: [Haskell-cafe] Looking for final year project - using Haskell,or another functional language Hi Joseph, no, I don't mind if you cc the list. I just skimmed the two papers on Vertigo and Renaissance. Very interesting ... and not just that. I have been following in the last months/years the advances of GPGPU. Surely a lot of people think this is nothing of practical usage, especially if it comes to serious mathematical computation, or is there already a GPU which supports double float by now? ... Something in this direction would surely be nice ... Can you point to some more papers like those? Thanks walter. On 7/12/07, Re, Joseph (IT) < Joseph.Re(a)morganstanley.com <mailto:Joseph.Re@morganstanley.com> > wrote: No problem. I have a strong interest in the non-graphics portions of game engines and simulations, but as good visual representations are a critical part of expressing those parts, I prefer keeping my exposure to the graphics systems as painless as possible. Therefore, while I'm by no means an expert, I occasionally think/read papers about a graphics engine "done right" and other lib/tools I only see as a means to an end (and thus not something I plan on tackling myself) just so I'm ready when people like you come along. ;) I tried to cover a wide range of different areas to get something that strikes your fancy, but if you're especially interested in any specific area, I can provide additional help (mostly in terms of papers to check out, but a few original ideas as well). [I prefer CCing the list if that's alright with you, because I'm limited to certain a mailbox during weekdays and another during nights/weekends] ________________________________ From: wp [mailto:walter1003@gmail.com] Sent: Thursday, July 12, 2007 4:11 PM To: Re, Joseph (IT) Subject: Re: [Haskell-cafe] Looking for final year project - using Haskell,or another functional language Hi Joseph, this is an impressive summary of ideas! By far the best someone sent me so far. Thank you very much for this. At this point I really don't mind about the formatting:) So, as I like programming, but it's still the case that I am a beginner in Haskell some of the ideas might be quite advanced for me; further, I never really did graphics programming, but I would for sure learn a lot doing something in this direction. Another company suggested a similar idea to yours, building a DSL for textures and model generation ... DSL seems anyway a hot topic at the moment (or is it a revival?). I am working with q/kdb+ and am particularly interested in seeing that Credit Suisse is currently building a DSL embedded in Haskell .... hopefully some more of these languages will follow soon:) IT people would certainly have more fun doing their job, avoiding long debugging session:) Again, thank you very much for your effort! walter ________________________________ NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error. -------------------------------------------------------- NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error.

1 0

Multiple instancing of functions with FFI
by Lewis-Sandy, Darrell 13 Jul '07

13 Jul '07

I am having trouble exporting multiple instances of a polymorphic function similar to the example in the "Haskell 98 Foreign Function Interface 1.0 addendum" (page 6). My specific code is below: -----------------------begin test.hs--------------------------------- >module Test() where >import Foreign >import Foreign.C >foreign export stdcall "addByte" (+):: Int8->Int8->Int8 >foreign export stdcall "addInt" (+):: Int16->Int16->Int16 >foreign export stdcall "addLong" (+):: Int32->Int32->Int32 -----------------------end test.hs--------------------------------- This somewhat contrived example should export three foreign implementations of integer addition (one for each of 8, 16 and 32 byte integers). I am compiling to a Win 32 DLL with GHC 6.61 using the following set of commands: -------------------------------------------------------- ghc -c adder.hs -fglasgow-exts -ffi ghc -c dllMain.c ghc -static --mk-dll -optdll--def=test.def -o test.dll test.o test_stub.o dllMain.o -------------------------------------------------------- where dllMain.c declares my entry point for the DLL, and is as follows --------------------begin dllMain.c------------------------------------ #include <windows.h> #include <Rts.h> extern void __stginit_Adder(void); static char* args[] = { "ghcDll", NULL }; BOOL STDCALL DllMain ( HANDLE hModule, DWORD reason, void* reserved ) { if (reason == DLL_PROCESS_ATTACH) { startupHaskell(1, args, __stginit_Adder); return TRUE; } if (reason == DLL_PROCESS_DETACH) { shutdownHaskell(); return TRUE; } return TRUE; } ----------------------------end dllMain.c---------------------------- and I have declared the exported function names explicitly in test.def: ---------------------------begin test.def----------------------------- EXPORTS addByte addInt addLong ----------------------------end test.def---------------------------- Upon compilation, I receive a long list of errors including things like "error:redefinition of 'stginit_export_Test_zdfzp' was here", etc. Any help would be appreciated. Darrell

2 1

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