June 2004 - Haskell - Haskell.org

Re: [Haskell] Help in understanding a type error involving forall and class constraints
by MR K P SCHUPKE 29 Jun '04

29 Jun '04

Try this: distString :: String -> String -> Int distString s0 s1 = let a = runST (difST s0 s1) in a!(1,1) difST :: MArray (STUArray s) Int (ST s) => String -> String -> ST s (UArray (Int,Int) Int) difST s0 s1 = do b@(_,br) <- return $ (\x1 y1 -> ((0,0),(x1,y1))) (length s0) (length s1) d <- newArray b 0 :: ST s (STUArray s (Int,Int) Int) mdiff d s0 s1 -- readArray d br unsafeFreeze d Keean.

2 1

Re: [Haskell] Help in understanding a type error involving forall and class constraints
by MR K P SCHUPKE 29 Jun '04

29 Jun '04

Erm, something I remember about needing MArrays... Here's something which does the same thing (cooks and MArray then freezes it - also using STUArray... The neat thing is MArray is a class, so you can swap between STUArray and STArray implementations without changing code. This is the classic dynamic programming version of string difference: distString :: String -> String -> Int distString s0 s1 = runST (difST s0 s1) difST :: MArray (STUArray s) Int (ST s) => String -> String -> ST s Int difST s0 s1 = do b@(_,br) <- return $ (\x1 y1 -> ((0,0),(x1,y1))) (length s0) (length s1) d <- newArray b 0 :: ST s (STUArray s (Int,Int) Int) mdiff d s0 s1 readArray d br mMin :: Int -> Int -> Int -> Int mMin i j k = min (min i j) k costDelete :: Char -> Int costDelete _ = 1 costInsert :: Char -> Int costInsert _ = 1 costReplace :: Char -> Char -> Int costReplace _ _ = 1 mdiff :: MArray a Int m => a (Int,Int) Int -> String -> String -> m () mdiff (d :: a e i) s0 s1 = do writeArray d (0,0) 0 foreach 1 s0 $ \x a -> do dx <- readArray d (x-1,0) writeArray d (x,0) (dx+costDelete a) foreach 1 s1 $ \y b -> do dy <- readArray d (0,y-1) writeArray d (0,y) (dy+costInsert b) foreach 1 s0 $ \x a -> do foreach 1 s1 $ \y b -> do dx <- readArray d (x-1,y) dy <- readArray d (x,y-1) dxy <- readArray d (x-1,y-1) writeArray d (x,y) $ mMin (dx+costDelete a) (dy+costInsert b) (if a==b then dxy else dxy+costReplace a b) where foreach :: MArray a Int m => Int -> String -> (Int -> Char -> m ()) -> m () foreach _ [] _ = return () foreach i (c0:cs) f = do f i c0 foreach (i+1) cs f ------------------------------------ Keean.

2 1

Help in understanding a type error involving forall and class constraints
by Duncan Coutts 29 Jun '04

29 Jun '04

