- Haskell-Cafe - Haskell.org

better error expression in IO function
by brad clawsie 14 Jul '07

14 Jul '07

i am working on improving a module for getting Yahoo Finance quote data, hopefully getting it to a point that i can put it on hackage in the quote retrieval function, there are a few places i would like to call out errors. in a trivial case i could return IO (Maybe String) with Nothing signifying any error state, or Just expressing the data but i would like to be able to express some of these error cases in a more structured manner i know the Either type can be used in such a case(?), but i've had some problem locating a satisfactory example (if this is indeed appropriate) could one of the vets here provide a simplistic example expressing error cases, preferrably in the IO Monad (in case there are any gotchas there)? thanks so much! brad

8 10

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

14 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 14 Jul '07

14 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 14 Jul '07

14 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 14 Jul '07

14 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 14 Jul '07

14 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 14 Jul '07

14 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

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 13 Jul '07

13 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 13 Jul '07

13 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 13 Jul '07

13 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 13 Jul '07

13 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 13 Jul '07

13 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 13 Jul '07

13 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 13 Jul '07

13 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

Lambdabot web interface
by Janis Voigtlaender 12 Jul '07

12 Jul '07

Hi, I can't get http://lambdabot.codersbase.com/ to work for me. Whatever input => "No lambdabot process" Is that a known issue, not the right URL, ...? Thanks, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

3 4

Monadic tunnelling: the art of threading one monad through another
by Jules Bean 12 Jul '07

12 Jul '07

