- Haskell-Cafe - Haskell.org

online judge with Haskell
by Tomek Noiński 23 Jun '04

23 Jun '04

I have read a post to this list from about a year ago, considering Haskell support on online judges, like acm.uva.es. I think our online judge (a system for the verification of the correctness of submitted programs, which solve problems selected from a repository) might interest you. The Sphere Online Judge (SPOJ) is available at http://spoj.sphere.pl, and supports solutions written in 20 different programming languages including Haskell. We would like to invite you to solve problems at our server. At present, nearly half of the rapidly expanding problemset (currently more than 60 tasks) can be solved using functional languages easily within the time-limit. It is possible to add tasks dedicated to functional programming and the development team will be glad to cooperate if you are willing to create some new interesting problems. With best wishes, Adrian Kosowski, Michal Malafiejski, Tomasz Noiński, Gdansk University of Technology, Poland

1 0

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 23 Jun '04

23 Jun '04

>f (i:is) = even i : f is >f e = e This still makes perfect sense to me... you see the let binding: let e@[] = e has no additional information about the type of [] so it must be fully polymorphic. if the function binding we know typeOf e == typeOf (i:is) and that i is a member of the class Integral (from the application of even) As we always take the most precise available type we end up with forall a. Integral a => [a] as the type for 'e'... Now Bool is not a member of Integral so it is a type error! Keean.

2 1

RE: [Haskell-cafe] Ord (IORef a)?
by Simon Marlow 23 Jun '04

23 Jun '04

On 23 June 2004 03:53, John Meacham wrote: > Yeah, i forgot about the GC moving things around. actually, if the GC > could be coaxed to move things around, but never change the relative > order of IORefs (like a compacting collector), then the address could > still be used for Ord and Eq. This is a rather restrictive global invariant, I don't think it's practical. > how is Eq implemented such that the GC doesn't move one side after you > read the address of the other? The sameMutVar# primitive is atomic with respect to the GC. It ought to be possible to implement Ord on IORef using StablePtr, but for some reason StablePtr isn't an instance of Ord. Cheers, Simon

1 0

RE: [Haskell-cafe] Ord (IORef a)?
by Simon Marlow 23 Jun '04

23 Jun '04

On 22 June 2004 10:38, Simon Peyton-Jones wrote: >> From: John Meacham >> would it be possible to provide an Ord instance for (IORef a)? For >> things like loop detection, one may need to make many IORef >> comparasions and being able to use an efficient set would be a >> really big win. >> >> Since IORefs are created in the IO monad, the actual order can be >> arbitrary without breaking referential transparency (as long as it >> doesn't change over the lifetime of the IORef.) > > I think that'd be entirely reasonable. Two runs of the same program > might give observably different behaviour wrt Ord, but that's ok > because the refs are allocates in the monad, as you say. > > There is an efficiency cost though. Each IORef would need to have an > extra field, to record its allocation ID. (Address is not enough -- > the garbage collector can mangle them.) > > My own view is that this is fine -- IORefs shouldn't be in your inner > loop, so an extra word in each is no big deal. Unless there are > views to the contrary, I'd be happy to see this in GHC. I'm torn. If it were free, it would be a no-brainer. But I know of several cases where IORefs are performance-critical (or at least performance-important). We should implement & measure. Cheers, Simon

2 1

RE: [Haskell-cafe] Ord (IORef a)?
by Simon Peyton-Jones 23 Jun '04

23 Jun '04

| From: John Meacham | would it be possible to provide an Ord instance for (IORef a)? For | things like loop detection, one may need to make many IORef comparasions | and being able to use an efficient set would be a really big win. | | Since IORefs are created in the IO monad, the actual order can be | arbitrary without breaking referential transparency (as long as it | doesn't change over the lifetime of the IORef.) I think that'd be entirely reasonable. Two runs of the same program might give observably different behaviour wrt Ord, but that's ok because the refs are allocates in the monad, as you say. There is an efficiency cost though. Each IORef would need to have an extra field, to record its allocation ID. (Address is not enough -- the garbage collector can mangle them.) My own view is that this is fine -- IORefs shouldn't be in your inner loop, so an extra word in each is no big deal. Unless there are views to the contrary, I'd be happy to see this in GHC. Simon

4 3

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 22 Jun '04

22 Jun '04

>to be [] in each case. ahh but in this example: f :: [Int] -> [Bool] f (i:is) = even i : f is f e@[] = e e is an empty list of Ints not an empty list of Bools! you mean: f :: [Int] -> [Bool] f (i:is) = even i : f is f _ = [] Keean.

3 3

How to use QSem?
by S. Alexander Jacobson 22 Jun '04

22 Jun '04

The GHC documentation on QSem is very sparse. I would like to give a thread exclusive access to a resource. My *guess* based on the documentation is that I can create an exclusive lock using: logSem <- newQSem 1 And then any thread that wants to lock the resource uses: withLogSem x = do waitQSem logSem; y <- x; signalQSem logSem; return y as follows: withLogSem $ rotate curLogPos Am I misunderstanding QSem? -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com

1 0

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 22 Jun '04

22 Jun '04

>(I still think it's a bug though:-) It is definitely not a bug... you cannot assert that the types: Either String a Either String b are both equal ant not equal at the same time. You either mean: f :: (a->a) -> Either String a -> Either String a Or you mean f :: (a->b) -> Either String a -> Either String b actually the second form a and b can be the same but they cannot be unified inside the closure. One way of doing this is to group all the string types on one side: so instead of: data A a = A a | B String | C String | D String you do: data A a = A a | B Strings data Strings = S1 String | S2 String | S3 String you can then write: f :: (a->b) -> A a -> A b f g (A a) = (A $ g a) f g (B a) = (B a) and use (S1 . B), (S2 . B), (S3 . B) to access each string. Keean.

2 1

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 22 Jun '04

22 Jun '04

>data E a b > = L1 { r :: a } > | L2 { r :: a } > | L3 { r :: a } > | L4 { r :: a } > | R b > deriving Show How is this different from: data E a b = L1 a | L2 a | R b f g (R a) = R (g a) f _ other = other Isn't this more or less what was in the original... The problem is the type: f :: (a->b) -> Either String a -> Either String b this line: f _ other = other says: Either String a == Either String b -- which it doesn't Keean.

2 2

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 22 Jun '04

22 Jun '04

>If I have a polymorphic algebraic type (T a) with several type data MyType a = A a | B String | C Int So how do you expect to get the contents of B and C outm when they are differenf Types - surely you mean: data MyType a = A a | B MyStrings Keean.

1 0