- Libraries - Haskell.org

Network.URI - RFC2396bis nearing last call
by Graham Klyne 23 Apr '04

23 Apr '04

The revision of RFC2396 is nearing last call (for IETF "draft standard" status), and after some discussion of details I've made some changes to my (re)implementation of Network.URI (these affect some abnormal cases when calculating a URI from base + relative URIs, where the relative URI uses more '..' components than the base URI has path components). I've also prepared a revised version of the test module that is driven by an external RDF/N3 description of the, constructing the HUnit test cases "on the fly", then executing them. (It's a bit slow, but that's because my RDF graph API is still worse than unoptimized.) More info about the test case descriptions can be found via: http://www.ninebynine.org/Software/HaskellUtils/Network/URITestDescriptions… A copy of the the software itself is here: http://www.ninebynine.org/Software/HaskellUtils/Network/ http://www.ninebynine.org/Software/HaskellUtils/Network/URI.hs (currently: $Id: URI.hs,v 1.11 2004/04/21 16:58:34 graham Exp $) I am proposing to replace the existing network.URI module in the library CVS, but I've been holding off until the revised URI spec is stabilized, and also to get some sense of how much disruption would be caused by the change of representation of the URI type. I have found that some Network.HTTP modules did need to be changed to accommodate the new structure (my modified sources are in the same directory as URI.hs, see above). Unless I hear any squeals, I'll plan to actually update the URI module once the RFC2396 revision goes to last call, and it seems clear that there are no major objections to the changes. #g -- ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: #ifdef considered harmful (was: DData)
by Simon Marlow 20 Apr '04

20 Apr '04

On 20 April 2004 11:54, Alastair Reid wrote: >> If FastInt is Int# in GHC, and we want it to be portable, then we >> have to introduce unlifted types & kinds in Hugs and nhc98 too. > > Yes, I was proposing that Hugs and NHC be extended with unlifted > types of some form. I think this is only worth doing if someone can work out whether polymorphic kinds can be supported, perhaps in a restricted way, so that we can define instances of classes for unlifted types. There's a good open research question! Cheers, Simon

1 0

RE: #ifdef considered harmful (was: DData)
by Simon Marlow 20 Apr '04

20 Apr '04

Robert Will writes: > I think what Haskellers (and others) can do in most cases is > to factor out > platform dependent parts to mini-modules which have different > implementations but the same interface. The version of such > a module is > choosen by the path it resides in during the build process. (Simplest > case: the -i option of the compiler.) I have to say, I dislike this approach to conditional compilation. - it puts the conditional in the build system rather than the source code, which means you have to look in the build system to find out what the code means. - it means if I want to ask questions like "hmm, how does this differ from the Windows version?" I have to go find the windows version of the file. - the interface to the module is duplicated, and nothing is checking that all your implementations have the same interface. OTOH, if you want to see a good example of #ifdefs gone wrong, take a look at GHC's native code generator. #ifdef can indeed be misused; that's not a reason to throw it out altogether. Cheers, Simon

8 8

Re: sequences
by Robert Will 20 Apr '04

20 Apr '04

