- Libraries - Haskell.org

Data.FiniteMap proposed addition, bug fix
by Graham Klyne 15 Nov '04

15 Nov '04

At 13:06 09/11/04 +0000, Simon Marlow wrote: >On 09 November 2004 12:45, Graham Klyne wrote: > > > I'd like to propose an addition to the FiniteMap module in the form > > of a monadic version of plusFM_C. The proposed implementation is > > pretty much a copy of the existing implementation within a do block. > >Data.FiniteMap will shortly be deprecated in favour of DData.Map (which >will be renamed to Data.Map when it is imported). Perhaps you'd like to >reformulate the proposal using Data.Map instead? I added tests for the monad threading order, and realized it was a complete red herring. (I got it in my head that when reversing the parameters to optimize the hedge union, I needed to reverse the monad ordering. Duh!) So the two sets of functions for hedgeUnionWithKeyM* were unnecessary, unless it really is desired to have right-to-left monad threading #g -- Proposed addition: [[ {-------------------------------------------------------------------- Monadic union --------------------------------------------------------------------} -- | /O(n+m)/. Monadic version of union with a combining function. -- The implementation uses the efficient /hedge-union/ algorithm. -- -- The combining function returns a monadic value, which is threaded though -- the combined elements in key order, yielding a Map that is bound -- to the same monadic type. The intended use for this is with a Maybe -- monad, allowing result returned to be Nothing if any of the attempted -- combinations of key values return Nothing. Could also be usefully used -- with an error or state monad. -- unionWithM :: (Ord k, Monad m) => (a -> a -> m a) -> Map k a -> Map k a -> m (Map k a) unionWithM f m1 m2 = unionWithKeyM (\k x y -> f x y) m1 m2 -- | /O(n+m)/. Monadic version of @unionWithKey@. -- The implementation uses the efficient /hedge-union/ algorithm. -- -- See @unionWithM@ for further details. -- unionWithKeyM :: (Ord k, Monad m) => (k -> a -> a -> m a) -> Map k a -> Map k a -> m (Map k a) unionWithKeyM f Tip t2 = return t2 unionWithKeyM f t1 Tip = return t1 unionWithKeyM f t1 t2 -- hedge-union is more efficient on (bigset `union` smallset) | size t1 >= size t2 = hedgeUnionWithKeyML f (const LT) (const GT) t1 t2 | otherwise = hedgeUnionWithKeyML flipf (const LT) (const GT) t2 t1 where flipf k x y = f k y x -- Left version of monadic hedgeUnionWithKey. -- (Monad is threaded left-to-right in tree) -- hedgeUnionWithKeyML :: (Ord k, Monad m) => (k -> a -> a -> m a) -> (k -> Ordering) -> (k -> Ordering) -> Map k a -> Map k a -> m (Map k a) hedgeUnionWithKeyML f cmplo cmphi t1 Tip = return t1 hedgeUnionWithKeyML f cmplo cmphi Tip (Bin _ kx x l r) = return $ join kx x (filterGt cmplo l) (filterLt cmphi r) hedgeUnionWithKeyML f cmplo cmphi (Bin _ kx x l r) t2 = do { newl <- hedgeUnionWithKeyML f cmplo cmpkx l lt ; newx <- case found of Nothing -> return x Just y -> f kx x y ; newr <- hedgeUnionWithKeyML f cmpkx cmphi r gt ; return $ join kx newx newl newr } where cmpkx k = compare kx k lt = trim cmplo cmpkx t2 (found,gt) = trimLookupLo kx cmphi t2 -- And some test cases: fm1 = fromList [(1,["a"]),(2,["b","c"]),(3,["d"])] fm2 = fromList [(1,["b","c"]),(4,["e"])] fm3 = fromList [(1,["d","e"]),(2,["c","d"]),(4,["f"])] -- Test function returns Nothing if list values have a member in common: comb ovs nvs | null (List.intersect ovs nvs) = Just (ovs++nvs) | otherwise = Nothing fm12 = Just $ fromList [(1,["a","b","c"]),(2,["b","c"]),(3,["d"]),(4,["e"])] fm13 = Nothing fm23 = Just $ fromList [(1,["b","c","d","e"]),(2,["c","d"]),(4,["e","f"])] fmt1 = unionWithM comb fm1 fm2 == fm12 fmt2 = unionWithM comb fm1 fm3 == fm13 fmt3 = unionWithM comb fm2 fm3 == fm23 -- Test function uses state to accumulate combined keys combk :: k -> [a] -> [a] -> State.State [k] [a] combk k ov nv = State.State (\s -> (ov++nv,s++[k])) fmk12 = ( fromList [(1,["a","b","c"]),(2,["b","c"]),(3,["d"]),(4,["e"])] , [1] ) fmk13 = (fromList [(1,["a","d","e"]),(2,["b","c","c","d"]),(3,["d"]),(4,["f"])] ,[1,2] ) fmk23 = (fromList [(1,["b","c","d","e"]),(2,["c","d"]),(4,["e","f"])] ,[1,4]) fmt4 = State.runState (unionWithKeyM combk fm1 fm2) [] == fmk12 fmt5 = State.runState (unionWithKeyM combk fm1 fm3) [] == fmk13 fmt6 = State.runState (unionWithKeyM combk fm2 fm3) [] == fmk23 fmtall = and [fmt1,fmt2,fmt3,fmt4,fmt5,fmt6] ]] ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact _______________________________________________ Libraries mailing list Libraries(a)haskell.org http://www.haskell.org/mailman/listinfo/libraries ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 4

