July 2007 - Haskell-Cafe

Conditional compilation of Setup.hs
by Bayley, Alistair 31 Jul '07

31 Jul '07

I'd like to add a #ifdef to Takusen's Setup.hs, so that we can have a single source file that will compile with ghc-6.6 and ghc-6.6.1. With ghc-6.6 and Cabal-1.1.6.1 we use splitFileName and joinPaths from Distribution.Compat.FilePath. With ghc-6.6.1 (which includes Cabal-1.1.6.2) these have been moved to System.FilePath. I'd like to do something like the following: #ifdef __CABAL_VERSION__ > 117 import System.FilePath (splitFileName, combine) joinPaths = combine #else import Distribution.Compat.FilePath (splitFileName, joinPaths) #endif Is something like this possible with Cabal? It's either that, or make Takusen's install depend on filepath. I'm not sure which is the least desirable, but I'm open to suggestions. To be fair, we already require our ghc-6.6 users to upgrade Cabal from 1.1.6 to 1.1.6.1, so making them install filepath instead perhaps isn't so bad, and is no more effort. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

3 3

Constraing satisfaction
by drop669＠gmail.com 30 Jul '07

30 Jul '07

Hi. I have a set of problems in the field of constaint satisfaction and I'm looking for a tool for this. In simplest form, these task are like Sudoku puzzle solver, school schedule creator, etc. Prolog language comes to mind at first. But if to choose Haskell? Can be these tasks defined in Haskell with the same elegance as in Prolog, or I'll need some additional framework or library?

3 3

Latest AngloHaskell news and a request
by Philippa Cowderoy 30 Jul '07

30 Jul '07

Two pieces of news regarding AngloHaskell: 1) We've been offered WiFi access at Microsoft Research for any attendees who want it. We'll need a name, email address and company/institution affiliation where appropriate - see wiki for details. 2) We're being given lunch on Friday! Finally, a request: We're a little short on crashspace, and I suspect this is affecting who's able to show up. Could people who can only make it with crashspace (or who can only make one day without) add their names on the wiki? Is there anyone in the area able to offer people at least some space on a floor? Last year we had offers early, and I think this helped get plans moving. For those who could use the reminder, the wiki page is at http://www.haskell.org/haskellwiki/AngloHaskell Many thanks, and I hope to see you there! -- flippa(a)flippac.org Society does not owe people jobs. Society owes it to itself to find people jobs.

1 0

GSL special functions (Re: [Haskell] math library for Haskell)
by Alberto Ruiz 30 Jul '07

30 Jul '07

(moved to Haskell-cafe) On Wednesday 25 July 2007 12:52, Gregory Wright wrote: > On Jul 25, 2007, at 6:39 AM, Chris Kuklewicz wrote: > > Alberto Ruiz wrote: > >> I have included a binding to gsl_sf_gamma in the darcs repo of > >> GSLHaskell: > >> http://dis.um.es/~alberto/GSLHaskell/doc/GSL-Special.html#v%3Agamma > >> I will try to upload to hackage a recent version of the library in > >> a few days. > >> Alberto > > > > It occurs to me that generating the binding for all the GSL > > "Special" functions by hand may be labor intensive. Would it be > > reasonable to have a (perhaps customized) tool generate the > > wrapping code? Absolutely! I am busy working on my applications and rewriting the internal support for the linear algebra wrappers, so I usually add new functions only when I need them for my own work. But a GSL library without the simplest functions is not very useful... > I have some functions that make wrapping the GSL special functions > much simpler. I've used them > to wrap all of the Airy and Bessel functions. The process could be > automated, but there are a few > more cases than convenient. (For example, the computationally > expensive functions take an additional > argument specifying how much precision is desired.) It wouldn't be > too much work to automate the > most common cases (double arg, double return and double arg, error > struct return); perhaps doing the > remainder by hand is reasonable. That's also right, so I have written a (very crude and ad-hoc) tool to generate wrappers for the most common cases. The results look promising: http://perception.inf.um.es/~aruiz/darcs/HSSL/doc/html/GSL-Special.html They are available in the new version of the library. In principle it is already working but needs more testing. I plan to upload a version to hackage (the repo can be found in the GSLHaskell web page). A problem with automatic wrappers is that we should still add a small piece of useful haddock documentation and appropriate tests for each function. > I also have bindings for all of the ODE integration routines and all > of the numerical differentiation > routines. All are low level, just exposing the underlying GSL > routines without any "convenience wrapper". > I can make them available if anyone is interested. > > Best Wishes, > Greg Good! I'd like to include a high level interface to the ODE routines. Perhaps it could be based on your bindings... Best regards, Alberto

