December 2003 - Haskell

RE: type classes, superclass of different kind
by Niklas Broberg 11 Dec '03

11 Dec '03

Robert Will wrote: >Now I would like to have Collection to be a superclass of Map yielding the >following typing > > reduce :: (Map map a b) => > ((a, b) -> c) -> c > -> map a b -> c > >Note that in an OO programming language with generic classes (which is in >general much less expressive than real polymorphism), I can write > >class MAP[A, B] inherit COLLECTION[TUPLE[A, B]] > >which has exactly the desired effect (and that's what I do in the >imperative version of my little library). > >There seems to be no direct way to achieve the same thing with Haskell >type classes (or any extension I'm aware of). Here is a quesion for the >most creative of thinkers: which is the design (in proper Haskell or a >wide-spread extension) possibly include much intermediate type classes and >other stuff, that comes nearest to my desire? I don't know if I qualify as the most creative of thinkers, but I have a small library of ADSs that you may want to look at, it's at http://www.dtek.chalmers.se/~d00nibro/algfk/ I recall having much the same problem as you did, my solution was to make maps (or Assoc as I call them) depend on tuple types, i.e. (somewhat simplified): class (Collection c (k,v), Eq k) => Assoc c k v where lookup :: k -> c (k,v) -> v [...many more member functions here...] This means that the type constructors for maps and collections have the same kind (* -> *), which makes it possible for me to say that an Assoc is actually also a Collection. A lot more info to be found off the link. >I believe this question to be important and profound. (We shouldn't >make our functional designs more different from the OO ones, than they >need to be.) If I err, someone will tell me :-> No need to recreate all the stupid things the OO world has come up with, better to do it correctly right away... ;) /Niklas Broberg, d00nibro[at]dtek.chalmers.se _________________________________________________________________ The new MSN 8: advanced junk mail protection and 2 months FREE* http://join.msn.com/?page=features/junkmail

1 0

Abstract Data Structures
by Robert Will 11 Dec '03

11 Dec '03

