January 2005 - Haskell-Cafe

FFI and C99 "complex"
by Aaron Denney 16 Jan '05

16 Jan '05

Basically, what's the best way to deal with C99's complex types? Pragmatically, how do I deal with them in function definitions now? Is there any chance they'll get added to a later version of the FFI addendum? -- Aaron Denney -><-

2 2

Is it possible to print out types of instances in scope
by Jeremy Shaw 16 Jan '05

16 Jan '05

Hello, Is it possible to write a function that would display all the instances of a class currently in scope[1]? For example, for 'Show a' it should output something like: The instances of 'Show a' currently in scope are: Show Int Show Float Show Char Show ... Depending on what modules are imported at compile time, the list would grow or shrink. I am willing to accept all sorts of restrictions at this point in time such as: ~ Yes, but only if the classes are declared in this way (but not for ones declared in the standard library) ~ Yes, but it requires template haskell It is currently my belief that the compiler "knows" the answer, but there is no way to get the list from the compiler... I would be interested in any information, links, examples, papers, etc, that you can provide that would tell me: ~ Yes it can be done ~ It could be done with a compiler extension ~ It could never be done ~ It could be done, but it would be a really horrible idea, and here's why So don't hold back :) Thanks! Jeremy Shaw. [1] I suppose by 'currently in scope' I mean all the instances that type checker is considering when it type checks the function at compile time. But I am really not picky about what I mean right now as I can't get anything remotely ressembling this to happen.

3 4

Efficiency Question
by Daniel Fischer 15 Jan '05

15 Jan '05

Hi folks, toying a bit with splitAt and take, I have met yet another thing, I don't understand. In the Hugs Prelude, splitAt is defined splitAt n xs | n <= 0 = ( [],xs) splitAt _ [] = ([],[]) splitAt n (x:xs) = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs whereas in the report it is described as (take n xs,drop n xs) -- I have no problem with that, since the report explicitely states that the functions need not be implemented as given there --, let's call that function bSplit (b was chosen for 'bad'). Now, as expected, splitAt takes fewer reductions than bSplit, splitAt (n+1) takes 18 reductions more than splitAt n, bSplit (n+1) takes 32 more than bSplit n (24 for take, 8 for drop). So far so good, now changing to ghci and testing that on a long list ([1 .. 1000000], [1 .. 500000]), splitting at half, then printing the two middle numbers. The first surprise was that there bSplit was faster than splitAt (roughly twice as fast). Does anybody know how that can be?? The second surprise was the variation of time needed. For the longer list, splitAt usually took 0.45 - 0.48 secs, occasionally about 0.9 secs (I think that will be due to gc), bSplit usually took 0.22 - 0.25 secs, occasionally about 0.7 secs (gc, probably). For the shorter list, splitAt took 0.22 - 0.28 secs (0.7 with gc), bSplit took 0.10 - 0.20 secs (0.6 with gc). Now, what's the explanation for that? Differences of, say, 0.03 secs or so I happily attribute to an occasional interrupt or something, but the difference between 0.10 and 0.20 I would like an explanation for. Another thing, while toying, I found out that a comparison (n <= 0) takes three reductions more than (n < 1) according to my hugs, so changing the definition of splitAt thus, we require (3*n) reductions less. But the number of reductions and speed are different things, as witnessed by the above, so would it be an improvement to replace "n <= Integerliteral"-queries by "n < Integerliteral"-queries or doesn't that make any difference at all in execution time? Finally, in several contexts I needed to cons an element to one of a pair of lists, so I defined infixr 5 &,§ (&) :: a -> ([a],[b]) -> ([a],[b]) x & (xs,ys) = (x:xs,ys) (§) :: b -> ([a],[b]) -> ([a],[b]) y § (xs,ys) = (xs,y:ys). I find them useful (though I don't like the symbols, if you have any better ideas, thx) and for splitAt, (&) saves another reduction per step. Now, I would like to have such operators supplied by the language, so is there space for them in the Prelude or in List, or does hardly anyone besides me ever need them? Have a wonderful weekend ye all, Daniel

4 7

Linear shuffle
by Gracjan Polak 15 Jan '05

15 Jan '05

Hi, I want to implement linear list shuffle in Haskell (http://c2.com/cgi/wiki?LinearShuffle) and I invented code: shuffle :: [a] -> IO [a] shuffle [] = return [] shuffle x = do r <- randomRIO (0::Int,length x - 1) s <- shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s) This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? -- Gracjan

10 18

Efficiency Question
by Derek Elkins 15 Jan '05

15 Jan '05

> Another thing, while toying, I found out that a comparison (n <= 0) > takes three reductions more than (n < 1) according to my hugs, so > changing the definition of splitAt thus, we require (3*n) reductions > less. But the number of reductions and speed are different things, as > witnessed by the above, so would it be an improvement to replace "n <= > Integerliteral"-queries by "n < Integerliteral"-queries or doesn't > that make any difference at all in execution time? I don't know about in Hugs, but in (compiled, optimized) GHC it should make no difference. Presumably, if you are running something in an interpreter micro-optimizing isn't worthwhile. > Finally, in several contexts I needed to cons an element to one of a > pair of lists, so I defined > > infixr 5 &,§ > > (&) :: a -> ([a],[b]) -> ([a],[b]) > x & (xs,ys) = (x:xs,ys) > > (§) :: b -> ([a],[b]) -> ([a],[b]) > y § (xs,ys) = (xs,y:ys). Well, to start, the type signatures are unnecessarily restrictive. Then, the function that also is not in the Report, but does come up quite a bit by people who get into a point-free or categorical style is the bifunctor, (***) :: (a -> b) -> (c -> d) -> (a,c) -> (b,d) f *** g = \(a,b) -> (f a,g b) this is an instance of (***) in Control.Arrow, hence the name. So, your first function is, (&) x = (x:) *** id or using another function from Control.Arrow, (&) x = first (x:) I can say that I have wanted (***), I can't say that I've ever wanted your two functions. Also, first (x:) seems to be more self-documenting.

2 1

Re: [Haskell-cafe] Efficiency Question
by Tom Pledger 14 Jan '05

14 Jan '05

Daniel Fischer wrote: [snip] >Another thing, while toying, I found out that a comparison (n <= 0) takes >three reductions more than (n < 1) according to my hugs, so changing the >definition of splitAt thus, we require (3*n) reductions less. > That difference looks like it comes from the default definitions of (<) and (<=) in Ord, and the default definition of (/=) in Eq. There's potential for Hugs to scrounge a little extra performance by going straight to case expressions in its Prelude: Prelude> 1 >= 0 True (28 reductions, 42 cells) Prelude> 1 > 0 True (25 reductions, 39 cells) Prelude> let x `gt` y = case x `compare` y of GT -> True; _ -> False in 1 `gt` 0 True (23 reductions, 37 cells) Prelude> let x `ge` y = case x `compare` y of LT -> False; _ -> True in 1 `ge` 0 True (23 reductions, 37 cells) Regards, Tom

1 0

Re: [Haskell-cafe] Problem with wxHaskell
by Atwood, John Wesley 14 Jan '05

14 Jan '05

> Jinwoo Lee <jinwoo68(a)gmail.com> > You can remove that error message by including following in > package.conf file. > > Package > {name = "readline", > auto = True, > import_dirs = ["$libdir/imports"], > source_dirs = [], > library_dirs = ["$libdir"], > hs_libraries = ["HSreadline"], > extra_libraries = ["readline", "advapi32"], > include_dirs = [], > c_includes = ["HsReadline.h"], > package_deps = ["base"], > extra_ghc_opts = [], > extra_cc_opts = [], > extra_ld_opts = [], > framework_dirs = [], > extra_frameworks = []}, > > Jinwoo Lee > > Always remember that you are unique. Just like everyone else. > jinwoo68(a)gmail.com You'll still run into the problem: Failed to load interface for `Graphics.UI.WXCore.Dialogs': Bad interface file: C:\Program Files\wxhaskell-0.8\lib/imports/Graphics/ UI/WXCore/Dialogs.hi mismatched interface file versions: expected 6022, found 6021 The right fix would be to recompile wxHaskell from source, but since I don't have cygwin installed on a handy machine, I tried editing the .hi files, jamming in the 6022 version number. That worked, at least for the examples I tried. I used the old DOS command, debug (I thought TextPad would respect binary files, but it didn't). the 1 byte change is at offset 1b (or 11b in debug). John

1 0

Re: [Haskell-cafe] Linear shuffle
by Atwood, John Wesley 14 Jan '05

14 Jan '05

> Gracjan Polak <gracjan(a)acchsh.com> wrote: > John Meacham wrote: > > Oleg wrote a great article on implementing the perfect > shuffle. with > > some sample code. > > > > http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle > > > > Thats the kind of answer I was hoping to get :) Thanks. > > > shuffle could be useful in standard library. At least Python > has it. I > was translating some small Python program, the hardest part was the > missing shuffle function. What do you think? Also, note that, in a lazy language, the algorithm's complexity will be dependent on the number of cards drawn from the deck, are possibly sub-linear in the number of cards in the deck. John