Apologies, I sent this to the wrong list. It should go to Libraries... Robert ---------- Forwarded message ---------- hi Ross and others, On Wed, 7 Apr 2004, Robert Will wrote: > > On Mon, 5 Apr 2004 ross(a)soi.city.ac.uk wrote: > > > To have something concrete to discuss, I've placed a structure based on > > Edison at > > docs: http://www.soi.city.ac.uk/~ross/seq/ > > code: http://www.soi.city.ac.uk/~ross/seq.tar.gz Really, since you have read the comparison of my Abstract Collections with Edison, you should have said one word, why you choose Edison as a basis and not mine. Well, I gues the reason is just that you don't want MPTC and that you're perhaps afraid of all my new terminology while Edisons names sound so familiar. So here is a short argument in favour of my choices: 1. The class "OperationalSequence" in the Abstract Collections is an MPTC that makes no restrictions on the element type. I dubbed it "Operational", because without an equality over Sequences we can't give executable algebraic specifications. It uses MPTC for a debatable reason: to be part of the framework of Abstract Collections. (The source file explains why we can't mix SPTC and MPTC code.) But is that really so bad? MPTC work on all major compilers and no-one doubts they will be in a future standard. Furthermore, since it uses Constructor Classes (just like Edison) there are no ambiguity problems that would involve FunDeps! 2. Also the names are choosen not to be compatible with the past, but to be combatible with the future: the names of the Sequence operations fit well with those of all other Collections. Many names are shared and have the same semantics on all Collections. > PS: Dessy also started with (list-compatible) Sequences and than added the > rest. We should certainly not make that detour on the large scale. with "list-compatible" I mean starting with class members (cons head tail foldr foldl...) and then add many more. Really one should be looking for the common base of all sequence implementations and what's more all sequence applications. The absurdness of the "list-compatible" approach shows in the ridiculous default running times for 'cons' O(1) and 'snoc' O(n), really what's the big difference between those operations? The names alone are a nightmare: (cons snoc init tail head last left right) (as in lview, rview) and many functions that only work from the front. How many different names should we have for the front (with the first element) and the back (with the last element)? My proposal shows that those four terms (first last front back) suffice to name all useful functions on lists. Surely the naming approach taken for my Abstract Collections is no fundamental breaking with conventions: all the names and operators are either tradition in Haskell or tradition in Scheme or some consistent extension of this (e.g. (<:) and (>:) for 'add_first' and 'add_last'). Clearly my new names are easier to learn for novices, but I also claim that learning the whole library (i.e. the "compatible" functions and the new ones) is easier for the Abstract Collections than for Edison. Just because the names are more consistent, and still many names are like in standard Haskell. So I'd suggest, that a standard Sequence class should be based on the Abstract Collections. (And by the way, why not also think about Sets and Maps, you can use them now: "import Prelude (); import Collections" is not so hard to write!) By the way I think that the documentation for the Sequence instances in Ross' proposal is too redundant. The only thing we should need is a specification of the performance and of additional operations. I would propose the following time bounds: Defaults for Sequences: O(logN) for all operations, except O(1) for "atomic queries" (is_empty, first, last, size (or length)) This is the simplest to remember and a "democratic" implementation will just have those bounds. (And balanced tree does, Dessy has five of them.) Next thing needed are Deques: O(1) for (empty single <: >: first last but_first but_last is_empty) O(N) for the rest (JoinLists are like that with additional O(1) (++), so they're perhaps better called 'AppendableDeques'. Likewise CatenableLists are really AppendableStacks.) Write-only Sequences: (OrdList) O(1) for (empty single <: >: ++) O(N) for the rest One-side flexible Arrays or Random Access lists: are another very "algorithmic" structure, which support efficient 'update', a function that my Sequences don't even specify. This reminds me, that I haven't really seen any applications of Sequence data structures and that I decided anyway to get some examples before fixing the details of the class. By the way, there are already some examples of Maps and Sets at work: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/examples/ The only examples for Sequences is Okasakis Tree Enumeration using Deques and that doesn't look nice without views :-( Robert _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

3 6

RE: #ifdef considered harmful (was: DData)
by Simon Marlow 20 Apr '04

20 Apr '04

On 19 April 2004 15:06, Jan-Willem Maessen - Sun Labs East wrote: > The real problem, of course, isn't the data structures at all---GHC > does an excellent job with these (though the "UNPACK" pragma is a > revelation). The actual problem is function arguments. GHC can't do > worker-wrapper unless a function is strict. Often we end up with > something like this: I'm not sure I'd characterise that as "the real problem" - in a lot of the cases I've come across, the UNPACK pragma has been exactly what I needed. In a few critical functions where I found that arguments weren't strict enough, I've had to add seqs to help the compiler. > data Tree a = Branch !Int a (Tree a) (Tree a) > > lookfor :: Int -> Tree a -> Maybe a > lookfor Leaf key = Nothing > lookfor (Branch k v l r) key > | key==k = Just v > | key < k = lookfor l key > | otherwise = lookfor r key > > Here we don't use "key" in the first clause, so GHC isn't allowed to > unbox. Most of the uses of Int# that I've seen in library code have > been workarounds to this problem. In this case, being able to write > > lookfor :: FastInt -> Tree a -> Maybe a > > might give us some hope of getting the compiler to generate the > unboxed code we might want, yet still afford us the opportunity to > use boxed types if that's not possible. > > We could do this today without changing the language or the compilers. > The library would have to be carefully coded... I'm not clear on exactly what the FastInt type means. I think I asked Alastair the same question recently - is FastInt an unlifted type? Can I store it in a polymorphic data structure or pass it to a polymorphic function? If FastInt is Int# in GHC, and we want it to be portable, then we have to introduce unlifted types & kinds in Hugs and nhc98 too. Declaring instances of classes for unlifted types isn't possible, so you can't have instane Num Int#, for example. I think you need polymorphic kinds for that. Cheers, Simon

2 1

Re: #ifdef considered harmful (was: DData)
by Jan-Willem Maessen - Sun Labs East 20 Apr '04

20 Apr '04

