- Haskell-Cafe - Haskell.org

represent data sturcture using function
by Raeck chiu 30 Dec '08

30 Dec '08

Merry Christmas! Hope everybody is enjoying the Christmas! I am doing some readings and I found something seems to be interesting. People sometime will try to represent a quantity-regard-only data structure (such a order-regadless List) using functions instead of ta concrete data structure (like the haskell build-in []), any particular reason for this? For example, > data Sex = Male | Female > classA :: Sex -> Int > classA Male = 100 > classA Female = 200 when I should prefer the above solution instead of using a concrete data structure such as [] to represent the classA members? It seems to be very difficult to change the number of Male or Female if a concrete data structure is not used. Is it possible change the number of Male in classA when represent classA using function? Thank you very much! Best wishes, Raeck _________________________________________________________________ It’s the same Hotmail®. If by “same” you mean up to 70% faster. http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_…

5 6

Maintaining laziness
by Henning Thielemann 30 Dec '08

30 Dec '08

In case someone cares - after some battles with functions that are less lazy than expected, I have written a tutorial on how to get functions lazy and how to test, whether they are actually lazy: http://www.haskell.org/haskellwiki/Maintaining_laziness I found it especially enlightening, that one can avoid a 'force' function in a lazy parser by making the possibility of a parser failure explicit in its type. I.e. a parser that cannot fail, need no 'force'. (I learnt that in polyparse the 'force' function is hidden in 'apply': http://hackage.haskell.org/packages/archive/polyparse/1.1/doc/html/Text-Par… )

4 5

Data.List.sort, not so good?
by Adrian Neumann 29 Dec '08

29 Dec '08

Hello Haskell-Cafe, lately I've been playing around with sorting. I discovered that Data.List.sort is not as optimized I thought. At least not for random lists. I think we should consider adding a Data.List.Sort package to hackage (Similar to Data.List.Split) that offers a wide variety of sorting algorithms. I don't consider myself to be a very advanced Haskell programmer, but I could come up with a Mergesort that beats List.sort, time- and spacewise. > http://hpaste.org/13403 On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled with -O2). List.sort eats too much ram to sort 20.000.000 ints, my algorithms don't. QuickCheck says my implementations are correct. I suppose List.sort does clever things for nonrandom lists, that I didn't consider? I had a look at the source, but I couldn't find anything obvious. Adrian

3 3

Trouble with the ST monad
by Andre Nathan 29 Dec '08

29 Dec '08