Here's a small bit of code that involves some fairly hairy class overloadings (ghc's mutable unboxed array classes) The code builds an array in the ST monad by creating a mutable array then assigning to each element and finally freezing the array and returning an immutable array. Firstly the bit that does most of the work (in the ST monad). We have a MArray class constraint because we're working generically on any mutable unboxed array. Its not completely generic however since we know we're working in the ST monad with unboxed ST arrays 'STUArray'. buildUArray' :: (Ix i, MArray (STUArray s) a (ST s)) => (i,i) -> (i -> a) -> ST s (STUArray s i a) buildUArray' bounds f = do arr <- newArray_ bounds mapM_ (\i -> writeArray arr i (f i)) (range bounds) return arr Now the wrapper which freezes the mutable array and gives us back an immutable array (still in the ST monad). We gain an extra IArray class constraint. buildUArray :: (MArray (STUArray s) a (ST s), Ix i, IArray UArray a) => (i, i) -> (i -> a) -> ST s (UArray i a) buildUArray bounds f = do arr <- buildUArray' bounds f unsafeFreeze arr This all typechecks fine. Now lastly we want to run this state thread monad to get the resultant 'UArray i a' foo :: (MArray (STUArray s) a (ST s), Ix i, IArray UArray a) => (i, i) -> (i -> a) -> UArray i a foo bounds f = runST (buildUArray bounds f) At first this seems like it ought to be the right type (it does discard the 's' type), but ghc complains: No instance for (MArray (STUArray s) a (ST s)) arising from use of `buildUArray' at BuildArray.hs:25:22-32 Probable fix: Add (MArray (STUArray s) a (ST s)) to the expected type of an expression Or add an instance declaration for (MArray (STUArray s) a (ST s)) In the first argument of `runST', namely `(buildUArray bounds f)' In the definition of `foo': foo bounds f = runST (buildUArray bounds f) I get the same error if I leave off the type signature for 'foo'. The error message suggests I add a class constraint that I've already added. I suspect there's a name clash and the 's' it means is not the same as the 's' that I've already got. Anyone have an idea what's wrong? My guess is that it's related to the nested forall type of runST. We need to express a class constraint on a type that is universally quantified but that doesn't escape to the top level of the functions type. If this is the case, it doesn't do any good to add the 'MArray (STUArray s) a (ST s)' constraint because 's' does not exist at this level of type scope (it just introduces a shadowing). So how would I write a constraint that involves 's'? Duncan Ps. similar code that uses normal (not unboxed) arrays works fine, but is has less complicated class constraints: buildArray :: Ix i => (i,i) -> (i -> a) -> Array i a buildArray bounds f = runST (do arr <- buildArray' bounds f unsafeFreeze arr) where buildArray' :: Ix i => (i,i) -> (i -> a) -> ST s (STArray s i a) buildArray' bounds f = do arr <- newArray_ bounds mapM_ (\i -> writeArray arr i (f i)) (range bounds) return arr

1 0

Announcement: Summer School on Memory Management
by kh＠dcs.st-and.ac.uk 29 Jun '04

29 Jun '04

[Posted on behalf of Richard Jones, the Summer School Organiser. Kevin] The 2004 UK Memory Management Network will hold a Summer School on Garbage Collection and Memory Management on 20-21 July at the University of Kent, Canterbury, UK (South-East England -- close to the EuroStar route from the continent, change at Ashford International, then 20 mins. by train; or travel direct by normal train from London). Full details including the programme are at: http://www.mm-net.org.uk/school There are lots of good speakers including Eliot Moss, Hans Boehm, David Bacon and Emery Berger. The registration fee is pounds 130 before July 9th; pounds 156 thereafter, and you can register online. Best Wishes, Kevin

1 0

Reading a directory tree
by Tom Hofte 29 Jun '04

29 Jun '04

Hi, I'm looking for a way to iteratively read all the files in a directory and its subdirectories, given the filepath of the top-level dir. For example, I want to find a file, corresponding to a given filename, in a directory and its subdirectories. Is there a way to implement this in Haskell? Kind regards, Tom Hofte

9 11

RE: [Haskell] randomgen for foreign random functions
by Simon Peyton-Jones 28 Jun '04

28 Jun '04