1 0

Matroids in Haskell
by Gerhard Navratil 14 Jan '05

14 Jan '05

Recently I had a course on matroids and would like to investigate the topic a little further. Did anybody write (or start writing) a Haskell-implementation for matroids? It would save me some time figuring out if this part of mathematics is useful for my work ... Thanks in advance, Gerhard ======================================== Gerhard Navratil Teaching- And Research-Assistant Technical University Vienna, Austria Institute of Geoinformation and Cartography Gusshausstr. 27-29, 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12712 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at

3 2

Linear Shuffle
by Okasaki, C. DR EECS 14 Jan '05

14 Jan '05

Clearly, you can do a perfect shuffle in O(N) time using mutable arrays, using the standard imperative algorithm. You can also do it in O(N) expected time using *immutable* arrays, using Haskell's bulk array operations. 1. Start with a list of length N. If N < 2, stop. 2. Pair each element with a random index in the range [1,2N] (or [0,2N-1]). 3. Use "accum" to create an array of size 2N, where slot I contains a list of all the elements paired with I. 4. Map the shuffle function recursively across the array to re-shuffle any slots that got more than one element. 5. Append all the slots together into the result list. If you leave out step 4, you get an algorithm that runs in O(N) worst-case time, rather than expected time, but you no longer have a perfect shuffle (although it might be good enough). Upping the size of the array from 2N to 3N or 4N will help reduce collisions, but will not entirely eliminate them. With step 4, you can imagine pathological cases where everything gets put in the same slot, but with a reasonable random number generator, it is vanishingly unlikely that you will have enough collisions to drive the cost higher than linear. Again, upping the size of the array from 2N to 3N or 4N makes this even more unlikely. -- Chris

1 0