- Libraries - Haskell.org

RE: [Haskell] RFC: DData in hierarchical libraries
by Simon Marlow 11 Mar '04

11 Mar '04

> I propose to add a modified version of DData to the > hierachical libraries. > > DData is a concrete library of collection types, by > Daan Leijen. > My modifications intend to make DData fit better in > the hierarchical libraries. > > The haddock-generated documentation can be found here: > > http://users.skynet.be/jyp/DData/doc/index.html > > while the source code is at > > http://users.skynet.be/jyp/DData/ddata.tar.gz Regarding the Seq type, I like the one that we use in GHC. See: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/utils/Ord List.lhs Both libraries can support the same interface, but the implementation in GHC's OrdList library is based on a concrete datatype: data OrdList a = Many [a] | Two (OrdList a) (OrdList a) | One a | None which is more flexible, and probably more efficient. Indeed for performance reasons you might want two more constructors: | Cons a (OrdList a) | Snoc (OrdList a) a I'd like to see many more operations defined over Seqs. At least: snoc :: Seq a -> a -> Seq a concat :: Seq (Seq a) -> Seq a and probably many other functions from Data.List. ------------- Looking briefly at the rest of the library, I have a few questions/comments: Why are there IntBags but no Bags? How do DData.Map and DData.IntMap compare in performance to the existing Data.FiniteMap? Similarly for Sets? Can IntMap and IntSet be implemented by specialisation or overloading the Set type (ala the overloaded arrays in Data.Array)? (The interfaces look very similar, but I didn't compare them in detail). Why is there no direct translation between Seqs and Sets/Maps, but there is for lists? I guess there's a consistency issue here - do we want to (a) use lists exclusively, (b) use Seq exclusively, or (c) have all operations available for both types? Internal functions like DData.Set.valid should not be visible. Cheers, Simon

4 3

Re: [Haskell] RFC: DData in hierarchical libraries
by Christian Maeder 11 Mar '04

11 Mar '04

JP Bernardy wrote: > Could you be more specific about this? Oops, shall I supply documentation text? > Would you prefix the function name with unsafe? I > wonder what is the best way to do such a marking. No, I only suggest(ed) to change the documentation, may to "unsafe coercions of ordered lists". (The name "formDistinctAscList" is compelling enough) >>Furthermore, already for >>Set.fromList I expect it to be linear, if the input >>list happens to be >>ascending. > > I'm afraid it's not, unfortunately. I intend not to > fiddle with the implementation, to avoid the involved > instability. Well, no problem, only my wrong assumption (and an argument to use "unsafe" functions for efficiency), don't change the implementation. > I'd choose "mapMonotonic", from Edison. Maybe the infix (or suffix) "Asc" could uniformly indicate the unsafe nature of a functions. So delete toAscList and have fromAscList and mapAsc as unsafe versions of fromList and map resp. (forget Set.image) Christian

1 0

Re: [Haskell] Re: RFC: DData in hierarchical libraries
by JP Bernardy 11 Mar '04

11 Mar '04

--- Johannes Waldmann <waldmann(a)imn.htwk-leipzig.de> wrote: > A few comments on the DData.Map proposal: > > * nice work. I might start using it (instead of > Data.FiniteMap) > just because the function names look better :-) Cool! ;) > * argument ordering: > > the existing Data.FiniteMap mostly has > f :: FiniteMap -> ... -> FiniteMap > while the proposal uses > f :: ... -> FiniteMap -> FiniteMap > I think the Edison guidelines are quite nice: > http://www.haskell.org/ghc/docs/edison/users004.html#toc10 > Did you follow them? What exceptions? I have this additional top-priority rule: Whenever a function has the same name as one in Data.List, it should have a corresponding type. But basically, those rules are followed. The above difference you mention is justified by ... "Functions that modify a collection should take the collection last." > * types: some functions are not declared at their > most > general type (I checked by commenting out the > decl. and asking ghci) > > difference :: forall a1 k a. > (Ord k) => > Map k a1 -> Map k a -> Map k a1 > > differenceWithKey :: forall a1 k a. > (Ord k) => > (k -> a1 -> a -> Maybe a1) -> > Map k a1 -> Map k a > -> Map k a1 > > intersection :: forall a k a1. > (Ord k) => > Map k a -> Map k a1 -> Map k a > > intersectionWith :: forall a k a2 a1. > (Ord k) => > (a1 -> a2 -> a) -> Map k a1 -> > Map k a2 -> Map k a > > > intersectionWithKey :: forall a k a1 a2. > (Ord k) => > (k -> a2 -> a1 -> a) -> Map > k a2 -> Map k a1 -> > Map k a > > isSubsetOfBy :: forall a1 k a. > (Ord k) => > (a -> a1 -> Bool) -> Map k a -> Map > k a1 -> Bool Well spotted. I'll change those. Cheers, JP. __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com

1 0