| Say I have a foreign function: | | foreign import ccall "statistical_c.h gengam" c_gengam :: CDouble -> CDouble -> IO CDouble | | that returns a random value parameterized by the two CDoubles. clearly | this must happen in IO since the return value will be different each time, | and some global state stuff is getting modified on the C side to | facilitate future random # generation. | | However, I would like to wrap this into an essentially pure function, ala | the Random class. basically, i want to wrap this up as something like: | | gengam :: RandomGen g => g -> Double -> Double -> (g, Double) | | analogously to the normal random # generation stuff. There's a standard approach, originally due to Lennart Augustsson. Have a single function that generates an infinite supply mkSupply :: IO Supply The Supply is a tree data Supply = Supply Int Supply Supply So splitting and generation are easy. But how do you generate an infinite tree? By using your side-effecting function plus unsafeInterleaveIO. (This function is better behaved then unsafePerformIO; no need for NOINLINE nonsense.) Here's the code from GHC's unique supply (you can ignore all the unboxed stuff. The genSymZh thing is the equivalent to your gengam. You still need the tree so that if you split the same random supply twice, you get the same thing: let (g1,g2) = split g in .. is the same as let g1 = fst (split g); g2 = snd (split g) in ... Simon mkSplitUniqSupply (C# c#) = let mask# = (i2w (ord# c#)) `uncheckedShiftL#` (i2w_s 24#) -- This is one of the most hammered bits in the whole compiler mk_supply# = unsafeInterleaveIO ( mk_unique >>= \ uniq -> mk_supply# >>= \ s1 -> mk_supply# >>= \ s2 -> return (MkSplitUniqSupply uniq s1 s2) ) mk_unique = genSymZh >>= \ (W# u#) -> return (I# (w2i (mask# `or#` u#))) in mk_supply#

2 1

Invitation to ICSM 2004, the 20th International Conference on Software Maintenance
by Software Maintenance 27 Jun '04

27 Jun '04