A programming style which is encouraged in haskell is to write your program using a special monad, rather than the IO monad. Normally some mixture of reader and state, possibly writer, the point of these monads is to help the type system to help you; help you be specific about which parts of your state can be modified by which parts of your program. One problem with this approach comes with what an imperative programmer would call 'callbacks'. It's quite common with C library interfaces to take as a parameter an IO action (a callback) which the library will call with certain parameters. It's even more common with haskell libraries, although the type then is normally more general than IO; any higher order function can be thought of as using callbacks. Now, supposing we have a library function which takes a callback. As an example, suppose we have a library function which reads in a file and calls our callback once on each line. A typical type might look like: forEachLine :: Handle -> (String -> IO ()) -> IO () We have to provide a callback in the IO monad. But what if we don't want to work in the IO monad? What if we are working in, for example, a custom state monad of our own? More generally, is there any sensible way to pass callbacks in one monad, to an action which runs in a different monad? What does it mean to want to do this? In general the 'outer' action can call the callback as many times as it once, something like this (monospace font needed!): m: <- cb -> <- cb -> | | | | n: -- outer ---> <-- outer --> <-- outer --- Now, to embed 'm' into 'n' in this way, we have to somehow 'freeze' the 'monadiness' (you may prefer to use the term 'the warmth and fuzziness') of m at the beginning, run the first callback in this correct environment, then 'freeze' it again just after the callback runs, and restore this for the second 'cb'. Finally we have to somehow ensure this 'monadiness' is returned to the caller. This procedure is not possible for every pair of Monads m and n. They need to have special properties. It is however possible (for example) when 'n' is IO, and when 'm' is one of several common custom monads, as I will now show. Boring imports give a clue as to which monads I'm going to attempt. > {-# OPTIONS -fglasgow-exts #-} Although I have -fglasgow-exts on here, it's actually only necessary for the MPTC tricks towards the end of the exposition. The initial discussion is haskell 98 as far as I know. > > import Control.Monad.State > import Control.Monad.Reader > import Control.Monad.Writer > import Control.Monad.Error > import Control.Exception > > import Data.Typeable > > import Data.IORef We begin with a callback which is not in the IO monad, but in StateT Int IO (). StateT monads are very common in real programs (or hand-rolled equivalents). The simple callback just prints a message so we know it has happened, and increments the counter in the state so we can prove state is being correctly threaded. > -- example small action in the custom monad > stateioact :: StateT Int IO () > stateioact = do > x <- get > liftIO $ putStrLn ("stateioact called, with state as "++ > show x) > put (x+1) > The main action is just a boostrap to call a 'real' main action with some initial state: > -- Main action has type IO () as standard > -- This example main action just defers to another action > -- which is written in a custom monad > > main :: IO () > main = do > putStrLn "main starting" > evalStateT mainAction 42 > putStrLn "main exiting" > The real main action is a StateT Int IO () action. It calls stateioact once, then calls a "library function" which is known to use callbacks, then it calls stateioact again. > -- mainAction is written in the custom monad > mainAction :: StateT Int IO () > mainAction = do stateioact > embedIO $ \x -> usesCB (makeCallback stateioact x) > stateioact > The library function is "usesCB". makeCallback and embedIO are the keys which make it all work. Here is the library function. Note that it has plain type IO () -> IO (), just like any library function (e.g. a C FFI function) which takes a single callback. It prints diagnostic messages and takes care to call its callback twice, to demonstrate the monad-threading. > -- a 'library function' in the IO monad, which has a callback as one > -- of its parameters. The library function has no knowledge of the > -- custom monad being used by the main action here > usesCB :: IO () -> IO () > usesCB f = do putStrLn "usesCB starting" > f > putStrLn "usesCB middle" > f > putStrLn "usesCB exiting" > The 'threading' of the monad internals is handled by the dual functions, embedIO and makeCallback. embedIO turns an IO action (usesCB in the example above) and makes it into a StateT action. In that sense, it is doing the same job as 'liftIO'. However, it also encapsulates the internals of the StateT monad into a package, from where they can be retrieved by the callback later: > -- the glue which makes it work: > embedIO :: (IORef s -> IO a) -> StateT s IO a > embedIO a = do s <- get > x <- liftIO $ newIORef s > r <- liftIO $ a x > s' <- liftIO $ readIORef x > put s' > return r > (You can infer a much more general type for embedIO, but it's not more useful in most cases.) In fact what embedIO does, in this particular case, is store the state of the StateT monad in an IORef. Then makeCallback arranges for that to be accessible to the callbacks: > makeCallback :: StateT s IO a -> IORef s -> IO a > makeCallback act x = do s <- readIORef x > (res,s') <- runStateT act s > writeIORef x s' > return res > So, in the critical call embedIO $ \x -> usesCB (makeCallback stateioact x) the 'trick' is that embed IO makes a new IORef to store the state, populates it with the current state, binds it to that \x, and makeCallback takes the IORef and forms a new IO callback 'around' stateioact which contains the plumbing to read from, and write to, that IORef. Or in other words, we use the IO monad's ability to store unlimited state, stealing away a little private (lexically bound) portion for the use of our callback. And, if you're skeptical, it does work: *Main> main main starting stateioact called, with state as 42 usesCB starting stateioact called, with state as 43 usesCB middle stateioact called, with state as 44 usesCB exiting stateioact called, with state as 45 main exiting Just to refresh what we have done. We have managed to arrange that a totally normal IO action taking an IO callback, usesCB :: IO () -> IO (), can be run instead with a callback in a custom monad without modification. We can do an exactly similar operation on several other common monad transformers. In order to highlight the uniformity in the approaches, we leave haskell 98 and create a multi-parameter type class: > class InterleavableIO m a | m -> a where > embed :: (a -> IO b) -> m b > callback :: m b -> a -> IO b > A monad 'm' is 'Interleavable' over IO if there is some type 'a' which represents the monad's internals sufficiently that you can write 'embed' which strips the internals from the monad and feeds them to the callbacks, and 'callback' which given an action in m and the internals in an 'a', makes a pure IO callback. Here is our state instance, and two more rather similar instances: > class InterleavableIO m a | m -> a where > embed :: (a -> IO b) -> m b > callback :: m b -> a -> IO b > > instance InterleavableIO (StateT s IO) (IORef s) where > embed = embedIO > callback = makeCallback > > instance InterleavableIO (ReaderT r IO) r where > embed a = do s <- ask > liftIO $ a s > callback act s = runReaderT act s > > instance Monoid w => InterleavableIO (WriterT w IO) (IORef w) where > embed a = do x <- liftIO $ newIORef mempty > r <- liftIO $ a x > w <- liftIO $ readIORef x > tell w > return r > callback a x = do (r,w) <- runWriterT a > modifyIORef x (mappend w) > return r > The Writer instance is really very similar to the state one. Writer is like a state monad with 'write-only' state. (Append-only state, to be precise). The Reader instance is extremely simple; it really just is a funny way of writing partial application, after all. It is interesting to note, at least, that the Reader instance doesn't need IORefs, so IORefs aren't the only possibility for 'internals'. I didn't think the Reader instance was interesting enough to demonstrate, but here's a demo of the Writer instance, proving that the writing all happens in the correct order: > writeact :: WriterT [String] IO () > writeact = do liftIO $ putStrLn "writeact called!" > tell ["writeact"] > > wtest :: WriterT [String] IO () > wtest = do liftIO $ putStrLn "Testing WriterT callbacks" > tell ["start"] > embed $ \x -> usesCB (callback writeact x) > tell ["end"] > liftIO $ putStrLn $ "Finished" > A simple writer action which logs something and prints a debugging message, and a test action which calls our old friend 'usesCB' now with a WriterT callback. The output: *Main> runWriterT wtest Testing WriterT callbacks usesCB starting writeact called! usesCB middle writeact called! usesCB exiting Finished ((),["start","writeact","writeact","end"]) So. we've demonstrated interleaving for StateT IO, ReaderT IO and WriterT IO. What else can we do? Sometimes your callback is actually pure: it doesn't do any IO at all. In these cases, it's nice to have the type system 'know' it's pure. Fortunately this is easy to patch in to our existing system, since you can promote any pure State, Reader, Writer action into xyzT IO. In fact you can do something slightly more general: > promoteState :: MonadState s m => State s a -> m a > promoteState act = do s <- get > let (r,s') = runState act s > put s' > return r > > promoteReader :: MonadReader s m => Reader s a -> m a > promoteReader act = do s <- ask > return (runReader act s) > > promoteWriter :: MonadWriter w m => Writer w a -> m a > promoteWriter act = do let (r,w) = runWriter act > tell w > return r > Then, given a pure state action: > stateact :: State Int () > stateact = do x <- get > put (x*2) and a slight specialisation of the promoteState function, to help type inference along: > promoteState' :: State s a -> StateT s IO a > promoteState' = promoteState we can use a totally pure callback in our same usesCB: > purestatedemo :: StateT Int IO () > purestatedemo = do > liftIO $ putStrLn "Pure state demo" > liftIO . putStrLn . ("state is " ++) . show =<< get > embed $ \x -> usesCB (callback (promoteState' stateact) x) > liftIO . putStrLn . ("state is " ++) . show =<< get and run it like this: *Main> runStateT purestatedemo 1 Pure state demo state is 1 usesCB starting usesCB middle usesCB exiting state is 4 ((),4) I haven't yet experimented with the type class inference needed to get a correct 'embed' instance for a tower of compatible monad transformers, but I don't think that would be all that tricky. There is one more instance, though, which is a little different. The three we have seen so far are all rather similar, in that one way or another they're all really a kind of state. Here is a rather different instance: > data InterleaveErrorTException e = InterleaveErrorTException e > deriving (Typeable) > > instance (Error e, Typeable e) => > InterleavableIO (ErrorT e IO) () where > embed act = do > x <- liftIO $ catchDyn (Right `fmap` act ()) > (\(InterleaveErrorTException e) -> return (Left e)) > case x of Right r -> return r > Left e -> throwError e > callback a () = do > x <- runErrorT a > case x of Right r -> return r > Left e -> throwDyn > (InterleaveErrorTException e) Here the trick is to convert between the 'ErrorT' way of signalling error conditions, with a Left-value, and the IO way of signalling them using exceptions. This enables our actions to have custom error handling and still interoperate with IO's exception throwing: > failer :: ErrorT String IO () > failer = do liftIO $ putStrLn "failer called" > throwError "failer" > liftIO $ putStrLn "failer exiting" > > succeeder :: ErrorT String IO () > succeeder = do liftIO $ putStrLn "succeeder called" > liftIO $ putStrLn "succeeder exiting" > > errtest :: ErrorT String IO () > errtest = do liftIO $ putStrLn "errtest starting" > embed $ \x -> usesCB (callback failer x) > liftIO $ putStrLn "errtest ending" > > errtest2 :: ErrorT String IO () > errtest2 = do liftIO $ putStrLn "errtest starting" > embed $ \x -> usesCB (callback succeeder x) > liftIO $ putStrLn "errtest ending" > *Main> runErrorT errtest errtest starting usesCB starting failer called Left "failer" *Main> runErrorT errtest2 errtest starting usesCB starting succeeder called succeeder exiting usesCB middle succeeder called succeeder exiting usesCB exiting errtest ending Right () Note how the first test successfully 'short-circuits' out of the IO action. One important thing to note about this kind of threading is that it doesn't attempt to solve the asynchrony problem. It is explicitly for callbacks which are used synchronously (in the sense that they are never called after the main library routine 'returns') so they couldn't be used, as is, for event handlers; also they must be used single-threadedly; two parallel StateT callbacks would fight over the IORef. This last point is actually very easy to solve, however! We can just replace the IORef with the obvious MVar operations, and we immediately get 'intelligently parallelisable' callbacks: the callbacks would serialise w.r.t. each other, using takeMVar, but would not otherwise restrict the multi-threaded behaviour of the enclosing action. It's a little harder, but not impossible, to extend this so that event callbacks, which are called long after the initial action completes, can also access state safely; you need a "MVar-aware" state monad at the outermost level, but that's easy to write in a way which complies with MonadState and thus doesn't require global code changes. Of course, this probably extends outside library callbacks. There's not currently any way for a StateT action to safely 'forkIO': or, rather, of course there is, but the subsidiary thread is not an equal citizen. The subsidiary thread is 'merely' an IO action instead of a StateT s IO action, but these ideas suggest a resolution to that. This email has turned out about five times as long as I intended, so I'm going to stop there, although there are still things I wanted to bring up that I haven't got around to. I hope some people out there recognise the problem I'm trying to address, and I'm interested in all comments or corrections. Jules

3 6

haskell -> db, on Solaris
by Daniil Elovkov 12 Jul '07

12 Jul '07

Hello fokls Would you please tell me, what would be my choice if I wanted to interact with MySql and Oracle from a Haskell program on Solaris? Thank you

3 5

embedding Haskell: problematic polymorphism
by Claude Heiland-Allen 12 Jul '07

12 Jul '07

Hi people, I'm embedding Haskell into a C program with a "stateful objects with message passing" paradigm [0]. I want to make "boxes" with useful functions, then connect them together within the C program. I know how to build a working version using Data.Dynamic, but that loses polymorphism [1]. Say I have 3 boxes: Box 1: [1,2,5,3] :: [Float] Box 2: reverse :: [a] -> [a] Box 3: putStrLn . show :: (Show b) => b -> IO () I wonder, is it possible to create these boxes separately at runtime (each box being compiled/loaded separately with hsplugins), then connect them together like {Box 1}=>{Box 2}=>{Box 3} (with a wrapping layer doing appropriate type checking/error reporting), or does the whole thing need to be compiled statically to generate specialized variants of the polymorphic functions? As hinted in #haskell : <quicksilver> ClaudiusMaximus: I don't think anything will allow you to pass around polymorphic values. They're an illusion of the type-checker, in a sense. Thanks for any insights, Claude [0] http://puredata.info [1] Data.Dynamic> (fromDynamic (toDyn (3.5::Double)))::(Typeable a => Maybe a) <interactive>:1:0: Ambiguous type variable `a' in the constraint: `Typeable a' arising from instantiating a type signature at <interactive>:1:0-59 Probable fix: add a type signature that fixes these type variable(s) -- http://claudiusmaximus.goto10.org

3 2

Constraints on data-types, mis-feature?
by Daniil Elovkov 12 Jul '07

12 Jul '07

Hello In the archives of haskell-cafe I found a mention of constraints on datatypes as a mis-feature of Haskell. In particular, that they're not propagated well. Can someone elaborate on that? Also, are they still considered a mis-feature with the emergence of GADTs ? If I have data GADT a where ... Alt :: (a -> b -> c) -> GADT a -> GADT b -> GADT c ... and I want to constrain all a, b, c. Would it be better to expose all of them as type vars, rather than constrain in-place? It would lead to a rather verbose code.

3 4

CPS versus Pattern Matching performance
by Tony Morris 12 Jul '07

12 Jul '07

Is there a performance penalty to be paid when using CPS instead of pattern matching? CPS often "feels more concise" but I suspect that it incurs a cost because of the accumulating stack that pattern matching wouldn't. When you you use maybe :: b -> (a -> b) -> Maybe a -> b instead of pattern matching a returned Maybe value? Is there something a bit more concrete on this issue? -- Tony Morris http://tmorris.net/

9 14

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

12 Jul '07

Tim Chevalier wrote: > On 7/10/07, Andrew Coppin <andrewcoppin(a)btinternet.com> wrote: >> On the one hand, it feels exciting to be around a programming language >> where there are deep theoretical discoveries and new design territories >> to be explored. (Compared to Haskell, the whole C / C++ / Java / >> JavaScript / Delphi / VisualBasic / Perl / Python thing seems so >> boring.) >> >> On the other hand... WHAT THE HECK DOES ALL THAT TEXT *MEAN*?! >_< >> > > If you're interested in a concept, why not read about it (it's easy to > find a quick definition for most terms on Google, and more details in > research papers), then ask *specific* questions on the list? Posting > to the list about how you don't understand something, without any > suggestion as to how anyone else could help, doesn't accomplish a lot. I wasn't being entirely serious. ;-) We've got a whole other thread going about trying to understand the difference between existential and universal quantification. Suffice it to say I'm still confused. I guess this is going to be one of those concepts I'll just never understand.

1 0

Re: [Haskell-cafe] function unique
by Gregory Propf 12 Jul '07

12 Jul '07

Yeah, I didn't see that part of the email, sorry. ----- Original Message ---- From: Alexteslin <alexteslin(a)yahoo.co.uk> To: haskell-cafe(a)haskell.org Sent: Wednesday, July 11, 2007 8:59:33 AM Subject: Re: [Haskell-cafe] function unique Thans Gregory, But I sticked to the original solution because the exercise was about primitive recursion and pattern matching over lists. ____________________________________________________________________________________ Never miss an email again! Yahoo! Toolbar alerts you the instant new Mail arrives. http://tools.search.yahoo.com/toolbar/features/mail/

1 0

Re: [Haskell-cafe] function unique
by Gregory Propf 11 Jul '07

11 Jul '07

Well there's this approach. Granted you need to split the input list into *both* args of the fold (i.e. the "input list" is really [1,4,5,3] but you can get this with head and tail). I'm just learning about the fold family myself. - Greg Prelude> foldl (\a b -> if (any (\x -> x == b) a) then a else b:a) [1] [4,5,3,3,4] [3,5,4,1] ----- Original Message ---- From: Alexteslin <alexteslin(a)yahoo.co.uk> To: haskell-cafe(a)haskell.org Sent: Tuesday, July 10, 2007 1:40:56 PM Subject: [Haskell-cafe] function unique 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ____________________________________________________________________________________ Shape Yahoo! in your own image. Join our Network Research Panel today! http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7

2 1

Haddock and link href locations?
by Marc Weber 11 Jul '07

11 Jul '07

I want to add some haddock support to nix So that you can also install package-haddock-version But I'm struggling. I can tell nix to but all html files into $out/<shared-dir> However this will lead to collisions. Either if a package ships with a dependency itself or if you install different versions. The latter is not a big problem. You can assign priorities to choose the version which will be linked to you nix-profile directory. You'll be using the latest documentation any most of the time, won't you? Is there an easy way to tell haddock to use absolute paths? DepA/interface-dump DepA/*.html DebB/interface-dump DepB/*.html Now I want to create some documentation for C referencing DepA and DepB in DepC/*.html DebC/interface-dump Cat this be done? By now the created files will reference the html file with a relative path. Thus they won't be found unless I put everything into one shared directory (which I'll do for now) Marc

1 0

increase in spam on the wiki
by dons＠cse.unsw.edu.au 11 Jul '07

11 Jul '07

Looks like the spam protection measures are breaking down a bit. There's been 4 spam incidents (at least) on the wiki in the past day. Ashley et al, is there any easy fix? -- Don

1 0

ANN: Network.HTTP.Simple 0.1 in hackage
by brad clawsie 11 Jul '07

11 Jul '07

i have mentioned my small Network.HTTP.Simple wrapper library here before i have made api changes and i have released it to hackage these changes are described here http://www.b7j0c.org/content/haskell-http.html this page oddly gets many non-bot hits a day, so i presume there is sufficient interest to merit major changes here on the list i have made every attempt to correctly attribute work i borrowed from the Network.HTTP authors, to whom i am grateful

1 0

Re: [Haskell-cafe] function unique
by Gregory Propf 11 Jul '07

11 Jul '07

There was a typo in my last email. The input list is [1,4,5,3,3,4] not [1,4,5,3]. - Greg ----- Original Message ---- From: Alexteslin <alexteslin(a)yahoo.co.uk> To: haskell-cafe(a)haskell.org Sent: Tuesday, July 10, 2007 1:40:56 PM Subject: [Haskell-cafe] function unique 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ____________________________________________________________________________________ It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/

1 0

Allocating enormous amounts of memory and wondering why
by Jefferson Heard 11 Jul '07

11 Jul '07

I'm using the Data.AltBinary package to read in a list of 4.8 million floats and 1.6 million ints. Doing so caused the memory footprint to blow up to more than 2gb, which on my laptop simply causes the program to crash. I can do it on my workstation, but I'd really rather not, because I want my program to be fairly portable. The file that I wrote out in packing the data structure was only 28MB, so I assume I'm just using the wrong data structure, or I'm using full laziness somewhere I shouldn't be. I've tried compiling with profiling enabled, but I wasn't able to, because the Streams package doesn't seem to have an option for compiling with profiling. I'm also a newbie to Cabal, so I'm probably just missing something. The fundamental question, though is "Is there something wrong with how I wrote the following function?" binaryLoadDocumentCoordinates :: String -> IO (Ptr CFloat, [Int]) binaryLoadDocumentCoordinates path = do pointsH <- openBinaryFile (path ++ "/Clusters.bin") ReadMode coordinates <- get pointsH :: IO [Float] galaxies <- get pointsH :: IO [Int] coordinatesArr <- mallocArray (length coordinates) pokeArray coordinatesArr (map (fromRational . toRational) coordinates) return (coordinatesArr, galaxies) I suppose in a pinch I could write a C function that serializes the data, but I'd really rather not. What I'm trying to do is load a bunch of coordinates into a vertex array for OpenGL. I did this for a small 30,000 item vertex array, but I need to be able to handle several million vertices in the end. If I serialize an unboxed array instead of a list or if I do repeated "put_" and "get" calls, will that help with the memory problem?

4 6

GHC threads and SMP
by Paul L 11 Jul '07

11 Jul '07

I have two parallel algorithms that use the lightweight GHC thread and forkIO. I compile them using the -threaded (or -smp) option, and run both with +RTS -N2 -RTS command line option. QSort is able to make use of the dual cores on my laptop -- "top" shows that two threads show up and both CPUs are utilized, and "time" it will give something like this: real 0m0.502s user 0m0.872s sys 0m0.004s But Prime can only make use of one core, as shown by "top". "time" gives real 0m9.112s user 0m9.093s sys 0m0.028s Because forkOS is not used anywhere, the decision of running them on 1 or 2 OS threads seem rather arbitary. Why? Regards, Paul L > import Control.Concurrent > import System.Random > import Data.Array.MArray > import Data.Array.IO > import System.IO.Unsafe > import Control.Exception 1. Quick Sort > testQSort' n verbose = do > let b = (0, n - 1) > arr <- newArray b 0 :: IO (IOUArray Int Int) > initM' (mkStdGen 0) b arr > waitForChildren > qsortM' b arr > waitForChildren > if verbose then getElems arr >>= putStrLn . show else return () Initialize an array with random numbers. > initM' g (i, j) arr | j - i < 10000 = fillArr g i j > where > fillArr g i j = if i > j then return () else do > let (v, g') = next g > writeArray arr i v >> fillArr g' (i + 1) j > initM' g (i, j) arr = do > let k = (i + j) `div` 2 > (g1, g2) = split g > forkChild $ initM' g1 (i, k) arr > forkChild $ initM' g2 (k + 1, j) arr > return () > qsortM' (i, j) arr = qsort' (i, j) > where > qsort' (i, j) = > if j <= i then return () else do > k <- split i j > if j - i > 10000 then (forkChild $ qsort' (i, k - 1)) >> return () > else qsort' (i, k - 1) > qsort' (k + 1, j) > split left right = do > v <- readArray arr right > let split' i j = if j == right then swap i right v >> return i else do > b <- readArray arr j > if b <= v > then (swap i j b) >> split' (i + 1) (j + 1) > else split' i (j + 1) > split' left left > swap i j b = do > a <- readArray arr i > writeArray arr i b > writeArray arr j a 2. Prime > testPrime' n verbose = do > arr <- newArray (0, n) True :: IO (IOUArray Int Bool) > primeM' arr n > waitForChildren > if verbose > then getElems arr >>= putStrLn . show . map fst . filter snd . zip [0..] > else return () > primeM' arr n = do > let p = truncate $ sqrt (fromIntegral n) + 1 > remove i = if i > p then return () else do > spawnRemover (i + 1) > remove' (i + i) > where > remove' j = if j > n then return () else do > writeArray arr j False > remove' (j + i) > spawnRemover j = if j > n then return () else do > t <- readArray arr j > if t then forkChild (remove j) else spawnRemover (j + 1) > remove 2 Manage thread termination > children :: MVar [MVar ()] > children = unsafePerformIO (newMVar []) > waitForChildren :: IO () > waitForChildren = do > cs <- takeMVar children > case cs of > [] -> putMVar children cs > m:ms -> do > putMVar children ms > takeMVar m > waitForChildren > > forkChild :: IO () -> IO () > forkChild io = do > mvar <- newEmptyMVar > childs <- takeMVar children > putMVar children (mvar:childs) > forkIO (io `finally` putMVar mvar ()) > return ()

3 4

Re: [Haskell-cafe] The Garbage Collector Ate My Homework
by Thomas Conway 11 Jul '07

11 Jul '07

Hmm, looks like the garbage collector got hungry again: 1093,741,664,672 bytes allocated in the heap 1006,759,632,160 bytes copied during GC (scavenged) 72,181,353,728 bytes copied during GC (not scavenged) 400,940,412 bytes maximum residency (8853 sample(s)) 76353 collections in generation 0 (3724.54s) 8853 collections in generation 1 (19689.00s) 1065 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 2619.54s (3103.46s elapsed) GC time 23413.54s (23569.24s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 2167.91s (2204.09s elapsed) EXIT time 0.00s ( 0.08s elapsed) Total time 28201.00s (28876.80s elapsed) %GC time 83.0% (81.6% elapsed) Alloc rate 417,531,666 bytes per MUT second Productivity 9.3% of total user, 9.1% of total elapsed And that was with -H700M. What a shame the heap profiler (-hb) aborts on my program. :-( Still, -hc and -hd seem to work, the only hassle is the hours of running time required to get things to go bad. cheers, T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

1 0

Sequence Classes
by Jonathan Cast 11 Jul '07

11 Jul '07

I was just meditating on array fusion using streams, and list fusion using streams, and it struck me: the definition of the list functions over arrays is the same as that of the list functions over lists. From the ByteString paper, we get: map f = transformerBi (mapS f) foldr f z = consumerDn (foldrS f z) foldl f z = consumerUp (foldlS f z) replicate n = producerBi (replicateS n) etc. So why not say class Sequence t alpha where consumerUp, consumerDn, consumerBi :: (Stream alpha -> beta) -> t alpha -> beta producerUp, producerDn, producerBi :: Stream alpha -> t alpha transformerUp, transformerDn, transformerBi :: Sequence t beta => (Stream alpha -> Stream beta) -> t alpha -> t beta map :: Sequence t alpha => (alpha -> beta) -> t alpha -> t beta map f = transformerBi (mapS f) etc.? Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs

2 1

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

11 Jul '07

On 7/10/07, Dan Piponi <dpiponi(a)gmail.com> wrote: > On 7/10/07, Andrew Coppin <andrewcoppin(a)btinternet.com> wrote: > > But what does, say, "Maybe x -> x" say? Silly me. You reversed the arrows and I copied you. (Could it be something to do with the other conversation we were having?) I meant to say: So x -> Maybe x says that X implies "True or X". That's a valid proposition and so there is a function x -> Maybe x. -- Dan

1 0

Re: [Haskell-cafe] In-place modification
by Andrew Coppin 11 Jul '07

11 Jul '07

Bulat Ziganshin wrote: > Hello Andrew, > > Monday, July 9, 2007, 12:36:25 AM, you wrote: > >> OK. So that's just the GHC binary itself, right? >> > > it's INSTALLER > Ah. That explains the size then... Is it safe to install two versions of GHC at once? :-.

3 6

ANNOUNCE: HCL v1.0 -High-level library for building command line interfaces
by Justin Bailey 11 Jul '07

11 Jul '07

I'm please to announce HCL 1.0 - a library for building command line interfaces. The library exports a mix of low and high-level functions for building programs which gather simple values, ask yes/no questions, or present hierarchical menus. The library is not intended to do complex, full-screen UIs ala ncurses - it is intended for line-oriented interfaces. Included with the library is a hangman game, so if nothing else you can enjoy that. Where do I get it? ============= Download from Hackage at: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HCL-1.0 How do I use it it? ============= It's Cabal-ized so, after downloading and unpacking: runghc Setup.hs configure runghc Setup.hs build runghc Setup.hs install Note I had some inconsistent results building with HEAD cabal, but the version distributed with GHC works great (1.1.6.2). To play hangman, execute 'hangman'. Once installed, you can look at it in GHCi by loading the "HCL" module. Tell me more! ========== This library lets you do a lot of cool things. For example, here's a simple guess a number game: guess_num_fun = do target <- reqIO $ getStdRandom (randomR (1::Integer,100)) let guessed val = case compare target val of GT -> do { reqIO $ putStrLn "Too low!"; return False } LT -> do { reqIO $ putStrLn "Too high!"; return False } EQ -> do { reqIO $ putStrLn "You win!"; return True } reqUntil guessed (prompt "Enter a number between 1 and 100: " reqInteger) "reqUntil" takes a predicate and asks for a response until the predicate is true. In the case above, the user is asked to enter an integer. Once they guess the number, the program ends. The library makes it easy to gather structured values. For example, imagine this data structure: data Taxpayer = Taxpayer { name :: String, age :: Int, ssn :: String } deriving (Read, Show) One way to use HCL to get Taxpayer values from the user is to take advantage of its Read instance: reqTaxpayer :: Request Taxpayer reqTaxpayer = prompt "Please enter tax payer information: " (reqRead reqResp) But that is ugly because the user has to type a "Read"-able string: > getTaxpayer reqTaxpayer Please enter tax payer information: Taxpayer {name="John", age = 30, ssn = "" } However, we can build a form of sorts and make life much easier for the user: reqTaxpayerEasy :: Request Taxpayer reqTaxpayerEasy = do name <- prompt "Please enter the tax payer's name: " reqResp age <- prompt "Please enter their age: " reqInt ssn <- prompt "What is their SSN/ASN: " reqResp return (Taxpayer name age ssn) Which looks like this: > getTaxpayer reqTaxpayerEasy Please enter the tax payer's name: Bob Please enter their age: 50 Please enter their SSN/ASN: 111-11-1111 The library also makes simple hierarchical menus easy to build. The below defines the menu structure for a hypothetical PIM: reqMenu $ reqSubMenu topMenu "Manage contacts" manageContactsMenu $ reqSubMenu topMenu "Manage calendar" (reqMenuItem "Add an event" ... $ ... reqMenuExit "Return to previous menu" reqMenuEnd) $ -- End the menu definition reqMenuEnd -- Defines a partial menu manageContactsMenu = reqMenuItem "Add a contact" ... $ ... reqMenuExit "Return to previous menu" reqMenuEnd These and more examples are distributed with the library in the examples directory. Anything else? =========== Feedback, praise and criticism are welcome. Feedback regarding 'idiomatic' usage is especially desired. This is a first for me so any responses are appreciated. The library was developed on Windows using GHC - please let me know of any odd *nix and Hugs bugs. This library was inspired in part by the Ruby HighLine library (http://highline.rubyforge.org/) Many thanks Mark Jones for his input on HCL's design and implementation.

4 5

Need for speed: the Burrows-Wheeler Transform
by Andrew Coppin 10 Jul '07

10 Jul '07

OK, so I *started* writing a request for help, but... well I answered my own question! See the bottom... I was reading Wikipedia, and I found this: http://en.wikipedia.org/wiki/Burrows-Wheeler_transform I decided to sit down and see what that looks like in Haskell. I came up with this: module BWT where import Data.List rotate1 :: [x] -> [x] rotate1 [] = [] rotate1 xs = last xs : init xs rotate :: [x] -> [[x]] rotate xs = take (length xs) (iterate rotate1 xs) bwt :: (Ord x) => [x] -> [x] bwt = map last . sort . rotate step :: (Ord x) => [x] -> [[x]] -> [[x]] step xs = zipWith (:) xs . sort inv_bwt :: (Ord x) => x -> [x] -> [x] inv_bwt mark xs = head . filter (\xs -> head xs == mark) . head . drop ((length xs) - 1) . iterate (step xs) . map (\x -> [x]) $ xs My my, isn't that SO much shorter? I love Haskell! :-D Unfortunately, the resident C++ expert fails to grasp the concept of "example code", and insists on comparing the efficiency of this program to the C one on the website. Fact is, he's translated the presented C into C++, and it can apparently transform a 145 KB file in 8 seconds using only 3 MB of RAM. The code above, however, took about 11 seconds to transform 4 KB of text, and that required about 60 MB of RAM. (I tried larger, but the OS killed the process for comsuming too much RAM.) Well anyway, the code was written for simplicity, not efficiency. I've tried to explain this, but apparently that is beyond his comprehension. So anyway, it looks like we have a race on. >:-D The first thing I did was the optimisation mentioned on Wikipedia: you don't *need* to build a list of lists. You can just throw pointers around. So I arrived at this: module BWT2 (bwt) where import Data.List rotate :: Int -> [x] -> Int -> [x] rotate l xs n = (drop (l-n) xs) ++ (take (l-n) xs) bwt xs = let l = length xs ys = rotate l xs in map (last . rotate l xs) $ sortBy (\n m -> compare (ys n) (ys m)) [0..(l-1)] This is indeed *much* faster. With this, I can transform 52 KB of text in 9 minutes + 60 MB RAM. The previous version seemed to have quadratic memory usage, whereas this one seems to be linear. 52 KB would have taken many months with the first version! Still, 9 minutes (for a file 3 times smaller) is nowhere near 8 seconds. So we must try harder... For my next trick, ByteStrings! (Never used them before BTW... this is my first try!) module BWT3 (bwt) where import Data.List import qualified Data.ByteString as Raw rotate :: Int -> Raw.ByteString -> Int -> Raw.ByteString rotate l xs n = (Raw.drop (l-n) xs) `Raw.append` (Raw.take (l-n) xs) bwt xs = let l = Raw.length xs ys = rotate l xs in Raw.pack $ map (Raw.last . rotate l xs) $ sortBy (\n m -> compare (ys n) (ys m)) [0..(l-1)] Now I can transform 52 KB in 54 seconds + 30 MB RAM. Still nowhere near C++, but a big improvement none the less. Woah... What the hell? I just switched to Data.ByteString.Lazy and WHAM! Vast speed increases... Jeepers, I can transform 52 KB so fast I can't even get to Task Manager fast enough to *check* the RAM usage! Blimey... OK, just tried the 145 KB test file that Mr C++ used. That took 2 seconds + 43 MB RAM. Ouch.

12 21

Haskell and GnuPG?
by Magnus Therning 10 Jul '07

10 Jul '07

Continuing my "life up-side-down"¹ I'm looking for a Haskell wrapper around GPGME. Is there such a beast? /M ¹) That's the life where I turn to Haskell before turning to Python. -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus

2 1

Data.ByteString.dropWhile
by Thomas Conway 10 Jul '07

10 Jul '07

Hi All, I notice that Data.ByteString has span and spanEnd. Is there a known particular reason why dropWhile and takeWhile don't have corresponding *End functions? If not, what is the protocol for adding them? cheers, T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

4 7

where's yi available?
by Vadim 10 Jul '07

10 Jul '07

I'm trying to get 'hide' but failed to install 'yi'. I followed instructions at page http://haskell.org/hawiki/hIDE_2fDesign but can't succeed in executing darcs get http://scannedinavian.org/repos/yi/ the mentioned http isn't responding. Can you please advise where can I get yi? TIA. Vadim.

2 1

Too many packages on hackage? :-)
by dons＠cse.unsw.edu.au 10 Jul '07

10 Jul '07

Hackage hackers, Looks like there's too many packages on hackage.haskell.org now for a single page listing: http://hackage.haskell.org/packages/archive/pkg-list.html Perhaps we can have a page with just the categories, with subpages hanging off? -- Don

11 14

Evaluation of IO actions in record assignment
by Adde 10 Jul '07

10 Jul '07

Hi. I'm toying around with GTK2Hs and one of the things I'm doing is stuffing a bunch of widgets in a record. The problem is that the function that fetches a widget from the Glade file returns IO Widget while my structure contains Widget's. The best I've come up with is simply evaluating the actions by putting the result in temporaries and then building the record. Is there an easier way to accomplish this? signatureEntry <- xmlGetWidget xml castToEntry "signatureEntry" passwordEntry <- xmlGetWidget xml castToEntry "passwordEntry" repeatEntry <- xmlGetWidget xml castToEntry "repeatEntry" return UserPanel {userPanelSignatureEntry = signatureEntry, userPanelPasswordEntry = passwordEntry, userPanelRepeatEntry = repeatEntry} Thanks, Adde

3 3

Testing parsing failures with Parsec
by Sean Smith 10 Jul '07

10 Jul '07

All - I tried emailing this to Daan, but I can't find an up-to-date email address, so I hope this is an acceptable alternative :). I'm looking for someone who knows the guts of Parsec a bit, or has done some automated testing of a Parsec parser. I'm interested in using Parsec for a number of projects, so I'm giving it a try. So far, it has really served me well. However, I've run into an issue with testing for proper parsing failures. As an example, I've been parsing a simplified version of scheme's s-expressions. When parsing "(1 2n3)", I expect a parse error "unexpected \"n\"". Therefore, I've made a test case which attempts to inspect the resulting ParseError to make sure it's correct. However, I'm confused by this list of Messages: [SysUnExpect "\"n\"",SysUnExpect "\"n\"",Expect "space",Expect "\")\""] Why is SysUnExpect "\"n\"" in the list twice? I can't figure that out from looking over the source for Parsec. It seems like the following rules should hold, but I can't be sure: 1) There should only be one occurrence of SysUnExpect *or* UnExpect in the list 2) UnExpect is only used for an unexpected reserved word or operator, and SysUnExpect is used for parse errors 3) There can be any number of Expect in the list, which indicate what was expected to occur in the stream If the above rules are correct, I was thinking it might make more sense to use a type with more structure than a list to hold those data. Also, the fact that neither Message nor ParseError derives Eq makes it difficult to test values of those types. Why not derive Eq? Finally, do you have any suggestions as to how I might better test for correct parse errors from Parsec? Thanks very much for your help! - Sean Smith P.S. I'm more than willing to dig into the Parsec source and provide patches for any changes I might make, if someone will accept them!

1 0

Haskell's prefix exprs
by Christian Maeder 10 Jul '07

10 Jul '07

Hi, I would like haskell to accept the following (currently illegal) expressions as syntactically valid prefix applications: f = id \ _ -> [] g = id let x = [] in x h = id case [] of [] -> [] i = id do [] j = id if True then [] else [] The rational is that expressions starting with a keyword should extend as far as possible (to the right and over several lines within their layout). In this case the above right hand sides (rhs) are unique juxtapositions of two expressions. (This extension should of course apply to more than two expressions, i. e. "f a do []") Furthermore the above rhs are all valid if written as infix expressions: f = id $ \ _ -> [] g = id $ let x = [] in x h = id $ case [] of [] -> [] i = id $ do [] j = id $ if True then [] else [] (In fact, maybe for haskell-prime "$" could be changed to a keyword.) Does this pose any problems that I haven't considered? I think only more (and shorter) illegal haskell programs will become legal. Cheers Christian Maybe someone else can work out the details for Haskell's grammar (I've posted this message to glasgow-haskell-users before, but it applies to every Haskell implementation and should be discussed here.)

3 2

Elementary question about Type Constraints
by lassoken 10 Jul '07

10 Jul '07

Hi, I'm trying to translate Example 2.3.3 (simple symbolic differentation) from Structure and Interpretation of Computer Programs into Haskell. Here is code that works (as far as see): --- data Term b = Var String | Const b | Sum (Term b) (Term b) | Prod (Term b) (Term b) newSum (Const a) (Const b) = Const (a+b) newSum (Const 0) t@_ = t newSum t@_ (Const 0) = t newSum a b = Sum a b newProd (Const a) (Const b) = Const (a*b) newProd (Const 1) t@_ = t newProd t@_ (Const 1) = t newProd (Const 0) t@_ = Const 0 newProd t@_ (Const 0) = Const 0 newProd a b = Prod a b deriv (Var x) (Const c) = Const 0 deriv (Var x) (Var y) | x == y = Const 1 | otherwise = Const 0 deriv x@(Var _) (Sum u v) = newSum (deriv x u) (deriv x v) deriv x@(Var _) (Prod u v) = newSum (newProd u (deriv x v)) (newProd (deriv x u) v) --instance Show (Term b) where show = showTerm showTerm (Var x) = x showTerm (Const c) = show c showTerm (Sum a b) = "(" ++ showTerm a ++ "+" ++ showTerm b ++ ")" showTerm (Prod a b) = "(" ++ showTerm a ++ showTerm b ++ ")" --- Where should I put type constraint (Show b) to be able to define Term b as an instance of Show class? Actually, I would like to say that Term b is an instance of Show iff b is and not to put constraint on b.

4 3

More binary IO, compression, bytestrings and FFI fun
by dons＠cse.unsw.edu.au 10 Jul '07

10 Jul '07

Processing larger amounts of data, compression, serialisation and calling C. An elaboration of the previous example: * Build a largish structure in Haskell * Compress it in memory * Serialise it to disk * Deserialise it * Decompress * Pass it to C * Display the result Pretty common pattern for low level stuff. We use zlib + lazy bytestrings for streaming decompression, and Data.Binary for the serialisation. We will use * Foreign.* to generate the data * Wrap it as a lazy bytestring * Data.Binary to serialise it * Code.Compression.Gzip to compress/uncompress * Pass it to C and make a simple FFI call on the result * Display the result Running: $ ghc -O2 A.hs --make $ time ./A Built table Compressed 25600000 bytes Compressed size 2231545 bytes (91.28%) Decompressed 25600000 bytes Calling into C ... -8.742278e-8 -0.6865875 -0.7207948 -0.1401903 0.63918984 0.7437966 0.27236375 -0.5763547 -0.75708854 -0.39026973 ./A 2.98s user 0.11s system 94% cpu 3.275 total The code: {-# OPTIONS -fglasgow-exts #-} -- -- Some imports -- import Foreign import Foreign.C.Types import Data.Int import qualified Data.ByteString.Lazy as L import qualified Data.ByteString.Base as S import qualified Data.ByteString as S import Data.Binary import Codec.Compression.GZip import System.IO import Text.Printf import Control.Monad ------------------------------------------------------------------------ -- Foreign Ptrs -- -- A simple wrapper type -- data Table = Table { floats :: ForeignPtr CFloat , ints :: ForeignPtr Int } -- Statically fixed sizes floatSize = 4800000 intSize = 1600000 totalBytes = sizeOf (undefined :: CFloat) * floatSize + sizeOf (undefined :: Int) * intSize -- -- Build a table populated with some defaults -- Float table filled with 'pi' , ints numbered consecutively -- newTable :: IO Table newTable = do fp <- S.mallocByteString (floatSize * sizeOf (undefined :: CFloat)) ip <- S.mallocByteString (intSize * sizeOf (undefined :: Int )) withForeignPtr fp $ \p -> forM_ [0..floatSize-1] $ \n -> pokeElemOff p n pi withForeignPtr ip $ \p -> forM_ [0..intSize-1] $ \n -> pokeElemOff p n n return (Table fp ip) ------------------------------------------------------------------------ -- Lazy ByteStrings -- -- Convert ForeignPtr a to and from a lazy ByteString -- toByteString :: Storable a => ForeignPtr a -> Int -> L.ByteString toByteString (fp :: ForeignPtr a) n = L.fromChunks . (:[]) $ S.fromForeignPtr (castForeignPtr fp) (n * sizeOf (undefined :: a)) -- -- Flatten a lazy bytestring back to a ForeignPtr. -- fromByteString :: Storable a => L.ByteString -> ForeignPtr a fromByteString lbs = castForeignPtr fp where (fp,_,n) = S.toForeignPtr . S.concat $ L.toChunks lbs ------------------------------------------------------------------------ -- GZip and Data.Binary -- -- Serialise a Table, compressing with gzip it as we go: -- instance Binary Table where put (Table f i) = do put . compress . toByteString f $ floatSize put . compress . toByteString i $ intSize get = do fs <- liftM decompress get is <- liftM decompress get -- check we read the correct amount: if L.length fs + L.length is == fromIntegral totalBytes then return $ Table (fromByteString fs) (fromByteString is) else error "Partial read" ------------------------------------------------------------------------ -- FFI -- -- Example call to process the data using C functions. -- rounded :: Int -> ForeignPtr CFloat -> IO [CFloat] rounded l fp = withForeignPtr fp $ \p -> go p where go p = forM [0..l-1] $ \n -> do v <- peekElemOff p n return $ c_tanhf (c_sinf (v + fromIntegral n)) -- A random C function to use: foreign import ccall unsafe "math.h sinf" c_sinf :: CFloat -> CFloat foreign import ccall unsafe "math.h tanhf" c_tanhf :: CFloat -> CFloat ------------------------------------------------------------------------ -- -- Now glue it all together -- main = do table <- newTable putStrLn "Built table" -- write the data to disk, compressed with gzip as we go. encodeFile "/tmp/table.gz" table printf "Compressed %d bytes\n" totalBytes -- how good was the compression? h <- openFile "/tmp/table.gz" ReadMode n <- hFileSize h hClose h printf "Compressed size %d bytes (%0.2f%%)\n" n (100 - (fromIntegral n/fromIntegral totalBytes*100) :: Double) -- load it back in, decompressing on the fly table' <- decodeFile "/tmp/table.gz" printf "Decompressed %d bytes\n" totalBytes -- now process the floats with C printf "Calling into C ...\n" ps <- rounded 10 (floats table') forM_ ps print

2 3