RE: Text.PrettyPrint.HughesPJ fixities
by Simon Peyton-Jones 05 Mar '04

05 Mar '04

To be honest I have totally paged that code out. I cvs log doesn't show the "massive perf bug" entry for either of the modules we specify, though I do vaguely remember something. My memory is that it shouldn't matter which way round you associate <> and <+>, but I could well be wrong about that. If anyone wants to dive in, please go ahead! (I don't think I'm likely to.) I do have somewhere a half-written paper about the internals of the HughesPJ library. Adding the 'empty' document and <+> were entirely non-trivial, and made my head hurt badly. Alas, I never finished the paper, but I'll hunt if someone wants it. Simon | -----Original Message----- | From: libraries-bounces(a)haskell.org [mailto:libraries-bounces@haskell.org] On Behalf Of Ian Lynagh | Sent: 04 March 2004 00:46 | To: libraries(a)haskell.org | Subject: Text.PrettyPrint.HughesPJ fixities | | | Hi, | | Text.PrettyPrint.HughesPJ (the same applies to | ghc/compiler/utils/Pretty.lhs) contains | | infixl 6 <> | infixl 6 <+> | infixl 5 $$, $+$ | | whereas my intuition says that infixr will give more efficient | implementation. Is my intuition wrong? It seems to be supported by the | definitions of hcat, hsep, vcat being defined in terms of foldr. | | | We on #haskell are also confused by the changelog entry starting | "Cured massive performance bug." and ending | "I'm not satisfied that I've done the best possible job. I'll send you | the code if you are interested.". | It looks to me like the change was made and the original mail about the | problem appended without being reread? | | | Thanks | Ian | | _______________________________________________ | Libraries mailing list | Libraries(a)haskell.org | http://www.haskell.org/mailman/listinfo/libraries

1 0

Text.PrettyPrint.HughesPJ fixities
by Ian Lynagh 03 Mar '04

03 Mar '04

Hi, Text.PrettyPrint.HughesPJ (the same applies to ghc/compiler/utils/Pretty.lhs) contains infixl 6 <> infixl 6 <+> infixl 5 $$, $+$ whereas my intuition says that infixr will give more efficient implementation. Is my intuition wrong? It seems to be supported by the definitions of hcat, hsep, vcat being defined in terms of foldr. We on #haskell are also confused by the changelog entry starting "Cured massive performance bug." and ending "I'm not satisfied that I've done the best possible job. I'll send you the code if you are interested.". It looks to me like the change was made and the original mail about the problem appended without being reread? Thanks Ian

1 0

RE: Data.PackedString.hGetPS
by Simon Marlow 01 Mar '04

01 Mar '04

> If I have > > \begin{code} > import Data.PackedString (hGetPS) > import System.IO (openBinaryFile, hClose, IOMode(ReadMode)) > > main :: IO () > main = do h <- openBinaryFile "1000000x" ReadMode > p <- hGetPS h 1000000 > hClose h > return () > \end{code} > > (1000000x is a file containing 1000000 'x' characters) then: > > and compile with ghc -O2 (either 6.2 or reasonably recent CVS) then I > get: > > $ ./foo > Stack space overflow: current size 1048576 bytes. > Use `+RTS -Ksize' to increase it. > $ I noticed a while back that Data.PackedString isn't being optimised as well as it should. Most of the code in there is written with the assumption that lots of Deforestation is going to happen, and in several of the cases I looked at it isn't. This is on our list of things to investigate (along with performance of the overloaded array support). > -- | Read a 'PackedString' directly from the specified 'Handle'. > -- This is far more efficient than reading the characters > into a 'String' > -- and then using 'packString'. > -- NOTE: as with 'hPutPS', the string representation in the file is > -- assumed to be ISO-8859-1. > hGetPS :: Handle -> Int -> IO PackedString > hGetPS h i = do > arr <- newArray_ (0, i-1) > l <- hGetArray h arr i > chars <- mapM (\i -> readArray arr i >>= > return.chr.fromIntegral) [0..l-1] > return (packString chars) > > (is the efficiency comment accurate? This definition is calling > packString on a String it makes, so it's not intuitively > obvious to me). > > I think the last line should be replaced with > > return (packNChars l chars) Indeed that would make a small improvement, yes. Cheers, Simon

1 0

Data.PackedString.hGetPS
by Ian Lynagh 28 Feb '04

28 Feb '04

Hi all, If I have \begin{code} import Data.PackedString (hGetPS) import System.IO (openBinaryFile, hClose, IOMode(ReadMode)) main :: IO () main = do h <- openBinaryFile "1000000x" ReadMode p <- hGetPS h 1000000 hClose h return () \end{code} (1000000x is a file containing 1000000 'x' characters) then: and compile with ghc -O2 (either 6.2 or reasonably recent CVS) then I get: $ ./foo Stack space overflow: current size 1048576 bytes. Use `+RTS -Ksize' to increase it. $ The definition is: -- | Read a 'PackedString' directly from the specified 'Handle'. -- This is far more efficient than reading the characters into a 'String' -- and then using 'packString'. -- NOTE: as with 'hPutPS', the string representation in the file is -- assumed to be ISO-8859-1. hGetPS :: Handle -> Int -> IO PackedString hGetPS h i = do arr <- newArray_ (0, i-1) l <- hGetArray h arr i chars <- mapM (\i -> readArray arr i >>= return.chr.fromIntegral) [0..l-1] return (packString chars) (is the efficiency comment accurate? This definition is calling packString on a String it makes, so it's not intuitively obvious to me). I think the last line should be replaced with return (packNChars l chars) and that the packNChars definition: packNChars len str = PS (array (0,len-1) (zip [0..] str)) is equivalent to: packNChars len str = PS (listArray (0,len-1) str) which I assume is more efficient (due to not con/destructing tuples if nothing else). None of this solves the stack overflow, though. While I'm here, David Roundy has a PackedString which looks to have been forked from GHC or its libraries, now based around data PackedString = PS !(ForeignPtr Word8) !Int !Int He said it can't serve as a replacement as it doesn't support large unicode characters, though (would just changing to a Word32 or Char fix that?). If you're interested it's in the darcs (http://abridgegame.org/darcs/) darcs repo - selecting "FastPackedString.hs" on http://abridgegame.org/cgi-bin/darcs?darcs* should show you the latest version. It doesn't have this problem. Thanks Ian

