- Haskell-Cafe - Haskell.org

streaming, state, etc...
by Jorge Adriano 03 Nov '02

03 Nov '02

Hi, OK so I had completed my (search) algorithm implementation. And the 'last' function was something like: "until p f x0". But now I wanted all iterations, I wanted to analyze the behavior of the algorithm. What could I do? I thought about using Trace... but it didn't seem adequate, I wanted to manipulate and use that info... maybe monads... that would cluter my algorithm so bad... This feeling lasted for a few seconds, then I thought, Lazy Evaluation! "iterate p f x0" There, done :) I had an infinite list, and I'd just take as much as I wanted. *Analysis* and the *algorithm* itself were *completely separated*, yet it was using the information as soon as it was calculated - or maybe "it was being calculated only when it was needed". I could not do this kind of stuff in imperative languages. Very nice :) ------------ Problem 1: ------------ I've used that many times since then, but lately it doesn't really seem to serve my needs. What if I need to get two different kinds of data, say (list1, list2), and now I want to write them: writeFile file1 (analyze list1) writeFile file2 (analyze list2) What if you need to evaluate list2 to evaluate list1? Not good! I'm evaluating list2 and not consuming it, therefore space leak. I could alternate between one list and another, but what if at a certain point, evaluating the next elem in "list1" caused the evaluation of a few thousand elements of "list2"? So how do you usually deal with this kind of stuff? Concurrency?? ------------ Problem 2: ------------ Yes "iterate p f x0" looks good. What if function "f" is not a pure one? If my monad is a Lazy one, streaming can be used(*), if it is not, that won't work. So streaming could work with monads like State, (lazy) ST. Not with IO, or (lazy) ST. (*) do list<-myalgorithm writeFile file1 (analyze list) So, how do you usually do this kind of thing - extracting lists of info from an algorithm? J.A.

1 0

dozen
by Nuno Silva 30 Oct '02

30 Oct '02

can anyone help me how to get the dozen number? using Int example dozen 1020 the expected result is: 2 --------------------------------- Do you Yahoo!? Y! Web Hosting - Let the expert host your web site

7 14

RE: Concurrent Haskell, asynchronous exceptions and interruptibility (again)
by Simon Marlow 30 Oct '02

30 Oct '02

> For Concurrent Haskell, with respect to asynchronous > exceptions, can a > thread receive an asynchronous exception if it's evaluating > an expression > that could "potentially block on IO" when evaluated within > the "block" > function? > > Specifically, is interruptibility determined statically in > the language definition or dynamically at run time? "dynamically at runtime", according to the semantics given in our paper. GHC does actually implement this, although it implements a slightly different version of throwTo from the one described in the paper (ours blocks until the exception has been delivered). > For example, assume a thread is evaluating the following function. > > transfer :: MVar a -> IO (MVar a) > transfer from = > block $ do > to <- newEmptyMVar > x <- takeMVar from > putMVar to x > return to > > In general, since putMVar is an IO function, it can > potentially block (if > its MVar argument is already occupied with a value). However, > since "MVar > to" will obviously be vacant in this instance, the putMVar > can not block on > IO. > > Would ghc allow an asynchronous exception to be raised at the > point that "putMVar to x" is evaluated? Not unless the putMVar blocks. The proof that it never blocks depends on the behaviour of other threads though: if you have another thread doing putMVar on the same MVar, then it may block. Other threads must be "well-behaved" for it to work. > If not, then I guess transfer is exception safe. > > Would that answer scale? Could I replace the "putMVar to x" with an > arbitrarily large/complex IO function that I might write that > is guaranteed > (by me at least) to be non-blocking and still be sure that an > exception > would not be delivered during evaluation of that function? Yes. Cheers, Simon

2 1

Last generator in do {...}
by George Kosmidis 30 Oct '02

30 Oct '02