hi, Abstract Data Types plus Data Structures gives Abstract Data Structures. Divide by Conquer is a technique that every Computer Science Undergraduate learns: to sort a listm sort each of its halves then merge. This is what I call "Computational Divide and Conquer" and it is an important algorithm design strategy. Algorithm Design and Programming were once considerd the same and they were the heart of Computer Science. Nowadays, we get our algorithms from libraries and are instead faced with the complexity of programming applications. It is essential that we divide our programs into smaller parts and specify the contracts between those parts. This is what I call "Informational Divide and Conquer". (The words "informational" vs "calculational" go back to Dijkstra who said that a refinement step is good if it makes either "computational or informational progress". The former meaning decrease a loop or recursion variant, the latter meaning to get simpler assertions. I believe that the Art or Science or whatnot of Programming will make a leap forward, when it learns to profit from Dijkstras heritage.) -- Abstraction in Programming firmly rests on the separation -- of Specification and Implementation. Implementations in functional -- languages have always been on a "higher level", many of them -- serving as their own specifications. (Just take a look into -- Haskell's Prelude and try to specify one of the functions.) Due to -- take higher-level of built-in abstraction, they have resisted for a -- long time the use of programmer-defined abstraction, that is, the -- separation of Specification and Implementation. (Which is by the -- way also the basis of well-used polymorphism.) The main data -- structure of the Haskell programmer is still the same as the one -- from the first functional language in 1958. This file might -- convince the reader that a good functional language should have -- more to offer. http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/AlgebraBasic.hs I have always considered it an advantage that almost all of the Prelude functions are there own specifications. If you had a question, just go ask the code. This approach, however, doesn't scale. If we want to include other data structures than functional stacks into a library (or how did you call that structure with the basic axioms head (x : xs) = x tail (x : xs) = xs ?) we must also include abstraction. I don't know why I write such philosphical stuff, actually I only wanted to annouce my little project and ask for comments: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/ Anyway, it doesn't hurt to remind every now and then. I would especially like interested people to have a look at AlgebraBasic.hs which I think is quite evolved and even already contains the words "standard proposal". Robert

3 2

Re: Parsing HTML
by andrew cooke 10 Dec '03

10 Dec '03

Thanks - you should have replied to the list, because I think I did your package a dis-service. I've just been looking at the Haskell XML Toolbox, and comparing the two, and now that I understand a little more it seems like either will be fine for me. In fact I will copy this to the list, hope that's OK, because maybe someone will find this info via Google one day and find it useful. Cheers, Andrew Malcolm Wallace said: > "andrew cooke" <andrew(a)acooke.org> writes: > >> - HaXml looks like it might do what I want, but >> (1) seems tricky to install (needs "make", which isn't that cool for >> Windows); > > Until the general Haskell Library Infrastructure project is > sufficiently mature, I'm afraid 'make' is going to be pretty > de rigeur for any build-from-source library. > > Having said that, in the case of HaXml I reckon it would be pretty > straightforward to dispense with 'make' and issue a couple of 'ghc > --make' commands by hand. Especially since you seem only to want a > few of HaXml's facilities, not the complete set. > > Another alternative is simply to copy the small number of modules > you need into your local build tree, and ignore the standard package > mechanism altogether. > >> (2) has a load of fancy-schmancy combinator stuff, when all I want is a >> stream of tokens (something like the Java SAX interface); > > If you really want only a stream of tokens, have a look at > Text.XML.HaXml.Lex. For an error-correcting parse into a generic > tree-like XML data structure, use Text.XML.HaXml.Html.Parse. You don't > need the Combinators, Haskell2Xml, Xml2Haskell stuff at all. > >> (3) doesn't seem that solid on the basics >> (doesn't seem to handle namespaces (maybe they appear as part >> of the attribute name?) > > Namespaces are transparent, in the sense that the namespace is part > of the element or attribute name, but there is no further automatic > processing of it. So basically HaXml doesn't do anything fancy with > namespaces, but it doesn't crash, or discard them either. > >> (and I haven't yet worked out what it does about >> other "esoteric" things like character entities, XML declarations, >> CDATA, >> comments, etc)). > > All of these are stored in the 'generic' XML data structure > representation, so you can use them or discard them as you wish. > > data Element = Elem Name [Attribute] [Content] > type Attribute = (Name, AttValue) > data Content = CElem Element > | CString Bool CharData -- bool is whether whitespace > is significant > | CRef Reference -- character and entity references > | CMisc Misc -- comments, processing instructions, > etc. > > >> (No offense implied - it's a cool piece of work, just >> doesn't seem to be what I'm looking for; > > None taken. I'm sure it looks complicated from the outside, but > really it is just a collection of individual pieces that can be > mixed and matched to suit the needs of any particular application. > >> I'd write it myself, but (X)HTML is deceptively complex, ... >> HTML isn't XML, > > HaXml's special error-correcting HTML parser deals with most of this > stuff, for instance self-closing tags (IMG), implicitly closed tags (P), > improperly nested tags, and so on. > >> typical malformed pages (unescaped "<" in text; unescaped data in >> URLs inside links (eg "&"), etc) > > These two examples of error situations might be beyond the current > capability of the error-correcting parser, but I haven't checked in > a long while. > > So in summary, I think HaXml will get you a long way towards your > goal, but you will probably want to be selective about what you use, > and there may be extra things you need to code for yourself on top. > > Regards, > Malcolm > > -- personal web site: http://www.acooke.org/andrew personal mail list: http://www.acooke.org/andrew/compute.html

1 0

RE: Why are strings linked lists?
by Simon Marlow 10 Dec '03

10 Dec '03

> On Sat, Nov 29, 2003 at 11:10:57AM -0500, Wojtek Moczydlowski wrote: > > > > (though it still bothers me that I don't have an answer yet to the > > memory leak I posted some time ago) > > If you are talking about StateT space leak, then I think I have given > you an answer. My guess was that it is a CAF leak. GHC doesn't have CAF leaks. Next guess :-) Cheers, Simon

9 10

Parsing HTML
by andrew cooke 10 Dec '03

10 Dec '03

What are the options for parsing/lexing (X)HTML? As far as I can see... - the HTML library in GHC (or from Andy Gill) is for creating documents, not parsing them - HaXml looks like it might do what I want, but (1) seems tricky to install (needs "make", which isn't that cool for Windows); (2) has a load of fancy-schmancy combinator stuff, when all I want is a stream of tokens (something like the Java SAX interface); (3) doesn't seem that solid on the basics (doesn't seem to handle namespaces (maybe they appear as part of the attribute name?) (and I haven't yet worked out what it does about other "esoteric" things like character entities, XML declarations, CDATA, comments, etc)). (No offense implied - it's a cool piece of work, just doesn't seem to be what I'm looking for; this is all from reading the docs and api rather than looking at code, so I may be mistaken). - nothing else on the haskell.org page appears to do parsing. I'd write it myself, but (X)HTML is deceptively complex, in my experience. You start of thinking it's going to be trivial (S-expressions), then you realise that there HTML isn't XML, then there are character entities, weird CDATA things, namespaces, that what you have isn't robust enough to parse typical malformed pages (unescaped "<" in text; unescaped data in URLs inside links (eg "&"), etc) that are accepted by browsers, etc. Maybe that's why there doesn't seem to be anything?! (I'm writing a simple tool that generates web pages from templates; the tool data appears in attributes with a namespace (this is the standard trick for mixing code generation with HTML in a way that web authoring tools can parse). Hence the mix of requirements for HTML and XML.) Cheers, Andrew -- personal web site: http://www.acooke.org/andrew personal mail list: http://www.acooke.org/andrew/compute.html

1 1

Why are strings linked lists?
by Robert Will 10 Dec '03

10 Dec '03

hi, In relation to my other message, I can contribute to this question. I think it is very important and useful to consider Strings as Sequences of Characters. And independently of the issue discussed elsewhere -- whether Characters should be a type or a class -- I am asking whether Sequences should be "linked list", that is functional stacks in Haskell. (Stacks because cons, head, tail are primitive.) > 1. Today I spend a few hours trying to track down a memory leak. It > turns out I just didn't realize how much space a string takes up. > On my machine "replicate 5000000 'a'" will use 90MB of space! Of course, Packed Arrays will not really change this, but any implementation of Sequences, where ++ doesn't copy its first argument will. In Dessy's standard implementation the above will only use a few bytes... http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/ > 2. They are extremely slow for most operations like writing to disk, > adding something to the end, concatenation, etc. Again, while PackedArrays can't do all of that better, there are a purely functional data structures, that can. I estimate that 99% of all uses of Sequence will work fine with the standard implementation or with Deques, found on the same page above. > 3. They make learning Haskell harder. Why is 'last' so much slower than 'head'? Why is 'head' not called 'first'? Why does 'but_last' (aka init) copy the list, but 'but_first' (aka tail) does not? The question is whether we want to teach abstraction or stack programming... Robert

3 2

[CfP] PAPP 2004 - DEADLINE EXTENSION
by F. Loulergue 09 Dec '03

09 Dec '03

================================ DEADLINE EXTENSION: December, 22 + JOURNAL PUBLICATION ================================ Workshop on Practical Aspects of High-level Parallel Programming (PAPP 2004) part of The International Conference on Computational Science June 7-9, 2004, Kraków, Poland AIMS AND SCOPE Many applications of computing require performance levels attainable only on parallel architectures. Such systems are now readily available as their price/performance ratio continues to improve. The rapid development of affordable hardware for parallel computing makes the need to develop high-quality parallel software increasingly urgent. Sequential programming has long benefited from high-level programming techniques and tools that have made today's immense range of software economically viable. Two decades of research into high-level parallel programming (algorithmic skeletons, parallel extensions of functional languages, such as Haskell and ML, or parallel logic and constraint programming, parallel execution of declarative programs such SQL queries, etc.) has produced methods and tools that improve the price/performance ratio of parallel software, and broaden the range of target applications. Several emerging domains, such as Grid Computing, are currently raising new issues. GRIDs offer tremendous computing power. Nevertheless, this power is far from being effectively exploited. In addition to technical problems related to portability and access, Grid computing needs new programming paradigms. The PAPP workshop focuses on practical aspects of high-level parallel programming: design, implementation and optimization of high-level programming languages and tools (performance predictors working on high-level parallel/grid source code, visualisations of abstract behaviour, automatic hotspot detectors, high-level GRID resource managers, compilers, automatic generators, etc.), applications in all fields of high-performance computing, benchmarks and experiments. Research on high-level grid programming is particularly relevant. TOPICS We welcome submission of original, unpublished papers in English on topics including: high-level programming models and tools for GRID computing high-level parallel language design, implementation and optimisation functional, logic, constraint programming for parallel, distributed and Grid systems algorithmic skeletons and high level parallel libraries generative (e.g. template-based) programming with algorithmic skeletons and high level parallel libraries applications in all fields of high-performance computing (using high-level tools) benchmarks, experiments using such languages and tools PAPER SUBMISSION AND PUBLICATION Prospective authors are invited to submit full papers in English presenting original research. Submitted papers must be unpublished and not submitted for publication elsewhere. Papers will go through a rigorous reviewing process. Each paper will be reviewed by at least two referees. The accepted papers will be published in the Springer-Verlag LNCS series, as part of the ICCS proceedings. Papers (PDF file) should be sent to loulergue(a)univ-paris12.fr with subject "[PAPP Workshop] Submission" no later than Monday 22 December 2003. We invite you to submit a full paper of 6 to 10 pages (A4), describing new and original results. The submitted paper must be formatted according to the rule of Lecture Notes in Computer Science (LNCS). Submission implies the willingness of at least one of the authors to register and present the paper. An early email with your intention to submit a paper would be greatly appreciated (especially if you have doubts about the relevance of your paper). JOURNAL PUBLICATION Accepted papers should be presented at the workshop and extended and revised versions will be published in a special issue of the international journal Parallel and Distributed Computing Practices, Nova Science Publishers (provided revisions suggested by the referees are made). DATES December 22, 2003 Full paper due January 14, 2004 Notification Februray 10, 2004 Camera-ready paper due PROGRAMME COMMITTEE Rob Bisseling (Univ. of Utrecht, The Netherlands) Matthieu Exbrayat (Univ. of Orléans, France) Sergei Gorlatch (Univ. of Muenster, Germany) Clemens Grelck (Univ. of Luebeck, Germany) Kevin Hammond (Univ. of St. Andrews, UK) Zhenjiang Hu (Univ. of Tokyo, Japan) Frederic Loulergue (Univ. Paris Val de Marne, France) Quentin Miller (Miller Research Ltd., UK) Susanna Pelagatti (Univ. of Pisa, Italy) Alexander Tiskin (Univ. of Warwick, UK) Chair and Organizer Dr. Frédéric LOULERGUE Laboratory of Algorithms, Complexity and Logic (LACL) University of Paris Val de Marne 61, avenue du Général de Gaulle F-94010 CRÉTEIL - FRANCE

1 0

Forthcoming GHC 6.2 release
by Graham Klyne 09 Dec '03

09 Dec '03

I noticed your comment about the forthcoming GHC 6.2 release... Some time ago there was discussion of allowing alternative module names for containing the "main" function of a program, which I'm hoping to see in 6.2, per [1]. Are you expecting to release very soon? #g -- [1] http://www.haskell.org/pipermail/haskell/2003-June/012153.html ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: Why are strings linked lists?
by Simon Marlow 09 Dec '03

09 Dec '03

> > GHC 6.2 (shortly to be released) also supports toUpper, toLower, and > the > > character predicates isUpper, isLower etc. on the full Unicode > character > > set. > > > > There is one caveat: the implementation is based on the C library's > > towupper() and so on, so the support is only as good as the > C library > > provides, and it relies on wchar_t being equivalent to Unicode (the > > sensible choice, but not all libcs do this). > > Now, why would one want to base this on C's wchar_t and its > "w" routines? Because it's easy, and it's still an improvement over what we had before. > wchar_t is sometimes (isolated) UTF-32 code units, > including in Linux, sometimes it is (isolated) UTF-16 code units, > including in Windows, and sometimes something utterly useless. Yes, I mentioned this above. > Please instead use ICU's UChar32, Thanks, I didn't know about ICU - it looks nice. I did briefly investigate libunicode, which turned out to be worse than the C library. Cheers, Simon

1 0

How do I sleep in Ghc?
by Ben_Yu＠asc.aon.com 09 Dec '03

09 Dec '03

Hi there, In Ghc, how do I sleep for say, 1 minute? I'm trying to write a simple file arrival listener and could not find the sleep api. Can haskell do it at all? Thanks. Ben. This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.

5 4