Jan-Willem Maessen - Sun Labs East wrote: Simon Marlow wrote: >> Hmm, wouldn't it be nice to have a "FastInt" library which re-bound >> the appropriate types and functions? Haskell libraries are >> chock-a-block with instances of "#ifdef __GHC__" which define things >> in terms of Int# instead of Int. We could simplify all those >> libraries if we did it just once, in one place. >> >> The problem, of course, is that the naive non-GHC user could write a >> library which used "FastInt" polymorphically, and write code that >> wasn't portable to GHC. I don't think there's an easy, magic >> solution there. Perhaps such a library would be named >> FastIntWhichIPromiseToTestWithGHC. > > > > Most of the time it's unnecessary to use an explicit Int#. If your Int > is in a data structure, you can use > {-# UNPACK #-} !Int > > which is portable, and compiles to an unboxed Int in GHC >= 6.2. The real problem, of course, isn't the data structures at all---GHC does an excellent job with these (though the "UNPACK" pragma is a revelation). The actual problem is function arguments. GHC can't do worker-wrapper unless a function is strict. Often we end up with something like this: data Tree a = Branch !Int a (Tree a) (Tree a) lookfor :: Int -> Tree a -> Maybe a lookfor Leaf key = Nothing lookfor (Branch k v l r) key | key==k = Just v | key < k = lookfor l key | otherwise = lookfor r key Here we don't use "key" in the first clause, so GHC isn't allowed to unbox. Most of the uses of Int# that I've seen in library code have been workarounds to this problem. In this case, being able to write lookfor :: FastInt -> Tree a -> Maybe a might give us some hope of getting the compiler to generate the unboxed code we might want, yet still afford us the opportunity to use boxed types if that's not possible. We could do this today without changing the language or the compilers. The library would have to be carefully coded... -Jan-Willem Maessen

3 3

RE: aha! file descriptor leak in 'readFile'
by Simon Marlow 20 Apr '04

20 Apr '04

On 19 April 2004 08:32, John Meacham wrote: > I have finally tracked down a test case which results in the file > descriptor leak which has plauged one of my programs since its birth. > > this code: > sequence (replicate 100 $ handle (\_ -> return "") ( readFile ".")) > > will leak 100 file descriptors, apparently, after a > Fail: .: openFile: inappropriate type (is a directory) > exception from readFile, the file descriptor will not be closed, and > instead be left open til the end o' time. > > it took me a long time to find because I thought the bug was in > the listing of my directories, not the readFile's of its contents > (including "." and ".."). Yes, that's a bug. Now fixed. Cheers, Simon

1 0

aha! file descriptor leak in 'readFile'
by John Meacham 19 Apr '04

19 Apr '04

I have finally tracked down a test case which results in the file descriptor leak which has plauged one of my programs since its birth. this code: sequence (replicate 100 $ handle (\_ -> return "") ( readFile ".")) will leak 100 file descriptors, apparently, after a Fail: .: openFile: inappropriate type (is a directory) exception from readFile, the file descriptor will not be closed, and instead be left open til the end o' time. it took me a long time to find because I thought the bug was in the listing of my directories, not the readFile's of its contents (including "." and ".."). John -- John Meacham - ⑆repetae.net⑆john⑈

1 0

RE: #ifdef considered harmful (was: DData)
by Simon Marlow 16 Apr '04

16 Apr '04

On 16 April 2004 12:26, Alastair Reid wrote: > What I'd like to see is a general facility for defining strict types. > That is, types whose values will never be thunks so let binding > causes evaluation (as in ML) and use as a subexpression (which is not > under a lambda) causes evaluation (as in ML). The GHC syntax seems > too restrictive for this. Maybe something like this: > > strict_data Int# = Int# Int -- declare a strict Int type > > The typechecking issues would be the same as for GHC's unboxed types: > there are two kinds of typevar * and # and never the twain shall > meet. (I think GHC plays some neat tricks to ease the pain of this > restriction?) Yes, GHC has a separate kind for unlifted types. Unlifted types have kind #, so you can't pass something of unlifted type to a polymorphic function or store it in a polymorphic data structure, because ordinary type variables have kind *. I think there's a small superkind relationship, so kind *# is a superkind of both * and #, which is useful for things like the return type of 'error'. Do you want your strict types to be truly unlifted? GHC could usefully take advantage of that knowledge. > A semantically correct (but maybe a bit slow) implementation would be > easy enough: > > 1) let-bind all strict non-atomic subexpressions. > 2) float strict variable bindings out to nearest enclosing lambda > (float out any lazy variable bindings if required) > 3) Use 'seq' to force all the strict var thunks. > > For example: > > insert :: a -> (Int#,[a]) -> (Int#,[a]) > > insert x (cnt,xs) = (cnt+1,x:xs) > ===> > insert x (cnt,xs) = let cnt'=cnt+1 in seq cnt' $ > (cnt',x:xs) You have some kind of implicit coercion between Int and Int#. How does the type system work here? In GHC you can't put Int# in a pair, of course. Cheers, Simon

1 0

DData
by JP Bernardy 16 Apr '04

16 Apr '04

Hello everyone, After a month or so spent on stabilizing DData, I think I've reached a point where it is hopefully acceptable for everyone. In any case, I don't feel like I can make it much better (within the self-imposed restrictions). Therefore, I hereby submit it to the people in charge of the hierarchical libraries, for integration. Of course, if any specific detail deserves work, I remain available. The code/doc is at the usual url: http://users.skynet.be/jyp/DData/doc/ http://users.skynet.be/jyp/DData/ddata.tar.gz Thank you all for your feedback, Cheers, JP. __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

18 40