- Libraries - Haskell.org

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

12 Mar '04

> > I did not follow the Edison guidelines, nor the GHC "guidelines". > > I tried different variations but in the end I sticked to the > > most consistent set I could think of: > > > > 1) The structure (i.e. Map, Set, Queue) is always the last argument. > > 2) All operations are left-biased. > > > > I noticed that the last point is rather important, it means that > > "insert key x map" will replace the current value of "key" with "x" > > if it is already present, and that "union map1 map2" will prefer > > elements of "map1" instead of "map2". > > Just as a matter of personal preference, I find a right bias > to be more > intuitive. Also, if the map argument comes first in 'insert > map key x', > then partial application is more likely to be useful (you're > more likely > to be inserting several things in the same map, rather than the same > thing in several maps). oops, I don't really mean "inserting several things in the same map", I mean "looking up several keys in the same map", i.e. it makes sense for the map argument to lookup to come first. Cheers, Simon

2 1

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

11 Mar '04

Hi Daan, >> Set.toAscList is not really necessary as it is the same as Set.toList. > > Not necessarily: the lists from Set.toList will be equal for equal > Set's, but may be unordered. Use "toAscList" or "toDescList" if you > want an ordered variant. That really surprises me. I think that toList must return a sorted list (to properly abstract the Set data type), and anything unsorted should only be for debugging purposes. >> The functions Set.fromAscList and Set.fromAscDistinctList should be >> marked as "unsafe" > > I think so too, although I like "unchecked" better? Good, I agree. >> Map.keySet = Set.fromDistinctAscList . Map.keys > Yes, we could do that -- but the circular dependency is terrible, and a > wrapper module > would need to look at the internal representation of Map/Set :-( I don't see the circular dependency. Map imports Set (but not vice versa?). In any case, I would prefer a wrapper (possible revealing some more "unchecked" functions). Christian

3 3

Re: [Haskell] Re: RFC: DData in hierarchical libraries
by Daan Leijen 11 Mar '04

11 Mar '04

On Thu, 11 Mar 2004 09:56:45 +0100, Johannes Waldmann <waldmann(a)imn.htwk-leipzig.de> wrote: > * nice work. I might start using it (instead of Data.FiniteMap) > just because the function names look better :-) Thanks. > * 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 did not follow the Edison guidelines, nor the GHC "guidelines". I tried different variations but in the end I sticked to the most consistent set I could think of: 1) The structure (i.e. Map, Set, Queue) is always the last argument. 2) All operations are left-biased. I noticed that the last point is rather important, it means that "insert key x map" will replace the current value of "key" with "x" if it is already present, and that "union map1 map2" will prefer elements of "map1" instead of "map2". Note that the GHC FiniteMap implementation is ambigious about its bias and the bias is documented per function (note: a thing that may bite us in particular is that GHC "plusFM" is right-biased and can thus not be replaced by DData "union" with a search-and-replace.) However, I do not have a strong opinion about this and maybe the Edison guide lines are better. However, I do believe that a "bias" rule like (2) is very important when you are using the library. A strong rule like (1) is maybe less convenient for fulltime users (especially in the context of partial applications), but much easier for sporadic users. > * types: some functions are not declared at their most > general type (I checked by commenting out the decl. and asking ghci) This was by purpose, for example: > difference :: forall a1 k a. > (Ord k) => > Map k a1 -> Map k a -> Map k a1 It is kind of strange to take the difference between to maps with different elements, so I thought it better to disallow that situation. However, it is a bit 1984 to disallow it, and I may be wrong here. All the best, Daan.

2 1

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