GHC.Unicode
by Ross Paterson 11 Nov '04

11 Nov '04

This module diverges slightly from Haskell 98, which has isAlpha c = isUpper c || isLower c I'd also suggest using the H98 definitions of isDigit and isControl, even though glibc does the same thing.

1 0

RE: proposal for ghc-pkg to use a directory of .conf files
by Simon Marlow 09 Nov '04

09 Nov '04

On 08 November 2004 18:47, Duncan Coutts wrote: > We can use ghc-pkg at the build / install-into-temp phase to create > the $(package).conf files under > $TMP_INSTALL_ROOT/usr/lib/ghc-$VER/package.conf.d/ and then final > installation is jsut merging files without any post-install calls to > ghc-pkg to modify installed files (ie the global ghc package.conf > file) > > So we can still keep the abstraction of $HC-pkg and gain simpler > packaging stuff. Ok, sounds reasonable. I'm going to be working on the package support in ghc and ghc-pkg to improve support for Cabal, so let's do this at the same time. Cheers, Simon

2 1

RE: Proposed addition to Data.FiniteMap
by Graham Klyne 09 Nov '04

09 Nov '04

At 13:06 09/11/04 +0000, Simon Marlow wrote: >On 09 November 2004 12:45, Graham Klyne wrote: > > > I'd like to propose an addition to the FiniteMap module in the form > > of a monadic version of plusFM_C. The proposed implementation is > > pretty much a copy of the existing implementation within a do block. > >Data.FiniteMap will shortly be deprecated in favour of DData.Map (which >will be renamed to Data.Map when it is imported). Perhaps you'd like to >reformulate the proposal using Data.Map instead? OK, the proposed addition is below. I haven't fully tested the monad threading order. (Hmm.. using a state monad to collect a list of keys might be a way to do that.) Deprecation notwithstanding, given that FiniteMap is the current library module, and that it would be nice if my code works out-of-the-box with the next public release of the libraries, would there be any objection to also adding my original proposal to the current FiniteMap module? #g -- Proposed addition: [[ {-------------------------------------------------------------------- Monadic union --------------------------------------------------------------------} -- | Monadic version of union with a combining function. -- -- The combiner function returns a monadic value, which is threaded though -- the combined elements in key order, yielding a Map that is bound -- to the same monadic type. The intended use for this is with a Maybe -- monad, allowing result returned to be Nothing if any of the attempted -- combinations of key values return Nothing. Could also be usefully used -- with an error or state monad. -- unionWithM :: (Ord k, Monad m) => (a -> a -> m a) -> Map k a -> Map k a -> m (Map k a) unionWithM f m1 m2 = unionWithKeyM (\k x y -> f x y) m1 m2 -- | Monadic version of unionWithKey. -- -- (See unionWithM) -- unionWithKeyM :: (Ord k, Monad m) => (k -> a -> a -> m a) -> Map k a -> Map k a -> m (Map k a) unionWithKeyM f Tip t2 = return t2 unionWithKeyM f t1 Tip = return t1 unionWithKeyM f t1 t2 -- hedge-union is more efficient on (bigset `union` smallset) | size t1 >= size t2 = hedgeUnionWithKeyML f (const LT) (const GT) t1 t2 | otherwise = hedgeUnionWithKeyMR f (const LT) (const GT) t2 t1 -- Left version of monadic hedgeUnionWithKey -- (Monad is threaded left-to-right in tree) hedgeUnionWithKeyML :: (Ord k, Monad m) => (k -> a -> a -> m a) -> (k -> Ordering) -> (k -> Ordering) -> Map k a -> Map k a -> m (Map k a) hedgeUnionWithKeyML f cmplo cmphi t1 Tip = return t1 hedgeUnionWithKeyML f cmplo cmphi Tip (Bin _ kx x l r) = return $ join kx x (filterGt cmplo l) (filterLt cmphi r) hedgeUnionWithKeyML f cmplo cmphi (Bin _ kx x l r) t2 = do { newl <- hedgeUnionWithKeyML f cmplo cmpkx l lt ; newx <- case found of Nothing -> return x Just y -> f kx x y ; newr <- hedgeUnionWithKeyML f cmpkx cmphi r gt ; return $ join kx newx newl newr } where cmpkx k = compare kx k lt = trim cmplo cmpkx t2 (found,gt) = trimLookupLo kx cmphi t2 -- Right version of monadic hedgeUnionWithKey -- (Monad is threaded Right-to-Left in tree) hedgeUnionWithKeyMR :: (Ord k, Monad m) => (k -> a -> a -> m a) -> (k -> Ordering) -> (k -> Ordering) -> Map k a -> Map k a -> m (Map k a) hedgeUnionWithKeyMR f cmplo cmphi t1 Tip = return t1 hedgeUnionWithKeyMR f cmplo cmphi Tip (Bin _ kx x l r) = return $ join kx x (filterGt cmplo l) (filterLt cmphi r) hedgeUnionWithKeyMR f cmplo cmphi (Bin _ kx x l r) t2 = do { newr <- hedgeUnionWithKeyMR f cmpkx cmphi r gt ; newx <- case found of Nothing -> return x Just y -> f kx y x ; newl <- hedgeUnionWithKeyMR f cmplo cmpkx l lt ; return $ join kx newx newl newr } where cmpkx k = compare kx k lt = trim cmplo cmpkx t2 (found,gt) = trimLookupLo kx cmphi t2 -- And some test cases: fm1 = fromList [(1,["a"]),(2,["b","c"]),(3,["d"])] fm2 = fromList [(1,["b","c"]),(4,["e"])] fm3 = fromList [(1,["d","e"]),(2,["c","d"]),(4,["f"])] fm12 = Just $ fromList [(1,["a","b","c"]),(2,["b","c"]),(3,["d"]),(4,["e"])] fm13 = Nothing fm23 = Just $ fromList [(1,["b","c","d","e"]),(2,["c","d"]),(4,["e","f"])] -- Test function returns Nothing if list values have a member in common: comb ovs nvs | null (List.intersect ovs nvs) = Just (ovs++nvs) | otherwise = Nothing fmt1 = unionWithM comb fm1 fm2 == fm12 fmt2 = unionWithM comb fm1 fm3 == fm13 fmt3 = unionWithM comb fm2 fm3 == fm23 fmtall = and [fmt1,fmt2,fmt3] ]] ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: Proposed addition to Data.FiniteMap
by Simon Marlow 09 Nov '04