1 0

RE: URI handling code; proposed Network.URI replacement
by Simon Marlow 25 Feb '04

25 Feb '04

> Thanks. (I've started trying to apply Haddock markup in my > own code, but > I've not yet got round to actually generating the docs from it.) > > >Since it's mostly backwards compatible, there's no issue > with upgrading > >it in place. (well, there's one small issue: it introduces > a dependency > >from the network package on the parsec package, but that's not a big > >deal). > > Hmmm... Parsec is pretty central to what I've done. It's not a problem: just add parsec to the PACKAGE_DEPS for the network package. > >We'll arrange for CVS access so you can commit your new > version to the > >repository. > > OK. > > Another detail. Do you have a preferred form of licence for > this. I've > been putting my own applications out as GPL to date, but I > imagine that the > viral effect would be problematic for the compiler library. > I'm happy to > use any reasonable (open) licence. BSD-style is preferred, because the network package is already BSD licensed. A package is the unit of licensing, so libraries with different licenses have to go in separate packages (to make it easier for users to be sure that they are complying with licenses). Cheers, Simon

1 0

RE: [Haskell] regular expression syntax - perl ain't got nothin on haskell
by Simon Marlow 25 Feb '04

25 Feb '04

[ moved to libraries(a)haskell.org ] > Inspired by an idea by Andrew Pang and an old project of > mine, I decided > to fill out a reusable regular expression library which is similar to > Perl's, but much more expressive. > > It provides regular and monadic versions, a very overloaded and useful > interface, as well as extensibility. although currently the only > instance is based on Text.Regex, it generalizes to matching lists of > arbitrary type, not just strings, and also leaves the door open for > compile-time checked and optimized regular expressions via template > Haskell. > > so, does this seem interesting? I am really enjoying the =~ syntax > already in projects, and the monadic version is great for > concise ad-hoc parsers. This is neat. We should provide (something like) this in Text.Regex itself, although perhaps the more generic regular expression functionality should go somewhere like Data.Regex? In any case, I'd be happy to add something to Text.Regex if you settle on something you're happy with and send it to the list for comments. Cheers, Simon

1 0

More on POpen for Windows
by Graham Klyne 24 Feb '04

24 Feb '04

Further to problems reported in [1]. I've made a small step forward on this. I'm nearly out of time for now, so this is a partial report. I've created a pair of simple C programs: + EchoShiftLetters.c Reads from standard input and writes to standard output, converting all letters to upper case + SpawnEchoShiftLetters.c Uses spawnProc (the function at the heart of POpen) to run EchoShiftLetters, write some data to its standard output and read back from the standard output and standard error streams. It displays the data read back. This program works fine. What this demonstrates is that the basic Win32 API calls are working as expected, and that the problems encountered previously are probably to do with the Haskell-to-C interface, or the Hugs library routines that create I/O streams from file descriptors. My next step, when I get more time, is to try a simple Haskell program spawning the EchoShiftLetters program -- I'm expecting that to fail. There's one other datum: I attempted to build these test programs using the MinGW gcc tools, but got an undefined symbol error (I think it was WinMain) when building the SpawnEchoShiftLetters program. So I reverted to using the old MS Developer Studio tools. I think it was probably just a library missing from the build, but can't be sure of that. The code for all this can be found at [2]. #g -- [1] http://www.haskell.org//pipermail/libraries/2004-February/001700.html [2] http://www.ninebynine.org/Software/HaskellUtils/Win32/ ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0