Attend ICSM 2004, the International Conference on Software Maintenance, 11-14 September 2004 in Chicago IL USA. Held continuously since 1983, ICSM, the International Conference on Software Maintenance, is the major international conference in the field of software and systems maintenance, evolution, and management. ICSM is the 20th in this series of international conferences. See www.cs.iit.edu/~icsm2004 for registration and details. Or email Publicity Co-Chair Nicholas Zvegintzov at zvegint(a)softwaremanagement.com with a request for all details. Register on-line at www.cs.iit.edu/~icsm2004, tab "Registration". Accommodation and the conference itself will be at the historic Palmer House Hilton Hotel in downtown Chicago, near the lakeside. See www.cs.iit.edu/~icsm2004, tab "Hotel Reservation". The ICSM 2004 program (www.cs.iit.edu/~icsm2004, tab "Program Information") includes: * 3 days (September 12-14) of 15 Technical Sessions featuring 48 research and empirical papers * 2 Industrial Applications Sessions featuring state-of-the-art descriptions, experience reports, and survey reports from real projects, industrial practices and models * 3 Tools Sessions featuring commercial and research tools with hands-on demonstrations * 2 Panel Sessions: Test-Driven Development and Software Maintenance Evolution and Maintenance of Web Service Applications * The PhD Dissertation Session presenting doctoral research in software maintenance and evolution * Keynotes by Bill Woodworth (Corporate Director of IBM Software Test and Development Excellence) and Victor R. Basili (Professor of Computer Science at the University of Maryland and the Executive Director of the Fraunhofer Center - Maryland) * 4 Tutorials (September 11): Management of Maintenance and Evolution Meta-programming in XVCL for Enhanced Changeability Program Transformation Systems: Theory and Practice for Software Generation, Maintenance and Reengineering Developing Software for Safety Critical Systems: When Failure is not an Option ICSM 2004 is associated with: 10th International Symposium on Software Metrics (http://swmetrics.org/) 6th International Workshop on Web Site Evolution (http://www.websiteevolution.org) 4th International Workshop on Source Code Analysis and Manipulation (http://www.brunel.ac.uk/%7Ecsstmmh2/scam2004/) 9th IEEE Workshop on Empirical Studies of Software Maintenance (WESS 04) (http://www.ise.gmu.edu/wess04/) General Chair is Panos Linos, Butler University, USA, with Program Co-Chairs Mark Harman, Brunel University, UK, and Bogdan Korel, Illinois Institute of Technology, USA. The Conference is sponsored by IEEE Computer Society's Technical Council on Software Engineering (TCSE) in cooperation with Illinois Institute of Technology. ICSM 2004 The International Conference on Software Maintenance 11-14 September 2004 The Palmer House Hilton Hotel Chicago IL USA http://www.cs.iit.edu/~icsm2004/

1 0

randomgen for foreign random functions
by Hal Daume III 25 Jun '04

25 Jun '04

Hi All -- Say I have a foreign function: foreign import ccall "statistical_c.h gengam" c_gengam :: CDouble -> CDouble -> IO CDouble that returns a random value parameterized by the two CDoubles. clearly this must happen in IO since the return value will be different each time, and some global state stuff is getting modified on the C side to facilitate future random # generation. However, I would like to wrap this into an essentially pure function, ala the Random class. basically, i want to wrap this up as something like: gengam :: RandomGen g => g -> Double -> Double -> (g, Double) analogously to the normal random # generation stuff. is there a safe way to do this? one option, of course, is just to unsafePerformIO it and {-# NOINLINE #-} the call, but that is rather, uhm, unsafe, I believe. it seems to me that something like this should be possible. Any thoughts? - Hal -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume

3 3

MPC2004: Final call for participation
by Jeremy Gibbons 25 Jun '04

25 Jun '04

MPC 2004 7th International Conference on MATHEMATICS OF PROGRAM CONSTRUCTION 12-14 July, 2004, Stirling, Scotland, UK http://www.cs.cornell.edu/Projects/MPC2004 Organised in conjunction with AMAST and CMPP FINAL CALL FOR PARTICIPATION The final registration deadline for MPC2004 is 29th June. Accommodation is still available, but places are limited. To register, please follow the link from the conference web page, at the URL above. (Our apologies if you receive multiple copies of this announcement.) Jeremy Gibbons on behalf of the MPC programme committee -- Jeremy.Gibbons(a)comlab.ox.ac.uk Oxford University Computing Laboratory, TEL: +44 1865 283508 Wolfson Building, Parks Road, FAX: +44 1865 273839 Oxford OX1 3QD, UK. URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html

1 0

Exceptions in types and exception-free programming
by oleg＠pobox.com 25 Jun '04

25 Jun '04

S. Alexander Jacobson wrote: > Also, is there a way to get the typesystem to > tell you which functions may fail i.e. which > functions have failMsg as an implicit parameter? Generally speaking, that is not that easy. If we have a functional composition (foo . bar), we wish its type to reflect the _union_ of exceptions that can be raised in 'foo' and in 'bar'. Union types are hard to get. That's why in Ocaml, for example, exceptions aren't the part of a function signature. The good news is that we already have union types in Haskell -- to a large extent. To an extent enough to put exceptions into the types. The following are two approaches. They aren't perfect -- but that's a start. A better way however is to statically assure that no exception can occur. That is possible to achieve in Haskell today -- and improve efficiency of the code in the process due to elimination of run-time checks. The end of the message gives an example. The first approach applies only to polymorphic functions. Also we have to watch for monomorphic restriction (but we all know that). And it also works in GHC only, because GHC is lazy when it comes to constraint resolution (which is a good thing, IMHO). > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module TER where > > class CERROR a c where > darn:: a -> c-> String -> b > > instance Show a => CERROR a c where > darn label _ msg = error $ "Error: " ++ (show label) ++ " " ++ msg > > > data EHead = EHead deriving Show > data ETail = ETail deriving Show > data EJust = EJust deriving Show > > myhead x@([]) = darn EHead x "head of an empty list" > myhead (x:_) = x > > mytail x@([]) = darn ETail x "tail of an empty list" > mytail (_:xs) = xs Now, if we ask GHCi for the type of myhead, we get *TER> :t myhead myhead :: forall a. (CERROR EHead [a]) => [a] -> a As we can see, the exception is apparent right in the function type. We can define > ht x = myhead $ mytail $ mytail x *TER> :t ht ht :: forall a. (CERROR ETail [a], CERROR EHead [a]) => [a] -> a We can see that we indeed have a union of exceptions that can be raised in different sub-expressions of ht. A more involved example: > myjust (Just a) = a > myjust x = darn EJust x "Just nothing" > > foo x = myjust $ myhead $ mytail $ myjust x *TER> :t foo foo :: forall b. (CERROR EJust (Maybe [Maybe b]), CERROR ETail [Maybe b], CERROR EHead [Maybe b], CERROR EJust (Maybe b)) => Maybe [Maybe b] -> b *TER> foo (Just [Nothing,Just 2]) 2 *TER> foo (Just [Nothing]) *** Exception: Error: EHead head of an empty list The second method involves the use of implicit parameters. It works both in GHC and in Hugs, and can work with monomorphic functions too. But is has some other drawback (although that depends on the point of view) > idarn _ msg = error msg > > myhead1 [] = idarn ?e_head "head of an empty list" > myhead1 (x:_) = x > > mytail1 x@([]) = idarn ?e_tail "tail of an empty list" > mytail1 (_:xs) = xs > > ht1 x = myhead1 $ mytail1 $ mytail1 x If we check for the type of ht1 (e.g., in Hugs), we get TER> :t ht1 ht1 :: (?e_tail :: a, ?e_head :: b) => [c] -> c That is, ht1 can fail because it tries to get either the head or the tail of an empty list. Again, we get the true _union_ of exceptions. Alas, we can't invoke ht1 in a simple way any more. We've got to bind the errors. TER> let ?e_head = undefined; ?e_tail = undefined in ht1 [1,2] Program error: head of an empty list TER> let ?e_head = undefined; ?e_tail = undefined in ht1 [1,2,3] 3 It seems that the best way to cope with exceptions is to assure statically that they cannot occur at all -- in large segments of code. We don't need to change Haskell. Haskell already can "fake it" quite believably. Indeed, let us consider a segment of the code assert x msg = if x then (not x) else error msg foo x | assert (not (null x)) "non-empty-list in ..." = undefined foo x = ... body_foo x ... Obviously, when the second clause is about to executed, _we_ know that x is a non-empty list. Alas, that fact is not reflected in the type of x. And it cannot in the above case. Indeed, what if we change the order of clauses by mistake: foo x = ... body_foo x ... foo x | assert (not (null x)) "non-empty-list in ..." = undefined To the typechecker, the order of clauses makes no difference. Yet it does to the executioneer. There is however a way to make the assurances statically certain. We should re-write the code as with_non_empty_list x foo where with_non_empty_list:: [a] -> NonemptyList [a] does the run-time check -- and generates the run-time error. But, if the check succeeded, we know that the list is not empty. That information can be encoded statically, and be used within the body of foo. If NonemptyList is a newtype, no run-time overhead occurs. Moreover, within the body of foo we can use unsafe versions of head and tail when applied to 'x' because we are statically assured 'x' is non-empty. We cannot avoid run-time checks -- yet we can (greatly) reduce their quantity and improve confidence in the code. The paper about number-parameterized types (being considered for JFP, I guess?) shows a more involved example: list reversal with an accumulator. Here's a simple code: > newtype NonEmpty a = NonEmpty [a] -- the NonEmpty constructor should > -- be hidden (not exported from its module) > > head' (NonEmpty a) = head a -- no error can occur! Can use unsafe version > tail' (NonEmpty a) = tail a -- no error can occur! Can use unsafe version > > -- trusted function: the only one that can use NonEmpty constructor. > fork_list_len f g x = if null x then f else g (NonEmpty x) > > revers x = revers' x [] > where > revers' x accum = fork_list_len accum (g accum) x > g accum x = revers' (tail' x) ((head' x):accum) That is a complex example as the sizes of all the lists involved change on every iteration. The function is recursive. And yet it is possible to type the function in Haskell _and_ statically assure that all applications of head and tail are safe! There are some run-time checks, in fork_list_len. But first, we had to do that check anyway, according to our algorithm. And second, each iteration does one list size check but two applications of list deconstructors. If functions head' and tail' do no run-time checks (as they should not), then we save one size check per iteration. So, it is possible to achieve both efficiency and safety at the same time!

1 0