09 Nov '04

On 09 November 2004 12:45, Graham Klyne wrote: > I'd like to propose an addition to the FiniteMap module in the form > of a monadic version of plusFM_C. The proposed implementation is > pretty much a copy of the existing implementation within a do block. Data.FiniteMap will shortly be deprecated in favour of DData.Map (which will be renamed to Data.Map when it is imported). Perhaps you'd like to reformulate the proposal using Data.Map instead? Cheers, Simon

1 0

Proposed addition to Data.FiniteMap
by Graham Klyne 09 Nov '04

09 Nov '04

I'd like to propose an addition to the FiniteMap module in the form of a monadic version of plusFM_C. The proposed implementation is pretty much a copy of the existing implementation within a do block. [[ -- | Monadic version of plusFM_C. -- -- The combiner function returns a monadic value, which is threaded though -- the combined elements in key order, yielding a FiniteMap that is bound -- to the same monadic type. The intended use for this is with a Maybe -- monad, allowing result returned to be Nothing if any of the attempted -- combinations of key values return Nothing. Could also be usefully used -- with an error or state monad. plusFM_CM :: ( Ord key, Monad m ) => (elt -> elt -> m elt) -> FiniteMap key elt -> FiniteMap key elt -> m (FiniteMap key elt) plusFM_CM combiner EmptyFM fm2 = return fm2 plusFM_CM combiner fm1 EmptyFM = return fm1 plusFM_CM combiner fm1 (Branch split_key elt2 _ left right) = do { new_l <- plusFM_CM combiner (splitLT fm1 split_key) left ; new_elt <- case lookupFM fm1 split_key of Nothing -> return elt2 Just elt1 -> combiner elt1 elt2 ; new_r <- plusFM_CM combiner (splitGT fm1 split_key) right ; return $ mkVBalBranch split_key new_elt new_l new_r } -- And some test cases: fm1 = listToFM [(1,["a"]),(2,["b","c"]),(3,["d"])] fm2 = listToFM [(1,["b","c"]),(4,["e"])] fm3 = listToFM [(1,["d","e"]),(2,["c","d"]),(4,["f"])] fm12 = Just $ listToFM [(1,["a","b","c"]),(2,["b","c"]),(3,["d"]),(4,["e"])] fm13 = Nothing fm23 = Just $ listToFM [(1,["b","c","d","e"]),(2,["c","d"]),(4,["e","f"])] -- Test function returns Nothing if list values have a member in common: comb ovs nvs | null (intersect ovs nvs) = Just (ovs++nvs) | otherwise = Nothing fmt1 = plusFM_CM comb fm1 fm2 == fm12 fmt2 = plusFM_CM comb fm1 fm3 == fm13 fmt3 = plusFM_CM comb fm2 fm3 == fm23 fmtall = and [fmt1,fmt2,fmt3] ]] ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

