- Haskell-Cafe - Haskell.org

Roman Numerals and Haskell Syntax abuse
by George Russell 06 Jul '04

06 Jul '04

The following declaration for a function for converting positive integers to Roman numerals is 181 characters long. Is there a shorter one? roman=f[(i-j,i)|i<-[2,4..8],j<-[2,1]]where f(d@((a,b):c))n|n<1=""|n>=t!!a=s!!a:f d(n-t!!a)|1>0=if n+t!!b>=t!!a then s!!b:f d(n+t!!b)else f c n;s="mdclxvi";t=[1000,500,100,50,10,5,1]

6 9

RE: [Haskell-cafe] readMVar and the devils
by Simon Marlow 06 Jul '04

06 Jul '04

On 02 July 2004 10:16, Conor T McBride wrote: > Hi folks > > I'm having a play with Concurrent Haskell, and came across this in the > library. > > readMVar :: MVar a -> IO a > This is a combination of takeMVar and putMVar; ie. it takes the > value from the MVar, puts it back, and also returns it. > > I was just wondering if I understand things correctly. Suppose myMVar > is nonempty and I have one thread executing > > do x <- takeMVar myMVar -- (A) > putMVar myMVar x -- (B) > return x > > and another executing > > putMVar myMVar y -- (C) > > Questions > > (1) Is it possible that an evil scheduler will execute (A) then (C) > and block on (B)? Yes. In fact, you don't need an evil scheduler, an ordinary scheduler will do this :-) > (2) Is it the case that if myMVar is nonempty and readMVar is chosen > for execution, that readMVar myMVar takes the value > from myMVar, guaranteed that the _same_ value will be put > back immediately, and also returned? Only if there are no other threads executing putMVar on myMVar concurrently. > (3) If yes to both, what combination of takeMVar and putMVar manages > to maintain the lock in between the two? There isn't one. readMVar is only atomic with respect to other well-behaved threads; that is, other threads doing strictly take-followed-by-put operations. There are lots of similar cases in the world of MVars. Our general approach is that we provide combinators which help you build correct code (eg. withMVar, modifyMVar), but you can always shoot yourself in the foot by using the lower-level operations. > I'm only asking, because I'm trying to cook up some kind of partial > evaluator for programs which are being simultaneously edited by > fiercely argumentative devils. Kind of `demonic laziness', where > the computations decide when _they_ feel like running (eg sometime > after the program turns up), rather than the `angelic laziness' we're > used to. I'd like to use MVars in a write-once-read-many style, so > that once someone fills in a bit of program, it stays put. I'd hate > for another devil to sneak in a replacement program just in the > twinkling of an eye between taking something out to read and putting > it back to be read again. > > I guess I could use some kind of extra semaphore MVar to ensure that > the reader has the lock on the program MVar, but that's more like > hard work. Is readMVar what I want? It sounds like you want a different abstraction, but one that can almost certainly be built using MVars. I'm not sure exactly what it is you need, but if you provide the signatures of the operations then I could probably sketch an implementation. Cheers, Simon

2 1

Re: [Haskell-cafe] readMVar and the devils
by MR K P SCHUPKE 06 Jul '04

06 Jul '04

at a guess the magic take put is: block ( do a <- takeMVar x putMVar x a ) return a Keean.

3 2

Re: Help in understanding a type error involving forall and class constraints
by oleg＠pobox.com 06 Jul '04

06 Jul '04

> Is it possible to return an arbitrary unboxed array that was > constructed in the ST monad (as an STUArray)? > The issue is that you end up with a MArray class constraint that > involves the state thread's 's' parameter, but this type > variable gets 'hidden' by runST which universally quantifies > over it. runST :: forall a. (forall s. ST s a) -> a That seems to be possible. Let us start with the original code: > buildUArray' bounds f = do > arr <- newArray_ bounds > mapM_ (\i -> writeArray arr i (f i)) (range bounds) > return arr > > buildUArray bounds f = do arr <- buildUArray' bounds f > unsafeFreeze arr If we check for the type of buildUArray *Foo> :t buildUArray buildUArray :: forall e a1 b m a. (MArray a e m, Ix a1, IArray b e) => (a1, a1) -> (a1 -> e) -> m (b a1 e) we see the problem. It is in the constraint MArray a e m. If we use that function in runST, as in foo bounds f = runST (buildUArray bounds f) the constraint 'MArray a e m' has to be provided by the function foo. However, 'm' in that constraint will be 'ST s', so the state variable escapes. Therefore, the typechecker rejects foo. We should notice that the type variable 'a' in the above type appears only in the constraint -- but not in the types. That is, 'a' will be _existentially_ quantified. Thus, we can provide the needed constraint via an explicit existential type. Here's the solution > data Allocator m i e = forall a. MArray a e m => > Allocator ((i, i) -> m (a i e)) > > buildUArray'' allocator bounds f = > case allocator of > Allocator alloc -> do > arr <- alloc bounds > mapM_ (\i -> writeArray arr i (f i)) (range bounds) > unsafeFreeze arr *Foo> :t buildUArray'' buildUArray'' :: forall e a b m. (Monad m, Ix a, IArray b e) => Allocator m a e -> (a, a) -> (a -> e) -> m (b a e) That type shows that now buildUArray'' is truly polymorphic over the array types; furthermore, the particular MArray type is irrelevant. As we can see, the MArray constraint is nowhere to be found -- just as we wanted to. we can define one particular allocator, specifically for STUArray > allc:: Ix i => Allocator (ST s) i Bool > allc = Allocator (newArray_:: Ix i => (i,i) -> ST s (STUArray s i Bool)) we can then write > foo bounds f = runST (buildUArray'' allc bounds f) > test = foo (1::Int,2::Int) (const True) :: Array Int Bool One can say that foo builds only arrays of Booleans. Can we have a function that builds polymorphic arrays? The answer is again yes. We merely need to make our allocator polymorphic with respect to the type of the array: > class STUGood e where > allcg::Ix i => Allocator (ST s) i e > instance STUGood Bool where > allcg = Allocator (newArray_:: Ix i => (i,i) -> ST s (STUArray s i Bool)) > instance STUGood Float where > allcg = Allocator (newArray_:: Ix i => (i,i)-> ST s (STUArray s i Float)) etc. > bar bounds f = runST (buildUArray'' allcg bounds f) *Foo> :t bar bar :: forall e i b. (IArray b e, STUGood e, Ix i) => (i, i) -> (i -> e) -> b i e The type of bar is indeed polymorphic with respect to the index, the sort of the array, and the type of the element of the array: > test2 x :: Array Int x = bar (1::Int,2::Int) (const x) *Foo> test2 (1.0::Float) array (1,2) [(1,1.0),(2,1.0)] *Foo> test2 True array (1,2) [(1,True),(2,True)] As we see, we indeed need to define instances of STUGood for Bool, Char, Float, Word32, etc. One might wish if the designers of the Haskell library introduced a class 'Unpackable'. In that case, we would have needed only one STUArray instance instance Unpackable e => MArray (STUArray s) e (ST s) The constraint Unpackable would have made solving your problem easier. For the sake of completeness, I'd like to mention another solution, using castSTUArray. Yet it smacks too much of dynamic typing...

1 0

Re: [Haskell-cafe] data vs newtype (was: newbie problems)
by MR K P SCHUPKE 05 Jul '04

05 Jul '04

>But you have to balance this against newtypes being neater. I meant more efficient... oh well! (data is generally neater) Keean.

1 0

Re: [Haskell-cafe] data vs newtype (was: newbie problems)
by MR K P SCHUPKE 05 Jul '04

05 Jul '04

One difference is that Constuctors for 'data' can be curries, whereas 'newtype' cannot: data X a b c = X a b c newtype X a b c = X (a,b,c) But you have to balance this against newtypes being neater. Also data can represend and abstract type: data X whereas newtype cannot, also data can represent unitary types: data Y = Y whereas newtype is limited to wrapping up void: newtype Z = Z () Keean.

1 0

Re: [Haskell-cafe] Using Product Algebraic types
by Crypt Master 05 Jul '04

05 Jul '04

------------- <sigh> I always get a bad feeling when people start to think about efficiency right from the beginning: First get your program correct and readable, then measure, and only then optimize (if at all). Programmers are notoriously bad when guessing about efficiency, which even more true for lazy functional programs. </sigh> ------------ Sorry to have produced the *sigh* factor. I asked the question only to start learning, which your answer has certainly helped me with. Maybe I can present a differnt persepctive on performance though. I have to say up front though that if I was interested in squeezing the last drop of performance out of everything I wouldnt be learning haskell as all the web sites warn you about this :-) I do beleive in clarity, readbaility, correctness, time to develop etc.., it just that performance is one of those factors. My day job is all mostly about performance (from iterative programming perspective), I make complex business applications useable from a perfromance perspective. While most people say "just buy more hardware" or make it "correct or readable" first, my experince shows this leads to a lot of wasted effort which could have been avoided with a few seconds thought. Have you ever tried telling an IT Director that his 500 000 - 1 000 000 pound equipment purchase isnt cutting it for a "simple" business application :-) Let me tell you, they can have really selective hearing when it suits them :-) In my world, getting a program "correct" includes effieincy within reason. For exmaple, a 5 minute response time for interactive process can be pushed on employees with a relativilty minial cost of a small loss in productivity. However 5 minutes as a response for customer sitting on your web site is going to cost you millions and probably put you out of business. There are dozens of senarios like this where a "correct" program is as good as no program if it doesnt perform fast enough. What you say about guessing at performance is correct. I have given lectures on performance which start off with slides which say the trick to performance tuning is: "Measure, Measure, Measure" But I have found through experience (in the iterative world) that certian patterns of bad performance are easily avoided at development time because we know from experince they are bad at runtime. Performance has 3 flavours in my mind: 1) Hard Core 2) Design (Algortihms and data representation) 3) Common sense coding The fiirst, Hard code, invovles assemlber optimizations, branch reductions using boolean algebra etc.. No one argues these are mostly not worth the effort and so these are mostly ingnored expect for very special cercumstances. The phrase "buy more hardware" applies in this case 99% of the time. At the other end of the spectrum you have design. Few people will argue that getting your design right up front is very important. Changing Algorithms or Data Representation usually invovles changes of a significance that you have wasted your time on the "incorrect" version as you are starting mostly from scratch. Admitatly this looks a lot easier in haskell than in other impertive lanaguages. The 3rd area is where I differ from most people. Common sense coding is simply not calculating or looking something up over and over in an inner loop etc... While the programs can be changed afterwards to incorporate these, a few seconds thought by the developer avoids the bottle neck in the first place. An Example of the impact of such ineffiencies is this: Recenetly I "optimized" an interactive job which was taking over 10 minutes to run. Without understanding much about it (its highly complex) I was able to bring it down to < 1 minute applying simple common sense things. I never changed or looked at the "logic" behind it. Happy user base = productive company :-) That said haskell compiler seem pretty smart from what you have shown me so far ... which is a welcome change :-) Thanks for your reponse. This is the most helpfull community I have encountered so far .. :-) _________________________________________________________________ Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail

1 0

newbie problems
by paolo veronelli 05 Jul '04

05 Jul '04

I'd like to have a simple definition of the meanings of 'type' and 'data' and maybe a clarifing example on their use. I've read the Zipper doc on he wiki ,but I can't make it work on n-ary trees,and most of all they are not any clear the performance hits on using more complex 'data' Thanks Paolino

3 2

RE: [Haskell-cafe] Using Product Algebraic types
by Crypt Master 05 Jul '04

05 Jul '04

Hi Man, your a genius :-) Thanks for the help , still dijesting it. Interestingly enough I was playing with how to use sacnl1 just before I got this message from you, but as you mentioned I was battling with "kind" errors so I never got to test my idea besides on paper. Am I correct in assuming that your definition of Popoulation is now using tuple and not product types ? If so it it better to use tuples ? In the book the craft of func programing, it shows product type examples like this: data People = Person Name Age type Name = String type Age = Int Later it shows polymoric definitions like this: data Pairs a = Pr a a You mentioned that I had applied the polymorphic type "a" to Fitness, but but in the above example of person and people they have done the exactly what I did ? Used a space to seperate elements. So I am a little confused as to why mine didnt work. Regarding the use of newtype and data I saw another thread on this and I will use that get some insights on the differences. Your "rw" took some following until I realised currying was invovled *grin* > rw (Population xs) = Population (scanl1 f xs) > where f (n, a) = (+ n) `pair` id Can I ask one question, I am not concerned with performance at this point, but what sort of overhead does a function like id have. It seems unneccesary to me ( I am not critising your solution, I am vert thankfull for your help ) in a large populations you will land up doing a fair amount of extra but simple "reductions" ( I hope thats the right word. ) just to "copy" the unkown "a". Or does it have to be a function for some reason and so you had to use "id" ? Thanks, S ----Original Message Follows---- Crypt Master, CM> I need to be able to work with a list of items whos CM> structure is onyl partially know. That is at the level CM> of this module I dont care about what rest of it is. CM> So I have this: < type Fitness = Integer < data Population a = Population [Fitness a] Well, first of all: this will not compile. You've declared Fitness to be an synonym of Integer and Integer is not a parametric data type, i.e. it has kind *. In your definition for Population, however, you apply Fitness to a type argument. This will give you a kind error. CM> Hopefully this reads Population is constructed using CM> the Population constructor and is a list who elements CM> each conists a fitness value and some other value. So, no, it does not. I guess this is what you want: > type Fitness = Integer > data Population a = Population [(Fitness, a)] > deriving (Show) Now Population constructs a Population value from a list of which the elements are pairs of a Fitness value and a value of a specified type a. CM> Since I cant do poloymorphioc types with synonyms I CM> went with the data type. Well, actually, you can: > type Population' a = [(Fitness, a)] but type synonyms have the restriction that they cannot be partially applied. Another option might be > newtype Population'' a = Population'' [(Fitness, a)] which is only slightly different from the definition above involving data. CM> My current task is to build a roulette wheel CM> distribution of the fitness value. Basically I want to CM> build and incremental summing of the fitness value so CM> that each individual is paired with its upper range CM> like so CM> CM> Population [10 x, 20 y, 30 z] CM> New Population = [10 x, 20+10 y, 30+30 z] This can be accomplished by > rw :: Population a -> Population a > rw (Population xs) = Population (scanl1 f xs) > where f (n, a) = (+ n) `pair` id where pair is the maps a pair of functions to a function on pairs: > pair :: (a -> c) -> (b -> d) -> (a, b) -> (c, d) > f `pair` g = h > where h (a, b) = (f a, g b) A little test: > main :: IO () > main = print > $ rw (Population [(10, 2), (20, 3), (30, 5)]) This prints: "Population [(10,2),(30,3),(60,5)]". HTH, Stefan _________________________________________________________________ MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. http://join.msn.com/?page=features/virus

4 5

Working debuggers?
by Jim Apple 05 Jul '04

05 Jul '04

I downloaded and compiled buddha, but it apparently does not support Control.Monad.State. I downloaded Hat, but it requires hmake. Hmake fails to build (GHC 6.2.1). Any suggestions? Jim

2 1