April 2007 - Haskell-Cafe

Type classes and type equality
by Neil Mitchell 16 Apr '07

16 Apr '07

Hi, I'm looking for a type class which checks whether two types are the same or not. My first guess is: class Same a b where same :: a -> b -> Bool instance Same a a where same _ _ = True instance Same a b where same _ _ = False In Hugs this seems to work with overlapping instances (not requiring unsafe overlapping instances). GHC requires {-# LANGUAGE MultiParamTypeClasses, IncoherentInstances #-} So my question is if this is safe? Will the compiler always pick the "right one"? Is there a better way to do this? The alternative I thought of is using Typeable, but this is not supported particularly well on Hugs (no deriving Typeable) and would require modifications to the existing data structures (additional derivings) so is not such a good choice. Thanks Neil

3 2

Re: [Haskell-cafe] Tutorial on Haskell
by Neil Bartlett 16 Apr '07

16 Apr '07

Well, given that concurrency is a hot topic at the moment, how about something based on STM? E.g. perhaps some kind of instant messaging server? Or "Twitter" except scalable. By ruthlessly eliminating features, you could get the core of one of these down to something that could be built in three hours. But please, no Santa Clauses ;-) Neil > Friends > > I have agreed to give a 3-hr tutorial on Haskell at the Open Source Convention 2007 > http://conferences.oreillynet.com/os2007/ > > I'm quite excited about this: it is a great opportunity to expose Haskell to a bunch of smart folk, many of whom won't know much about Haskell. My guess is that they'll be Linux/Perl/Ruby types, and they'll be > practitioners rather than pointy-headed academics. > > One possibility is to do a tutorial along the lines of "here's how to reverse a list", "here's what a type is" etc; you know the kind of thing. But instead, I'd prefer to show them programs that they might consider *useful* rather than cute, and introduce the language along the way, as it were. > > So this message is to ask you for your advice. Many of you are exactly the kind of folk that come to OSCON --- except that you know Haskell. So help me out: > > Suggest concrete examples of programs that are > * small > * useful > * demonstrate Haskell's power > * preferably something that might be a bit > tricky in another language > > For example, a possible unifying theme would be this: > http://haskell.org/haskellwiki/Simple_unix_tools > > Another might be Don's cpu-scaling example > http://cgi.cse.unsw.edu.au/~dons/blog/2007/03/10 > > But there must be lots of others. For example, there are lots in the blog entries that Don collects for the Haskell Weekly Newsletter. But I'd like to use you as a filter: tell me your favourites, the examples you find compelling. (It doesn't have to be *your* program... a URL to a great blog entry is just fine.) Of course I'll give credit to the author. > > Remember, the goal is _not_ "explain monads". It's "Haskell is a great way to Get The Job Done". > > Thanks! > > Simon > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

type inference futility
by Paul Wankadia 16 Apr '07

16 Apr '07

The following code has ambiguity, but I can't figure out how to get around it. Am I missing something trivial? Am I going in the wrong direction? Thank you in advance for your time and for any help that you can offer. > data MehQueue = MehQueue > > class MehBase a where new :: IO a > instance MehBase MehQueue where new = return MehQueue > > class (MehBase a) => HasShift a where shift :: a -> IO a > instance HasShift MehQueue where shift a = return a > > main :: IO () > main = do > x <- new > shift x > return () Please note that I intend to extend this example with MehStack, HasPush and HasPop. You can probably guess where I'm going with all this.

3 3

ghci Crashing...
by Gaetano Caruana 16 Apr '07

16 Apr '07