Hello, I'm trying to write a function that would take an STArray and and shuffle its elements. I'm having trouble with the ST monad, though, and couldn't find out how fix this issue. The problem happens when I use runST to extract the shuffled array from the ST monad. I'm getting the following error: Inferred type is less polymorphic than expected Quantified type variable `s' is mentioned in the environment: a :: STArray s Int a The full code is at http://hpaste.org/13240#a1 Any help would be appreciated. Thanks, Andre

4 7

Using classes for a heterogeneous graph structure
by Jeremy Bowers 29 Dec '08

29 Dec '08

I'm trying to use a class to create a heterogeneous graph structure. Part of this involves holding things in a Data.Map identified only as "instances of some class", but then I can't figure out how to actually use these things. What is mystifying me is exemplified in the following code: ----------------- module Sample where import qualified Data.Map as Map class Thing thing where set_int :: thing -> Integer -> thing -- for wrapper wrapper :: thing -> ThingWrapper wrapper thing = ThingWrapper thing instance Thing Integer where set_int me i = i -- in the generic case, this actually does something type ThingsByString = (Thing thing) => Map.Map Integer thing update :: Integer -> Integer -> ThingsByString -> ThingsByString update key value map = let (Just thing) = Map.lookup key map in Map.insert key (set_int thing value) map test = let my_map = Map.empty::ThingsByString map1 = Map.insert 0 1 my_map map2 = update 0 8 map1 in map1 data ThingWrapper = forall t. (Thing t) => ThingWrapper t instance Thing ThingWrapper where set_int (ThingWrapper thing) i = wrapper $ set_int thing i wrapper thing_wrapper = thing_wrapper ----------------- This gives an error message (in GHC 6.8 w/ -fglasgow-exts , and yeah, that's deprecated, I'm still in dev): Sample.hs:27:16: Inferred type is less polymorphic than expected Quantified type variable `thing' is mentioned in the environment: map1 :: Map.Map Integer thing (bound at Sample.hs:26:9) my_map :: Map.Map Integer thing (bound at Sample.hs:25:9) In the third argument of `update', namely `map1' In the expression: update 0 8 map1 In the definition of `map2': map2 = update 0 8 map1 Now, I sort of understand this message. What I don't understand is how to do what I want to do; I've rearranged things in a number of ways but this comes up every which way. It seems like once I have one of these "things" there's absolutely nothing I can do to it (or absolutely no way to do what update does, which is mutate it using only the defined class interface without ever knowing what's in there). What's annoying is that at least as a human, what I want seems well-defined to me. Moreover, as shown in the code above, I can create a "wrapper" structure, and if I do that and manipulate only the wrapper (not shown in this example), everything works as I'd like. (If that's the answer, that's OK with me, but it seems klunky, wasteful, and amenable to being automatically done by the compiler as I understand it, and I expect there's a reason it isn't.) My question is: How can I have this heterogeneous graph structure and actually be able to manipulate it solely through a class interface? Or, is it impossible? (I'm open to "you're doing it entirely wrong and you should do X", but in that case I'd like to know what using classes to specify the interface a node should conform to is the wrong thing, because it sure *seems* right, based on what the interface is and how classes are documented. And it would need to work for a heterogeneous graph structure, not my very-simplified example above.) ---------------------------------- Barracuda Networks makes the best spam firewalls and web filters. www.barracudanetworks.com

2 1

RE: Haskell Performance
by Simon Peyton-Jones 29 Dec '08

29 Dec '08

Dear Dave | My question to you is, if you were asked to make a recommendation on | which programming language to use for a program which would run on a | multiple core processor, but also required adequate memory and running | time performance, would you lean towards or away from Haskell? What | other factors would you consider? In other words, was I correct in my | initial opinion that Haskell was more concerned about code expression | rather than performance? Thanks for your email. I'm ccing the Haskell Cafe, which is full of people with practical experience (many more than I) of using Haskell for real applications. I don't think it's possible to give a categorical yes/no answer to your question. Yes, Haskell is designed primarily for high-level expressiveness rather than performance. This is good for programmers, but it cuts both ways for implementation. On the one hand, the programmer is taking less control, and the implementation may not be as clever as a programmer could be (the quicksort example you cite is a good example). On the other hand, the high-level-ness gives the opportunity for the implementation to do stuff that the programmer could not feasibly do by hand; the vectorisation transformation in nested data parallelism is a good example (http://research.microsoft.com/~simonpj/papers/ndp/index.htm) Long term, my bet is that the second trend will win. If you want to write parallel programs, it makes sense to start with a language that is by-default parallel, rather than by-default sequential. But that does not mean that you get parallel performance without tears. Far from it: parallelism is a complex, multi-faceted beast (concurrency, communication, locality, granularity...). So the short-term answer might be different to the long term one. That said, GHC comes out very competitively in the (flawed, but available) language shootout http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=all. So performance is not at all bad. Simon | -----Original Message----- | From: Dave Roberts [mailto:dave.a.roberts@gmail.com] | Sent: 15 December 2008 14:42 | To: Simon Peyton-Jones | Subject: Haskell Performance | | Dear Mr. Peyton Jones, | | I recently watched a video of you giving a talk about type driven | testing in Haskell. | | http://video.google.com/videoplay?docid=- | 4991530385753299192&ei=PWFGSaazDJPuqAL779n1DA&q=simon+peyton+jones+testing&emb=1 | | I found it to be a very informative and entertaining presentation | about Haskell. About halfway through the video you examine the | performance of the n-shell problem in Haskell versus C++. You say the | functional solution to the problem is 100x faster than the C++ | implementation. You continue to examine reasons why, citing that set | operations in a purely functional language can make assumptions that | side-effect laden languages cannot. For example creating a union of | two sets does not need to allocate a new set in memory because it can | reuse large portions of the original sets. You continue to show that | purely functional languages lend themselves to parallelism better than | imperative languages because state is not being changed by default. | | Taking this into consideration, the Haskell website has a section | titled, When C is better. | | http://www.haskell.org/haskellwiki/Introduction#When_C_is_better | | (I suspect you have already read this if not wrote it yourself) This | section looks at the quick sort example presented in the wiki and | claims that if written in an imperative language, the quick sort can | have time and memory requirement advantages over the Haskell version. | I read the haskellwiki long before viewing the video and at the time I | branded Haskell as a language which stresses expression over | performance. | | My question to you is, if you were asked to make a recommendation on | which programming language to use for a program which would run on a | multiple core processor, but also required adequate memory and running | time performance, would you lean towards or away from Haskell? What | other factors would you consider? In other words, was I correct in my | initial opinion that Haskell was more concerned about code expression | rather than performance? What you suggest in the video seems to be to | the contrary. | |

1 0

Incremental trasnformations (not Haskell topic)
by frantisek kocun 29 Dec '08

29 Dec '08

Hi, this is not a Haskell question but I'm not sure if anyone in java community can answer this. And I'm sure every Haskell programmer know OO programing. I'm programming one big boring db application and making a MDD tool to model and generate such applications. Many times object have computed attributes: E.g. value attribute of class Invoice is sum of values of all associated classes Item (Invoice 1 <>---> * Item) So value attribute of invoice is computed every time it is demanded. So far easy.Sometimes it is necessary not to compute it when it is needed but to have it precomputed (computed it every time, item is added/removed to invoice or item value is changed). Contract of attribute value is the same but it is not obvious from code if you program it in event-based as if you program it with expression which is computed every time. Event-based=no big picture. Expression=big picture but little performance. Question: Is there any way how to transform the OO transformation (invoice value is a sum of values of items) to incremental transformation (update invoice value, when item is created/deleted/changed)? Is there any product doing it. I am not interesting in product itself I want only see how it works? Is there any science paper on this? I call this not a function but a OO transformation because it can be much more complicated. I know it is not possible for all the functions (transformations), you have to do undo step, but it is possible for that what we use. One more complicated example: Provider provides money to receiver. It provides money with special code. Receiver sees all the money from all the providers grouped by the code and summed. Every summed group on the code has a subgroup summed on the provider. Provider A provides to R 10 on code "ABC" Provider A provides to Q 10 on code "ABC" Provider A provides to R 5 on code "ABC" Provider A provides to R 20 on code "DEF" Provider B provides to R 30 on code "ABC" Reciever R - recieves 45 on code "ABC", 15 from A, 30 from B - recieves 20 on code "DEF", 20 from A Reciever Q - recieves 10 on code "ABC", 10 from A This example can be easily programmed declarative way in Scala the way that everytime everything is computed. But have no clue if it can be transformed automatically to incremental way. Hope you understand what I mean. Thanks for your help and opinions Fero

5 7

Cross compiling from Linux to windows?
by Erik de Castro Lopo 29 Dec '08

29 Dec '08

Hi all, I've googled for this but haven't really found an answer yet. Is it possible to build (or better yet download) a GHC compiler that runs on Linux and generates windows binaries? I already use the MinGW C compiler to generate windows binaries from C code and I run my test suite under WINE. This has been working very well for me for some time and now I'd like to do the same for Haskell code. Cheers, Erik -- ----------------------------------------------------------------- Erik de Castro Lopo ----------------------------------------------------------------- Those who do not understand Unix are condemned to reinvent it, poorly. -- Henry Spencer

3 3

Data.ByteString join
by Galchin, Vasili 29 Dec '08

29 Dec '08

Hello, http://cvs.haskell.org/Hugs/pages/libraries/base/Data-ByteString.html but vigalchin@ubuntu:~$ ghci GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :m +Data.ByteString Prelude Data.ByteString> :t join <interactive>:1:0: Not in scope: `join' Prelude Data.ByteString> Why no "join" function? Regards, Vasili

4 5

Transactional container for storing anonymous deletable objects
by John Ky 29 Dec '08

29 Dec '08

Hi, I need a container data structure for storing anonymous objects - most likely things that have not value such as STM (), but probably other things as well. This will allow me to later on, iterate over the container and process those objects. Additionally I have the requirement that I need to be able to remove individual objects from this container. It needs to be linear time. main = do container <- nil key1 <- cons 1 container key2 <- cons 2 container key3 <- cons 3 container key4 <- cons 4 container key5 <- cons 5 container unlink key3 container unlink key2 container unlink key4 container list <- toList container putStrLn (show list) The above should give: [1, 5] What should I use? Thanks -John

4 3