- Libraries - Haskell.org

RE: Instances for data types
by Simon Marlow 01 May '04

01 May '04

On 27 April 2004 20:58, Sven Panne wrote: > Playing around with System.Posix.Terminal, I realized that there are > no Read, Show, Eq, Enum, ... instances for the data types defined > there (TerminalState, TerminalMode, ...). This is not a very > difficult problem to solve in one's > own program, but it's not very handy, either. By all means go ahead and add these instances. > This raises a general > question: What instances should be defined in the standard libraries > for types like > this? A general policy would be a good thing. IMHO, at least Read, > Show, Typeable and Eq could be expected, having Ord, Enum and > Bounded, too, would be nice. Good point. I've been meaning to create a separate document so we have somewhere to collect general library policies like this. It's on my whiteboard... Cheers, Simon

4 3

Instances for data types
by Sven Panne 27 Apr '04

27 Apr '04

Playing around with System.Posix.Terminal, I realized that there are no Read, Show, Eq, Enum, ... instances for the data types defined there (TerminalState, TerminalMode, ...). This is not a very difficult problem to solve in one's own program, but it's not very handy, either. This raises a general question: What instances should be defined in the standard libraries for types like this? A general policy would be a good thing. IMHO, at least Read, Show, Typeable and Eq could be expected, having Ord, Enum and Bounded, too, would be nice. Any opinions? Cheers, S.

1 0

request: MultiMap
by haskell＠alias.spaceandtime.org 26 Apr '04

26 Apr '04

Hello, I would like to request that multimap be added to the data library. As a C++ programmer (and a complete Haskell newbie), I find myself frequently using std::multimap from the STL. However, as I'm moving my programs to Haskell, I'm having to do hacks such as a maps of keys to sets of values. I noticed that DData is under consideration, which has a multiset, so why not a multimap? I would implement it myself, but as I said, I am just learning FP. Thanks, James

2 2

Re: UTF-8 encode/decode libraries.
by Sven Panne 26 Apr '04

26 Apr '04

Duncan Coutts wrote: > On Mon, 2004-04-26 at 18:49, David Brown wrote: [...] > toUTF :: String -> String Hmmm, "String -> [Word8]" would be nicer... > fromUTF :: String -> String ... and here: "[Word8] -> String" or "[Word8] -> Maybe String". Furthermore, UTF-8 is not restricted to a maximum of 3 bytes per character, here an excerpt from "man utf8" on my SuSE Linux: * UTF-8 encoded UCS characters may be up to six bytes long, however the Unicode standard specifies no characters above 0x10ffff, so Unicode characters can only be up to four bytes long in UTF-8. IIRC we discussed encoders/decoders quite some time ago on the libraries mailing list, but nothing really happened, which is a pity. We should strive for something more general than UTF-8 <-> UCS/Unicode, there are quite a few more widely used encodings, e.g. GSM 03.38, etc. Any takers? Cheers, S.

2 1

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