Hi all. I am new to this list ;) Today I have encountered something new that has never happened to me in the past 6 months that I have been using ghci and Haskell. I wrote this function: type Line = (Point,Point) type Point = (Float,Float) circleLineIntersection :: Float -> Float -> Float -> Line -> Maybe [Point] circleLineIntersection h k r ((x1,y1),(x2,y2)) = do let perpdist = calcPerpDist (h,k) ((x1,y1),(x2,y2)) noSolution = perpdist > r oneSolution = perpdist == r twoSolutions = perpdist < r in do if noSolution then Nothing else let dx = x2 - x1 dy = y2 - y1 dr = sqrt (dx * dx + dy * dy) bigD = x1 * y2 - x2 * y1 x1 = ( bigD * dy + sign (dy) * dx * sqrt( r * r * dr * dr - bigD * bigD ) ) / (dr * dr) y1 = - bigD * dx + abs(dy) * sqrt( r * r * dr * dr - bigD * bigD ) / (dr * dr) x2 = ( bigD * dy - sign (dy) * dx * sqrt( r * r * dr * dr - bigD * bigD ) ) / (dr * dr) y2 = - bigD * dx - abs(dy) * sqrt( r * r * dr * dr - bigD * bigD ) / (dr * dr) in if oneSolution then do Just [(x1,y1)] else do Just [(x1,y1),(x2,y2)] Compiling is fine... When I run the function like this.... circleLineIntersection 1 1 1 ((1,1),(2,2)) it simply outputs.... Just [( No CPU usage. I am using fglasgow-exts Thanks for your help. Gaetano

2 1

System.Random
by Ketil Malde 16 Apr '07

16 Apr '07

Hi, I've recently stumbled upon some issues with the System.Random module, and thought I'd try to remedy them. However, I'm not quite sure what an optimal resolution is. Problem 1 is that I often get the same "random" number on consecutive program runs [1]. Looking at the code for initialization (called with '0' argument on program start): mkStdRNG :: Integer -> IO StdGen mkStdRNG o = do ct <- getCPUTime (TOD sec ms) <- getClockTime return (createStdGen (sec * 12345 + ms + ct + o)) Considering that 'getCPUTime' tends to return 0 early in the program, and that we simply ignore the picosecond part of 'getClockTime', it's fairly obvious why we get this result. What is not obvious is the rationale for discarding 'ms', or for that matter, the 12345 multiplication - can anybody shed some light on this? Anyway, on my Linux system, I get (unsurprisingly considering the defintion of time_t) picoseconds in even millions, and successive calls to getClockTime are not successive enough to give the same result in my cases. A better implementation would perhaps use /dev/urandom, but that is possibly not portable enough? The second issue is reading the random state from a string [2]. I realize (as Simon points out) that you can use 'reads' to get the remainder of the string, but as many find it confusing (at least the OP and I :-), I wonder what the rationale is behind this kind of interface? And checking how the state is actually calculated: stdFromString :: String -> (StdGen, String) stdFromString s = (mkStdGen num, rest) where (cs, rest) = splitAt 6 s num = foldl (\a x -> x + 3 * a) 1 (map ord cs) So, it picks six chars, and folds them into an Int for mkStdGen. Now, this number (due to the low multiplier) never exceeds 93549. Since we have an Int of state, why not use the whole range? Why not fold with a multiplier of 256? (All of this is trivial to fix of course, but I worry about changing code I don't understand the rationale behind.) One final question: are there build and install instructions for 'base'? I got the code from darcs, but I haven't find a way to build it and replace the bundled 'base' with a new version. -k References: [1] http://hackage.haskell.org/trac/ghc/ticket/1272 [2] http://www.nabble.com/Re% 3A--Haskell-cafe--System.Random-StdGen-read-fails-on-some-strings--tf3394495.html#a9450043 [3] http://web.archive.org/web/20011027002011/http://dilbert.com/comics/dilbert…

1 0

partial kinds and instances
by Matthew Pocock 16 Apr '07

16 Apr '07

Hi, I saw that it's possible to peal off kinds from the right-hand side when instantiating classes. Is it possible to peel them off from the left-hand side? Or in any order? I have been told in #haskell by people who seems to know that Very Bad Things happen if you do this without also making the kind system more clever. Is there a quick fix that will give me the same effect, without introducing a newtype or re-writing the original type declaration to introduce the extra types in a different order? Illustrative code below. Matthew data MyType e = Singleton e data MyOtherType k v = Empty | Node k v data YetAnotherType k v = OtherEmpty | OtherNode k v type RevYAT v k = YetAnotherType k v class Iterable ite where iterate :: ite e -> [e] instance Iterable MyType where iterate (Singleton e) = [e] instance Iterable (MyOtherType k) where iterate ite = [] --broken but illustrative instance Iterable (RevYAT v) where iterate it = [] --broken again Type synonym `RevMOM' should have 2 arguments, but has been given 1 In the instance declaration for `Iterable (RevYAT v)'

1 0

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