- Haskell-Cafe - Haskell.org

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

24 Jun '04

What you are suggesting - whilst it seems reasonable requires a fundamental change to the type system. At the moment [] signifies an empty list of type 'a' ... what you are suggesting requires [] to have a different type from [a]... This means a simple case statement : case a of (a:as) -> [] -> would now not type because everything on the LHS of the cases must be the same type. Infact I don't see how it could be any other way... 'a' has a type call it [a]... how could [] be any other type? Keean.

4 5

RE: atomic MVar overwrite (was RE: [Haskell-cafe] How to use QSem?)
by Simon Marlow 24 Jun '04

24 Jun '04

On 23 June 2004 17:46, S. Alexander Jacobson wrote: > Basically, what I want is a tryReadSampleVar > function. > > Or, if we stick with MVars, I don't want another > thread to operate between the tryTakeMVar and the > putMVar. In particular, I don't want another > thread to believe (mistakenly) that the mvar is > empty when it is simply being updated. > > I suppose I could define a new abstraction where I > have a second mvar that acts as an exclusive lock > on the the first MVar. e.g. > > data XMVar a = XMVar (MVar ()) MVar a > > overWriteXMVar (XMVar lock mvar) val = > withMVar lock (\_->tryTakeMVar mvar >> putMVar mvar val) > tryTakeXMVar (XMVar lock mvar) val = > withMVar lock (\_->tryTakeMVar mvar) > > But, I think it would be more sane simply to > have a tryReadSampleVar somewhere. If you send me code for tryReadSampleVar, I'll incorporate it. Unfortunately SampleVar is abstract, so you'll need to take the source for that library (libraries/base/Control/Concurrent/SampleVar.hs in a GHC distribution) and modify it to create your own version. Cheers, Simon

1 0

Polymorphic algebraic type constructors
by Graham Klyne 23 Jun '04

23 Jun '04

If I have a polymorphic algebraic type (T a) with several type constructors, only one of which actually references the type parameter, is there any way to express type conversion for the type-parameter-independent constructors without actually mentioning all the constructors? Here's a simple example based on Either: [[ data A = A String deriving (Show, Eq) data B = B String deriving (Show, Eq) f :: (a->b) -> Either String a -> Either String b f g (Right a) = (Right $ g a) f g (Left s) = (Left s) -- f g (s) = (s) -- doesn't work a2b (A s) = (B s) t1 = f a2b (Left "x") t2 = f a2b (Right (A "y")) ]] The second case for 'f' throws a type error when the constructor 'Left' is omitted, because the type of 's' is fixed to be Either String A when the required result (in this case, because of a2b) is Either String B. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 6

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

23 Jun '04

Adrian Hey wrote: I think all occurences of [] have type forall a. [a] The case expression.. case a of (a':as) -> <expr1> [] -> <expr2> Should be typed as if written.. case a of (a':as) -> let a=(a':as) in <expr1> [] -> let a=[] in <expr2> ---------------------------------------------------- Well, we will have to agree to disagree, I find the current system makes perfect sense, and is easy to reason with. If I want a let binding I can write one. The difference is really this: case a of (a:as) -> <expr1> e -> e In this case e represent 'the same []' as on the left hand side. in the let binding this is a new and fresh '[]'... When I pattern match a variable in a case extression I really expect it to get the type of the case... There are circunstances when I go on to use e, and if it is not grounded by the case expression I will get hit by the monomorphoism restriction, and have to add non haskell98 type annotation to ground 'e'... for example If I pass e to a polymorphic function, it won't know what type e has... case a of (a':as) -> let a=(a':as) in <expr1> [] -> let a=[] in (polyfn a) where polyfn a has a type like polyfna :: Ord a -> [a] -> String Now the above won't work and you will have to do: [] -> let a=[] in (polyfn (a :: [SomeListType])) and of course if you are using generics then how can polyfn get the original type of 'a' in the case expression... for example: polyfn :: Typable a -> [a] -> ShowS polyfn a = shows (typeOf a) then: case a of (a:as) -> <expr1> e -> polyfn e is correct, but: case a of (a':as) -> let a=(a':as) in <expr1> [] -> let a=[] in (polyfn a) does what? Keean.

2 1

RE: atomic MVar overwrite (was RE: [Haskell-cafe] How to use QSem?)
by Simon Marlow 23 Jun '04

23 Jun '04

On 23 June 2004 17:13, S. Alexander Jacobson wrote: > Ah, that worked. Thank you. The MVar > documentation is also very brief. > > I would also like to overwrite the contents of an > MVar atomically regardless of whether it is full > or empty. I am current using. > > overWrite mvar val = tryTakeMVar mvar >> putMVar mvar val > > But it is not atomic :-( The lib functions > (modifyMVar and tryPutMVar) are atomic but seem to > require that you know in advance the MVar's state. The question to ask here is "atomic with respect to what?". modifyMVar is atomic only with respect to other threads performing modifyMVar-type operations on the MVar (i.e. take followed by put). If another thread is doing repeated puts into the MVar, then modifyMVar's atomicity is defeated. There isn't really a problem here, you just need to be sure that you use your MVars in a consistent way - you can always define a new abstraction that doesn't permit operations to be performed in the wrong order. So in order to tell you how to write your overWrite function, we need to know what other operations are being concurrently performed on the MVar, and what invariants you expect to hold. Cheers, Simon

2 1

RE: [Haskell-cafe] How to use QSem?
by Simon Marlow 23 Jun '04

23 Jun '04

On 22 June 2004 21:44, S. Alexander Jacobson wrote: > 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 If the maximum value of your QSem is 1, then an MVar will do. That is, an MVar can be used as a simple semaphore, and a QSem is necessary if you need a quantity semaphore (there are > 1 units of the resource). > 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 import Control.Concurrent, create the semaphore like this: m <- newMVar () and use it like this: withMVar m $ \_ -> ... critical section ... If you are using the semaphore to protect a mutable variable, then you can handily merge the two ideas into an MVar, which behaves like a thread-safe mutable variable. Cheers, Simon

2 1

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