- Haskell-Cafe - Haskell.org

Re: [Haskell] Re: ANN: wl-pprint-1.0: Wadler/Leijen pretty printer
by Duncan Coutts 16 Apr '07

16 Apr '07

On Mon, 2007-04-16 at 10:08 +0000, Arthur van Leeuwen wrote: > Goody! UU.PPrint is now on hackage! Regrettably, this does seem like > a bit of a waste of time, as UU.PPrint was already cabalised as part > of the Haskell Utrecht Tools at http://www.cs.uu.nl/wiki/HUT/ > which also contains the parser combinators and DData, Daan > Leijen's datastructure library. > > Doei, Arthur. (Who thinks Utrecht does too little marketing of its code :)) I'd like to note that uulib and uuagc have been included in Gentoo for ages! :-) Duncan

1 0

Re: [Haskell-cafe] k-minima in Haskell
by raghu vardhan 16 Apr '07

16 Apr '07

There seems to be some confusion about the question. There are two key things to keep in mind here: 1) You must make at most O(k*n) comparisons (in the worst case) if the list has length n. 2) The output must be the indices and not the numbers themselves. So, any algorithm that sorts is no good (think of n as huge, and k small). Another interesting caveat to this is that if k=2, you can actually solve the problem with just (n+log n) comparisons in worst case(instead of 2*n, that you get by a naive approach), and it's a nice exercise to do this. As a further clarification, this is not a homework question. I genereally do whatever programming I do in Matlab, as I work with matrices (huge ones) and use this function a lot. I just wanted to see how different an implementation you can get in Haskell (I am new to Haskell so I might not be able to come up with the best way to do this). ----- Original Message ---- From: Stefan O'Rear <stefanor(a)cox.net> To: raghu vardhan <mrvr84(a)yahoo.co.in> Cc: haskell-cafe(a)haskell.org Sent: Wednesday, 11 April, 2007 10:47:08 PM Subject: Re: [Haskell-cafe] k-minima in Haskell On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote: > On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote: > > What's the best way to implement the following function in haskell: > > Given a list and an integer k as input return the indices of the least > > k elements in the list. The code should be elegant and also, more > > importantly, must not make more than the minimum O(k*length(list)) > > number of operations. > > Go read and thoroughly understand "Why Functional Programming > Matters." > > Also, your asyptotic complexity bound is just plain wrong. I'd give > faster code, but Don is suspicious (and I can never tell these things > myself). > > Stefan Don tells me (in #haskell) that you are legitimate, so here is the example: kminima k lst = take k $ sort lst If you want to be really explicit about it, here is a sort that will work: sort [] = [] sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l (A stable quicksort, btw) Note that this is FASTER than your bound - somewhere between O(n) and O(n*log n). Ain't lazy evaluation great? :) Stefan Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now at http://in.messenger.yahoo.com/

11 13

GADTs and Typeclasses
by Dominic Steinitz 16 Apr '07

16 Apr '07

Will I run into problems using typeclasses with GADTs? I've come up with this to model a fragment of ASN.1. I'd hate to spend a lot of time on this only to find out it's well known that these two features don't mix very well. Thanks, Dominic. data Type :: * -> * where INTEGER :: Type Int BOOLEAN :: Type Bool BITSTRING :: Type BitString NUMERICSTRING :: Type NumericString ReferencedType :: Type () -- for now ConstrainedType :: Type a -> Constraint a -> Type a SizeConstrainedType :: Size a => Type a -> Constraint Int -> Type a FromConstrainedType :: From a => Type a -> Constraint a -> Type a

2 1

LL(1) parsing of declarators
by Stefan O'Rear 15 Apr '07

15 Apr '07

I'm writing a code generator for C, and I'm trying to parse a C-like input language using LL(1) (parsec specifically). The syntax of declarators is giving me trouble: (simplified) declaration = qualifiers >> (declarator `sepBy1` char ',') qualifiers = many1 name declarator = name now if we have "<name> <name>", they are both parsed by the greedy many1 in qualifiers! I can make this work with some ugly rearranging: declaration = fdeclarator >> many (char ',' >> declarator) fdeclarator = name >> many1 name declarator = name is there a more elegant way? Stefan

2 3

darcs error
by Ruben Zilibowitz 15 Apr '07

15 Apr '07

What does it mean if I'm trying to check out a darcs repository and I get the following error? darcs: ./.DS_Store: openBinaryFile: does not exist (No such file or directory) .DS_Store files ought to be filtered out by the default boring file. I don't know how one got into the repository and started causing this error. Is there some way to repair the repository? darcs repair doesn't seem to help. Regards, Ruben

2 2

Weaving fun
by Bas van Dijk 15 Apr '07

15 Apr '07

Hello, For my own exercise I'm writing a function 'weave' that "weaves" a list of lists together. For example: weave [[1,1,1], [2,2,2], [3,3]] ==> [1,2,3,1,2,3,1,2] weave [[1,1,1], [2,2], [3,3,3]] ==> [1,2,3,1,2,3,1] Note that 'weave' stops when a list is empty. Right now I have: weave :: [[a]] -> [a] weave ll = work ll [] [] where work ll = foldr f (\rst acc -> work (reverse rst) [] acc) ll f [] g = \_ acc -> reverse acc f (x:xs) g = \rst acc -> g (xs:rst) (x:acc) However I find this definition hard to read and I'm questioning its efficiency especially due to the 'reverse' parts (how do they impact performance and can they be removed?) So I'm wondering if 'weave' can be defined more "elegantly" (better readable, shorter, more efficient, etc.)? happy hacking, Bas van Dijk

10 16

Calling C function in Mac OS X
by Sergey Perminov 15 Apr '07

15 Apr '07

I wish to optimize Haskell code using ByteString, direct reading Doubles form it, direct writing Doubles to it. I've tried Don Stewart's code http://hpaste.org/26 that uses calling to C functions to implement necessary readDouble & showDouble. readDouble works ok. showDouble always return "nan" in Mac OS X (but works well in Windows). I'm using GHC 6.6 in Mac (http://www.haskell.org/ghc/download_ghc_66.html#macosxppc) and in Windows (http://www.haskell.org/ghc/download_ghc_66.html#windows) I've made showInt based on showDouble: http://hpaste.org/1390 It works well in Mac OS X. It seems that problem happens only when I send CDouble (or CLDouble) to C function. My conf: PowerBook G4, Mac OS X 10.4.9, powerpc-apple-darwin8-gcc-4.0.1 What may cause this? How to fix it?

2 2

k-minima in Haskell
by raghu vardhan 15 Apr '07

15 Apr '07

What's the best way to implement the following function in haskell: Given a list and an integer k as input return the indices of the least k elements in the list. The code should be elegant and also, more importantly, must not make more than the minimum O(k*length(list)) number of operations. R M Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now at http://in.messenger.yahoo.com/

13 20

Do monads imply laziness?
by Brian Hurt 14 Apr '07

14 Apr '07

This is probably an off-topic question, but I can't think of a better forum to ask it: does the existance of monads imply laziness in a language, at least at the monadic level? Consider the following: a purely functional, eagerly evaluated programming language, that uses monads to encapsulate the awkward squad. In this programming language, a program generates an IO monad whose encapsulating computation performs side effecting affections- it writes to stdout, say. But this generated monad never has it's value evaluated- the monad is tossed away uninspected. Does the side effect happen? If the answer is at least potientially "no", then monads are lazily evaluated, and thus monads imply laziness (at least at the monadic level). On the other hand, if the answer is "yes", then monads do not imply laziness. Thanks, Brian

3 2

Left-factoring with Parsec
by Joel Reymont 14 Apr '07

14 Apr '07

Suppose I have expr = expr ":" expr ":" expr. Can the above be left-factored to fail on empty input so that my parser doesn't go into a loop? Thanks, Joel -- http://wagerlabs.com/

3 4