RE: [Haskell-cafe] Hal Daume III's NewBinary now ghc6ized, cabalized, debianize, darcsized.
by Simon Peyton-Jones 09 Nov '04

09 Nov '04

Good work! The last thing you need to do is to send a note to John Petersen to incorporate it on the Haskell libraries page haskell.org/libraries. That way lots more people will be able to find it. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | Jeremy Shaw | Sent: 08 November 2004 19:43 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] Hal Daume III's NewBinary now ghc6ized, cabalized,debianize, darcsized. | | Hello, | | I am quite interested in having better Binary support in Haskell -- | especially support for reading and writing binary files and protocols | that have fields smaller than 8-bits and non-byte alignment. | | As a first step, I have republished Hal Daume III's NewBinary package | in hopes that it will inspire some forward movement on it. I have made | the following 'improvements': | | ~ ghc6ized | | cd /tmp/NewBinary/ | diff /tmp/Binary.hs /tmp/NewBinary/NewBinary/Binary.hs | 81c81,82 | < import GHC.Handle ( openFileEx, IOModeEx(..) ) | --- | > import GHC.Handle | > import IOExts ( openFileEx, IOModeEx(..) ) | | (hrm, I probably don't need to import GHC.Handle anymore either...) | | ~ cabalized | | To build, you need the Cabal libraries installed. Then do something | like this: | | ghc -package Setup.lhs -o setup | ./setup configure | ./setup build | ./setup install | ./setup register (? maybe not needed ?) | | ~ debianized | | You should be able to build and install it like any other debian | package: | | dpkg-buildpackage && debi | | ~ darcsized | | darcs get http://www.n-heptane.com/nhlab/repos/NewBinary | | I hope I am not stepping on anyone's toes or duplicating efforts. | | Jeremy Shaw. | | ps. The original is available at: | | http://www.isi.edu/~hdaume/haskell/NewBinary/ | -- | | This message contains information which may be confidential and privileged. Unless you are the | addressee (or authorized to receive for the addressee), you may not use, copy or disclose to anyone | the message or any information contained in the message. If you have received the message in error, | please advise the sender and delete the message. Thank you. | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

RE: proposal for ghc-pkg to use a directory of .conf files
by Simon Marlow 08 Nov '04

08 Nov '04

On 06 November 2004 10:10, Sven Panne wrote: > Duncan Coutts wrote: >> I can knock up a proof of concept patch if anyone thinks this is a >> good idea. It should be totally backward compatible, it's ok to use >> both, but ditro packagers might like to enforce a policy of using a >> directory of package files for external libraries. > > OK, just send us a patch and if there are no objections we can merge > it into the HEAD. In some ways this looks like a good idea, but it contradicts some of the ideas in the Cabal proposal. There, we were treating the package database as an abstract entity hidden behind the ghc-pkg interface. All interaction with the database would be done via ghc-pkg. The advantages of this abstraction are the usual ones: we might want to change the representation, and the ghc-pkg tool provides a good place to add backwards compatibility if necessary. However, I'm prepared to be persuaded. The "just put a file in this directory" approach to installation is very compelling, being much more transparent. But bear in mind that if we pick this route, then backwards compatibility has to be built into the file format (I think it might be already, but we're planning changes in this area to better support Cabal). Also, there needs to be a way to find the location to install the file - asking ghc or ghc-pkg is the usual way. Cheers, Simon

2 1

proposal for ghc-pkg to use a directory of .conf files
by Duncan Coutts 06 Nov '04

06 Nov '04

Hi, It has been common in recent years since the widespread use of package management systems to break up configuration / settings files that are used by several packages into a directory of individual files rather than modifying a global file. The advantage of doing this is that it makes things easier for the package managers. Each individual file can belong to the appropriate package and so instead of having to execute registration/unregistration actions on install/uninstall it's just another file to add/remove. The other advantage is that there is no longer a global file that needs to be modified which means uninstallation is cleaner (most package managers do not remove files that were modified after installation). So the idea is that in addition to a single $HC-LIB/package.conf file you have a directory of package files $HC-LIB/package.conf.d/*.conf Obviously, the package chasing code needs to be tweaked slightly to slurp in a whole directory of .conf files and $HC-pkg would want to be able to use a directory as an installed package source. I had a peak at the code in ghc for dealing with .conf files. I'd guess it'd be best ok just check if the specified package file is a directory or an ordinary file and act accordingly. Ie you could say "-package-conf packages/" and ghc could by default read from $HC-LIB/package.conf and $HC-LIB/package.conf.d/ or something. I can knock up a proof of concept patch if anyone thinks this is a good idea. It should be totally backward compatible, it's ok to use both, but ditro packagers might like to enforce a policy of using a directory of package files for external libraries. Duncan

2 1

Re: Double -> CDouble, realToFrac doesn't work
by ross＠soi.city.ac.uk 05 Nov '04

05 Nov '04

[switching to libraries] Recap: the definition of realToFrac as going through Rational loses the NaN and +/-Infinity values of Double and Float (though GHC's RULES bypass this). On Thu, Nov 04, 2004 at 08:32:52PM +0100, Sven Panne wrote: > It's an old thread, but nothing has really happened yet, so I'd like to > restate and expand the question: What should the behaviour of toRational, > fromRational, and decodeFloat for NaN and +/-Infinity be? Even if the report > is unclear here, it would be nice if GHC, Hugs, and NHC98 agreed on > something. > Can we agree on the special Rational values below? [The proposal is to add 0:%0, 1:%0 and -1:%0 to Rational.] Changing Rational from meaning rational numbers would also be bad. I'd prefer to redefine realToFrac to go through a new type that is the union of Rational and these values. That would mean adding extended variants of toRational and fromRational to the Real and Fractional classes, with default definitions but overidden for the Float and Double instances. This type and the variant of fromRational might be usable for floating point literals too. > Printing those values could be more consistent for these systems, too, BTW. True, though Hugs is already inconsistent with H98 in its printing of floating point values.

6 9