1 0

Questions about threads
by John Goerzen 30 Jul '07

30 Jul '07

Hi everyone, I have been confused by some things about threads for a long time. I'm hoping someone out there can help clear this up. I'll clean up and document on the wiki if we get conclusive answers. So it seems there are four scenarios for firing off threads: A) Threaded RTS, forkIO B) Threaded RTS, forkOS C) Non-threaded RTS, forkIO D) Non-threaded RTS, forkOS So the questions, for each of the four models, are: 1) What is the impact of firing off a thread to execute a pure (non-IO) computation under each model? Will multiple pure computations be allowed to run in parallel, or will only one run at a time? (While the computation may be outside the IO monad, of course at the end it will have to use IO to communicate the result back.) 2) What is the impact of IO under each model? Will GHC internally use select/poll/whatever? Or will each thread get a dedicated OS thread that uses synchronous I/O? 3) When signals are received, which thread receives them? 4) When forkProcess is executed, which thread(s) are duplicated to the forked process? 5) What does an FFI import "safe" mean under each model? 6) What does an FFI import "unsafe" mean under each model? 7) What is the expected future level of support for each model? This is of significant concern to me, as it appears that the threaded RTS is only supported on an extremely limited set of architectures (most programs won't even link on Debian's autobuilders if I use -threaded). Also I have heard comments that the non-threaded RTS may be dropped in the future. 8) What is the expected level of support for STM in combination with each threaded model? 9) How does par mix with each threaded model? Is it equivolent to forkOS or forkIO? Thanks, -- John

4 3

MAPI provider?
by John Goerzen 30 Jul '07

30 Jul '07

Hi, I apologize if this is off-topic or stupid. I'm not very familiar (at all) with Windows programming... I have a Haskell program that I want to get called when someone sends a message on Windows. This sending a message will happen from various programs that call MAPI. It doesn't seem very easy to plug into MAPI from Haskell as a MAPI *provider*, though if anybody has examples, that'd be great. Does anybody know of an MAPI provider that receives send requests, writes the data to a file, and then just invokes a program passing the file as a parameter? That would let me do all I need to plug in. Thanks, -- John

1 0

Re: [Haskell] View patterns in GHC: Request for feedback
by Dan Licata 30 Jul '07

30 Jul '07