I am sure there are a billion errors in this. This is the first one: Line:17 - Last generator in do {...} must be an expression Can Anyone point the errors and maybe tell me if there is a possibility for this to work? import IO import System import List import Maybe import Char import Numeric type Name=String type Room=Int type Dr=String type PatientTup=(Name,(Room,Dr)) type PatientList=[PatientTup] main=do userText<-getText ----------------------------------------------------------------------------------- ________getText::IO String ________getText=do nc<-getText ___________________return (:nc) ----------------------------------------------------------------------------------- ________PatientList::[(String,(Int,String))] ________PatientList=[("Robson, Brian",(2,"MJH")), _____________________("Hitchin, Linda",(1,"ILR")), _____________________("Reeve, Paul", (2,"ILR"))] ----------------------------------------------------------------------------------- ________getWards::Int->Int ________getWards PatientList=[Room | (Name,(Room,Dr)) <- PatientList, Room==getText] _________________do putSpc (length Room) _________________return(RoomLength) ----------------------------------------------------------------------------------- ________getPatient::String->String ________getPatient PatientList=[Name,Room,Dr | (Name,(Room,Dr)) <- PatientList, Name==getText] ___________________do putChar (Name) ______________________putChar 'is in ward' ______________________putChar (Room) ______________________putChar 'and is treated by' ______________________putChar (Dr) ______________________return (wl) ----------------------------------------------------------------------------------- ________printFreq::WordList->IO() ________printFreq wl ----------------------------------------------------------------------------------- ________NumberInWard::printFreq(getWards(getText)) ----------------------------------------------------------------------------------- ________PatientInfo::printFreq(getPatient(getText)) ----------------------------------------------------------------------------------- ________setABC::ReceptionReport -> ReceptionReport ________setABC [ ]___=[ ] ________setABC(wn:ws)=setABC[(w,wc) | (w,wc)<-ws, not(isBigger(w,wc)wn)] _________++[wn]++setABC[(w,wc) | (w,wc) <- ws, isBigger (w,wc) wn] __________________where ___________________isBigger (w1,wc1) (w2,wc2) ____________________| ord(head(w1))-ord(head(w2))>0=True ____________________| ord(head(w1))-ord(head(w2))<0=False ____________________|length w1>1&&length w2>1 _____________________=isBigger(tail(w1),wc1) (tail(w2),wc2) ____________________|length w1>1&&length w2==1=True ____________________|otherwise=false ----------------------------------------------------------------------------------- ________ReseptionList::String->String ________ReseptionList PatientList=[Name,Room | (Name,(Room,Dr)) <- PatientList] ______________________do sequence (map ReceptionReport wl) __________________________________where ______________________________________ReceptionReport::setABC((Name,Room))->IO() ______________________________________ReceptionReport(w,wc)=do putStr w _______________________________________________________________putStr (show w) _______________________________________________________________putChar 'in' _______________________________________________________________putStr (show wc) _______________________________________________________________putChar '\n' _______________________________________________________________return wl ----------------------------------------------------------------------------------- ________setNum::DoctorsReport -> DoctorsReport ________setNum [ ] = [ ] ________setNum((wn,wcn):DoctorsReport[(w,wc)|(w,wc)<-ws, _________________________ws<=wcn++[(wn,wcn)]DoctorsReport[(w,wc)|(w,wc)<-ws,wc>wcn] ----------------------------------------------------------------------------------- ________DoctorsList::String->String ________DoctorsList PatientList=[Name,Room | (Name,(Room,Dr)) <- PatientList, Dr==getText] ____________________do sequence (map DoctorsReport wl) ________________________________where ____________________________________DoctorsReport::setNum((Name,Room))->IO() ____________________________________DoctorsReport(w,wc)=do putStr w ___________________________________________________________putStr (show w) ___________________________________________________________putChar 'in' ___________________________________________________________putStr (show wc) ___________________________________________________________putChar '\n' _______________________________________________________________return wl -----------------------------------------------------------------------------------

4 3

Concurrent Haskell, asynchronous exceptions and interruptibility (again)
by Patrick Bosworth 30 Oct '02

30 Oct '02

For Concurrent Haskell, with respect to asynchronous exceptions, can a thread receive an asynchronous exception if it's evaluating an expression that could "potentially block on IO" when evaluated within the "block" function? Specifically, is interruptibility determined statically in the language definition or dynamically at run time? For example, assume a thread is evaluating the following function. transfer :: MVar a -> IO (MVar a) transfer from = block $ do to <- newEmptyMVar x <- takeMVar from putMVar to x return to In general, since putMVar is an IO function, it can potentially block (if its MVar argument is already occupied with a value). However, since "MVar to" will obviously be vacant in this instance, the putMVar can not block on IO. Would ghc allow an asynchronous exception to be raised at the point that "putMVar to x" is evaluated? If not, then I guess transfer is exception safe. Would that answer scale? Could I replace the "putMVar to x" with an arbitrarily large/complex IO function that I might write that is guaranteed (by me at least) to be non-blocking and still be sure that an exception would not be delivered during evaluation of that function? Cheers, Patrick. _________________________________________________________________ Internet access plans that fit your lifestyle -- join MSN. http://resourcecenter.msn.com/access/plans/default.asp

1 0

RE: Odd Performance
by Garner, Robin 30 Oct '02

30 Oct '02

You may also like to compare this definition. > import List > > primes = unfoldr sieve [2..] > sieve (x:xs) = Just (x,filter (x `notDivisor`) xs) > x `notDivisor` y = y `mod` x /= 0 Slower, but (IMO) cuter. Cheers, -----Original Message----- From: Tim Otten [mailto:tim@cap.american.edu] Sent: Wednesday, 23 October 2002 15:10 To: haskell-cafe(a)haskell.org Cc: scasey(a)cap.american.edu Subject: Re: Odd Performance Tom Pledger writes: > Probably. Try replacing this > (\z -> z <= (intsqrt x)) > with this > (\z -> z^2 <= x) Yes! This is significantly nicer. Taking 4000 primes, this is about twice as fast as the original (loose) algorithm, and it appears that it gets better as n grows. (Call this version #3). > or moving the O(sqrt(n)) step[1] into a let expression This does help -- the implementation with this adjustment seems to hover around 1.1 times the speed of the loose algorithm. (Call this version #4) > Only if the predicate function (the p in takeWhile p xs) is > significantly more expensive than a constant-cost piece of arithmetic > and pattern-matching. This makes sense and explains the results above: squaring z is easier than square-rooting x. In fact, the way intsqrt is written, #4's takeWhile indirectly tests (z*z > x) once for each [z | 1<=z<=sqrt(x)]. #3's takeWhile expression will only evaluate (z^2 < x) once for each [ z | z <- primes, z<=sqrt(x) ]. Moreover, #4's takeWhile will do additional tests (z <= sqrt) for each [z | z <- primes, z <= sqrt(x)]. In retrospect, the intsqrt-approach seems rather silly. :) Thank you, Tim _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Active Haskell development and libraries
by Mark Carroll 29 Oct '02

29 Oct '02

The Libraries and Tools For Haskell page has quite a list of things, but a few broken links, and links to very many projects that seem to have started off as interesting research projects that, as the page itself says, were more proofs of concept and are no longer maintained. We can't help but be slightly worried by this when we're thinking about what language(s) try out for production code, given that when we look at things like Objective Caml there are nice things like the Caml Humps at http://caml.inria.fr/humps/ that shows a lot of recent work, and even a new O'Caml O'Reilly book coming out (well, mostly a translation of the French book, I think). The Haskell Communities and Activities Report is a great start for showing some recent Haskell activity, and the Libraries and Tools page at least separates out the unsupported GUI-libraries, and there is certainly some good stuff for Haskell - for instance, we like HUnit and Haddock, and I'm thinking that Parsec might come in handy. Still, at our end we're wanting to stop and think: I'm looking forward to reading the next communities and activities report. In particular, I want to reassure myself that there is a lot of useful actively-maintained stuff we can use, and more coming. Although I'm very happy that the libraries and tools page exists at all, I wonder if there's any possibility of the Haskell stuff being listed in a nice table too, including information as when the latest release was and with what versions of which Haskell compilers each thing was last found to be working. Maybe there is some existing free software that can make such a site easily maintained? Obviously I'm not demanding that all you guys write lots of extra libraries and tools for Haskell for free for me. (-: (Of course, stuff is already being written and released by posters here.) Partly I'm suggesting that, to avoid putting people off using Haskell, maybe the active and currently-working things should be highlighted and easy to find relative to the other things, right on the libraries and tools page, given that currently there are a few broken links and projects that are practically stalled, and partly I'm wanting to see what other people think about where Haskell is now relative to things like O'Caml from the point of view of commercial instead of research users. At least, am I right in thinking that more industrial Haskell users are wanted, and that it's not meant to be solely an interesting piece of research? To take an example, right now we're not exactly sure what the recommended way is to have Java code call our Haskell functions, for instance. (Background: I have reasonable influence in a tiny company and would like us to use Haskell to create some of our core products - I'm a big believer that use of rich, strong, static typing and a functional style will bring us benefits - at least, I'd like to exploit the fruits of programming language research in recent decades. However, although I'm fairly optimistic about Haskell's future, I've jumped the wrong way before, and I'm wanting to make sure that the momentum in the Haskell community is in the right direction. We would be very happy to contribute stuff ourselves if we needed to to bring things the final few inches toward what we need, as we're generally opensource fans, but we're too small to fund a whole lot of general stuff right now.) Apologies if this seems to be a reiteration of previous vocal worrying I've been doing. (-: Really, I'm just hoping that some changes on the libraries and tools page can help users of Haskell and encourage more people to join the community - especially given that much of the legwork is already being done by Claus anyway - and to help us be sure that Haskell and its associated things is, strategically, a good technology for us to rely on, from the point of view of there being a vibrant and growing repository of useful libraries. -- Mark

2 1

RE: Interruptibility and thread safeness with readMVar
by Simon Marlow 28 Oct '02

28 Oct '02

> How does the ghc run-time system determine if an operation is > interruptible > when within "block" function scope? Explanations I've read in various > papers/web pages state that an operation is interruptible, > even within a the > scope of the "block" function, if that operation can potentially block > waiting for input/output. That's correct. > Take the readMVar function. In my implementation > of ghc, readMVar is defined as follows. > > readMVar :: MVar a -> IO a > readMVar m = > block $ do > a <- takeMVar m > putMVar m a > return a > > Since, by the above definition of interruptible, both > takeMVar and putMVar > are both interruptible operations, isn't there a possibility that, on > receipt of an exception while blocked on the "putMVar m a" > operation, "MVar > m" would be left in an inconsistent state (i.e. empty)? Am I right in > thinking that readMVar should only ever be used when no other > thread can > potentially access "MVar m"? Or have I completely missed the point? Yes, that's right. The safetey of readMVar depends on there being no malicious threads doing putMVar without first doing takeMVar (in fact this condition extends to many MVar operations). > My second question concerns readMVar directly. Is this > function intended to > be an atomic operation in the context of multiple threads > accessing the > "MVar m" parameter (i.e. thread safe)? Presumably, if a > context switch takes > place after takeMVar but before putMVar, there is a > possibility that another > thread will successfully evaluate putMVar on "MVar m", > inserting a different > value. Is this intended? I suppose it's necessary to resort > to some kind of > cunning ploy of using more MVars/threads to control access to > MVar m if we > wan't to guarantee readMVar's thread safeness? If so, does > anyone have such an implementation? The assumption is that there are no threads attempting to do putMVar without first doing takeMVar (the same condition as above). > Both of these questions are a result of trying to implement a > function that > will atomically (in the presence of both other threads and > asynchronous > exceptions) transfer the contents of one MVar to another (or > leave both > MVars in their original states of the operation fails). In order to do this, you'll need to be clear about what another thread in the system is allowed to do with the MVars involved. This will affect whether you need extra locking (more MVars) or not. Also, doing atomic operations on two MVars simultaneously is tricky, because there is a risk of deadlock with another thread doing the same operation on the same MVars but in the opposite order. Usually some ordering is applied to the MVars to avoid this problem. Cheers, Simon

1 0

RE: autocompletion mode for ghci?
by Simon Marlow 28 Oct '02

28 Oct '02

> is there any mode for the ghci, which provides autocompletion > like e.g. the bash? GHCi on Unix provides autocomplete through the readline library (the same library used by bash) albeit only for filenames and directories. We don't compile with readline support on Windows (I'm not sure why). If you want completion of function names, type names, etc. then the answer is that we haven't implemented it, but it would be an interesting project. Cheers, Simon

1 0

Interruptibility and thread safeness with readMVar
by Patrick Bosworth 28 Oct '02

28 Oct '02

How does the ghc run-time system determine if an operation is interruptible when within "block" function scope? Explanations I've read in various papers/web pages state that an operation is interruptible, even within a the scope of the "block" function, if that operation can potentially block waiting for input/output. Take the readMVar function. In my implementation of ghc, readMVar is defined as follows. readMVar :: MVar a -> IO a readMVar m = block $ do a <- takeMVar m putMVar m a return a Since, by the above definition of interruptible, both takeMVar and putMVar are both interruptible operations, isn't there a possibility that, on receipt of an exception while blocked on the "putMVar m a" operation, "MVar m" would be left in an inconsistent state (i.e. empty)? Am I right in thinking that readMVar should only ever be used when no other thread can potentially access "MVar m"? Or have I completely missed the point? My second question concerns readMVar directly. Is this function intended to be an atomic operation in the context of multiple threads accessing the "MVar m" parameter (i.e. thread safe)? Presumably, if a context switch takes place after takeMVar but before putMVar, there is a possibility that another thread will successfully evaluate putMVar on "MVar m", inserting a different value. Is this intended? I suppose it's necessary to resort to some kind of cunning ploy of using more MVars/threads to control access to MVar m if we wan't to guarantee readMVar's thread safeness? If so, does anyone have such an implementation? Both of these questions are a result of trying to implement a function that will atomically (in the presence of both other threads and asynchronous exceptions) transfer the contents of one MVar to another (or leave both MVars in their original states of the operation fails). ********************************************************************** This message is intended only for the stated addressee(s) and may be confidential. Access to this email by anyone else is unauthorised. Any opinions expressed in this email do not necessarily reflect the opinions of royalblue. Any unauthorised disclosure, use of dissemination, either whole or part is prohibited. If you are not the intended recipient of this message, please notify the sender immediately. **********************************************************************

1 0