[I think we should move the rest of this thread to haskell-cafe, since it's getting long. Note that there have already been some responses on both lists.] Hi Claus, On Jul25, Claus Reinke wrote: > >I think that the signature > > > >> type Typ > >> > >> unit :: Typ -> Maybe () > >> arrow :: Type -> Maybe (Typ,Typ) > > > >is *wrong* if what you really mean is > > > >> type Typ > >> > >> data TypView = Unit | Arrow Typ Typ > >> view :: Typ -> TypView > > different =/= wrong !-) No, of course not. All I meant to say is that sometimes you want a total view, and that a total view should be given a type that says as much. The latter says this better than the former. On the other hand, there are lots of circumstances in which you want a partial view, and I think the (... -> Maybe _) types for those are perfectly appropriate. > >That is, if what you mean is that every Typ is either Unit or an Arrow > >*and nothing else* then the latter signature should be preferred, as it > >makes this fact explicit in the type system. > > but that is not what you're saying there at all! you're saying that -within > view 'view' of Typ- Typ is mapped to either Unit or Arrow, if the mapping > is successfull. there can be other views of Typ, Right, but the only issue here is whether this particular view function is total or not. > and the types do not guarantee that 'view' itself is exhaustive over > Typ (there can be variants of Typ that 'view' fails to map to > TypView). > in the abstract deconstructor variant, this partiality is explicit in the > types, > in the concrete view type variant, it is hidden from the types, implicit in > the implementation of 'view'. But by this reasoning, every expression you write should have a Maybe type, since there's always the possibility of match failure or non-termination. In Haskell, these effects are always implicit in a type, so there's no need to add extra summands to account for them. If you think about the *values* of the returned type, then (1 + Typ * Typ) is what you want, not ((1 + 1) + (1 + Typ * Typ)). > btw, it might be useful to permit association of abstract types > with abstract deconstructors, so that an extended abstract type > (export) declaration somewhat like > > type Typ as unit -> () | arrow -> (Typ,Typ) > > tells us (and the compiler) that the abstract patterns in the size > function are exhaustive (or at least as exhaustive as clients of > the abstract type Typ are supposed to be). the proof obligation > would be on the exporter of the abstract type, and any pattern > match failures relating to this should be reported as view failures. > > doing so would declare a virtual view type, similar to the concrete > view types used in other examples, so there might be several 'as' > clauses for a single abstract type, declaring separate sets of > exhaustive abstract deconstructors. Setting aside the "transparent ordinary patterns" feature, I think this is exactly what you get above: - the data declaration for TypView corresponds to this "as" declaration - the view function of type Typ -> TypView can be analyzed for exhaustiveness using GHC's exhaustiveness checker - a run-time match failure of view will be reported as such So I don't think I understand what you're going for here. Could you explain? -Dan

3 5

Strange behavior of executeFile
by Krzysztof Kościuszkiewicz 30 Jul '07

30 Jul '07

Fellow Haskellers, I wrote a small script that intercepts arguments and exec's the pstops program. The intention was to center and scale pages in a document before processing it by psnup. So far so good, I've ended up with something like: > runPstops :: [Flag] -> IO () > runPstops flags = > do let args = mkArgs flags > when (isVerbose flags) $ do > hPutStrLn stderr $ "pstops " ++ unwords (map show args) > executeFile "pstops" True args Nothing > main = do (opts, _) <- getOptions =<< getArgs > runPstops opts This works for files, but "randomly" fails when stdin is connected to a pipe (pstops complains that it can't seek input). I've tested "raw" pstops with pipes, files and /dev/null and it never fails, so I guess there is something wrong with my code. Can anyone enlighten me in this matter? :) Regards, -- Krzysztof Kościuszkiewicz Skype: dr.vee, Gadu: 111851, Jabber: kokr(a)jabberpl.org Phone IRL: +353851383329, Phone PL: +48783303040 "Simplicity is the ultimate sophistication" -- Leonardo da Vinci

4 4

Space usage and CSE in Haskell
by Melissa O'Neill 30 Jul '07

30 Jul '07

When advocating functional languages like Haskell, one of the claims I've tended to make is that referential transparency allows the language to be much more aggressive about things like common subexpression elimination (CSE) than traditional imperative languages (which need to worry about preserving proper side-effect sequencing). But a recent example has left me thinking that maybe I've gone too far in my claims. First, lets consider a simple consumer program, such as: > printEveryNth c l n = do print (c', x) > printEveryNth c' xs n > where c' = c+n > x:xs = drop (n-1) l Note that we can pass this function an infinite list, such as [1..], and it won't retain the whole list as it prints out every nth element of the list. Now let's consider two possible infinite lists we might pass to our consumer function. We'll use a list of primes (inspired by the recent discussion of primes, but you can ignore the exact function being computed). Here's the first version: > primes = 2 : [x | x <- [3,5..], all (\p -> x `mod` p > 0) > (factorsToTry x)] > where > factorsToTry x = takeWhile (\p -> p*p <= x) primes As you might expect, at the point where we print the nth prime from our infinite list, we will be retaining a list that requires O(n) space. But this simple modification allows us to use only O(sqrt(n)) space at the point we print the nth prime: > primes = > 2 : [x | x <- [3,5..], all (\p -> x `mod` p > 0) (factorsToTry x)] > where > slowerPrimes = > 2 : [x | x <- [3,5..], all (\p -> x `mod` p > 0) > (factorsToTry x)] > factorsToTry x = takeWhile (\p -> p*p <= x) slowerPrimes Notice the gigantic common subexpression -- both primes and slowerPrimes define exactly the same list, but at the point where we're examining the nth element of primes, we'll only have advanced to the sqrt(n)th element of slowerPrimes. Clearly, "simplifying" the second version of primes into the first by performing CSE actually makes the code much *worse*. This "CSE- makes-it-worse" property strikes me as "interesting". So, is it "interesting"...? Has anyone worked on characterizing CSE space leaks (and avoiding CSE in those cases)? FWIW, it looks like others have run into the same problem, since bug #947 in GHC (from October 2006) seems to be along similar lines. Melissa. P.S. These issues do make massive difference in practice. There is a huge difference between taking O(n) and O(sqrt(n)) space -- the difference between a couple of megabytes for the heap and tens or hundreds of megabytes.

7 12

Using GADTs
by Matthew Pocock 29 Jul '07

29 Jul '07

Hi, I'm trying to get to grips with GADTs, and my first attempt was to convert a simple logic language into negative normal form, while attempting to push the knowledge about what consitutes negative normal form into the types. My code is below. I'm not entirely happy with it, and would appreciate any feedback. The rules are that in nnf, only named concepts, the concept Top and the concept Bottom can be negated. So, I've added three NNFNegation_* constructors capturing these legal cases. Is there a way to use one constructor, that is allowed to 'range over' these three cases and none of the others? I've ended up producing two data types, one for the general form and one for the nnf. Actually, the constraint on what constitutes nnf is fairly obvious - no complex terms are negated. Is there a way to use just the one data type but to describe two levels of constraints - one for the general case, and one for the nnf case? Or is the whole point that you capture each set of constraints in a different data type? Thanks, Matthe data Named data Equal data Conjunction data Disjunction data Negation data Existential data Universal data Top data Bottom data Concept t where CNamed :: String -> Concept Named CEqual :: Concept a -> Concept b -> Concept Equal CConjunction :: Concept a -> Concept b -> Concept Conjunction CDisjunction :: Concept a -> Concept b -> Concept Disjunction CNegation :: Concept a -> Concept Negation CExistential :: Role Named -> Concept Existential CUniversal :: Role Named -> Concept Universal CTop :: Concept Top CBottom :: Concept Bottom data NNFConcept t where NNFCNamed :: String -> NNFConcept Named NNFCEqual :: NNFConcept a -> NNFConcept b -> NNFConcept Equal NNFCConjunction :: NNFConcept a -> NNFConcept b -> NNFConcept Conjunction NNFCDisjunction :: NNFConcept a -> NNFConcept b -> NNFConcept Disjunction NNFCExistential :: Role Named -> NNFConcept Existential NNFCUniversal :: Role Named -> NNFConcept Universal NNFCTop :: NNFConcept Top NNFCBottom :: NNFConcept Bottom NNFCNegation_N :: NNFConcept Named -> Concept Negation NNFCNegation_T :: NNFConcept Top -> Concept Negation NNFCNegation_B :: NNFConcept Bottom -> Concept Negation data Role t where RNamed :: String -> RNamed Named -- terms not prefixed with a negation are already in nnf nnf :: Concept t -> NNFConcept u nnf CNamed name = NNFCNamed name nnf CEqual lhs rhs = NNFConcept (nnf lhs) (nnf rhs) nnf CConjunction lhs rhs = NNFCConjunction (nnf lhs) (nnf rhs) nnf CDijunction lhs rhs = NNFCDisjunction (nnf lhs) (nnf rhs) nnf CExistential r c = NNFCExistential r (nnf c) nnf CUniversal r c = NNFCUniversal r (nnf c) -- if negated, we must look at the term and then do The Right Thing(tm) nnf CNegation (CNamed name) = NNFCNegation_N NNFCNamed name nnf CNegation (CEqual lhs rhs) = NNFCEqual (nnf $ CNegation lhs) (nnf $ CNegation rhs) nnf CNegation (CConjunction lhs rhs) = NNFCDisjunction (nnf $ CNegation lhs) (nnf $ CNegation rhs) nnf CNegation (CDisjunction lhs rhs) = NNFCConjunction (nnf $ CNegation lhs) (nnf $ CNegation rhs) nnf CNegation (CNegation c) = nnf c nnf CNegation (CExistential r c) = NNFCUniversal r (nnf $ CNegation c) nnf CNegation (CUniveral r c) = NNFCExistential r (nnf $ CNegation c) nnf CNegation CTop = NNFCNegation_T NNFCTop nnf CNegation CBottom = NNFCNegation_B NNFCBottom

2 2