- Haskell - Haskell.org

Call for Contributions - HC&A Report (May 2004 edition)
by Arthur van Leeuwen 14 Apr '04

14 Apr '04

Dear Haskellers, two changes of season and one of editor later, we strongly suspect the Haskell community has also moved along admirably. Thus comes the need to refresh our list of all things Haskell, and give *you* the opportunity to tell all the world about your passion. We invite your contributions to the imminent sixth edition of the ================================================================ Haskell Communities & Activities Report http://www.haskell.org/communities/ Submission deadline: 7 May 2004 (please send your contributions to hcar(a)haskell.org, in plain ASCII or LaTeX format) ================================================================ The Haskell Communities & Activities Reports biannually report on the state of Haskell over the last 6 months, and sometimes on plans for the next 6 months. If you have only recently joined the Haskell world, browse the November 2003 edition -- you will find an overview of what's going on as well as starting points and links that may provide many answers. We would much like you to send your contributions in by the first week of May, and will then endeavor to publish the collective report roughly a month before the start of summer. Note that this is a great opportunity to gauge the state of your research, update your web pages, release new versions, announce entirely new projects, summarize developments in sub-communities for every Haskeller to see, etc. :) The way we like to do things is have you update all existing summaries, as the purpose of these reports is to show *recent/current* activities. We will drop any topics that haven't had any activity since May 2003, so if you haven't updated your topic since then, now is a good time! Ofcourse, if you have new things to share, so much the better. We would love to hear of it, and include it in the report. Please keep your contributions short though, a couple hundred words maximum, as we would like to keep the size of the report reasonable. It is intended as an overview after all. Looking forward to your contributions, Arthur (interim editor, May 2004 edition) ----------------------------------- topics New suggestions for current hot topics, activities, projects, etc. are welcome - especially with names and addresses of potential contacts, but here is a non-exclusive list of likely topics (see also http://www.haskell.org/communities/topics.html ): General Haskell developments; Haskell implementations; Haskell extensions; Standardization and documentation; Haskell tutorials, howtos and wikis; Organisation of Haskell tool and library development; Haskell-related projects and publications; new research, fancy tools, long-awaited libraries, cool applications; Feedback from specialist mailing lists to the Haskell community as a whole; Haskell announcements; all (recent) things Haskell Announcements: if you've announced anything new on the Haskell list over the last six months, you'll want to make sure that is reflected in this edition! Project pings: if you're maintaining a Haskell tool or library or somesuch, you'll want to let everyone know that it is still alive and actively maintained, even if there have been no new additions, but all the more if there have been new developments. Tutorials: if you've fought with some previously undocumented corner of Haskell, and have been kind enough to write down how you did manage to build that graphical user interface, or if you' ve written a tutorial about some useful programming techniques, this is your opportunity to spread the word (short, topic-specific, and hands-on tutorials that only show how to achieve a certain practical task would do a lot to make things easier for new Haskellers - please write some!) Applications: if you've been working quietly, using Haskell for some interesting project or application (commercial or otherwise), you might want to let others know about what you're using Haskell for, and about your experiences using the existing tools and libraries; are you using Haskell on your job? An interesting thread about using Haskell and more generally functional programming for non-Haskell things seems to recur with reasonable frequency - why not write a sentence or two about your use of Haskell for our report? Feedback: if you're on one of the many specialist Haskell mailing lists, you'll want to report on whatever progress has been made there (GUI API discussions, library organisation, etc.) If you're unsure whether a contact for your area of work has come forward yet, have a look at the report's potential topics page, or get in touch with me. I've contacted last time's contributors, hoping they will volunteer to provide updates of their reports, and will update the contacts on the topics page fairly regularly. But where you don't yet see contacts listed for your own subject of interest, you are very welcome to volunteer, or to remind your local community/project team/mailing list/research group/etc. that they really ought to get their act together and let the Haskell community as a whole know about what they've been doing! :-) -------------------------- what should I write? That depends on your topic, but as a general rule, it shouldn't take you long. A simple sentence or two about your use of Haskell could go into the "Individual Haskellers and their projects" section. If you're a company, or if you're working on a project using Haskell as the implementation language, a paragraph on that could go into the "Commercial Applications" and "Non-Commercial Applications" sections. A typical summary report about a tool/library/project/application/.. would be between 1 and 3 paragraphs of ASCII text (what's it about? major topics and results since the last report? current hot topics? major goals for the next six months?) plus pointers to material for further reading (typically to a home page, or to mailing list archives, specifications and drafts, implementations, meetings, minutes,..). For those who prefer templates to fill in, the report is edited in LaTeX, and an entry template might look something like this: \subsubsection{<MYSTUFF>} \report{<MY NAME}\\ <WHAT IS IT?> <WHAT IS ITS STATUS? / WHAT HAS HAPPENED SINCE LAST TIME?> <CAN OTHERS GET IT?> <WHAT ARE THE IMMEDIATE PLANS?> <FURTHER READING> \url{<PROJECT URL>} Browsing through previous editions should give you a good idea of the variety of possibilities, ranging from very brief to extensive. -- Haskell Communities and Activities Report (May 2004 edition) All contributions are due in by the 7th of May 2004! http://www.haskell.org/communities/

1 0

Re: concurrent haskell, higher-order types and parameterizing by typeclass
by oleg＠pobox.com 14 Apr '04

14 Apr '04

> data Showable = forall a. Show a => Showable a > > writer :: Chan Showable -> IO () > writer ch = mapM_ (writeChan ch) [Showable 42, Showable pi, Showable > "hello", Showable 'c'] > > printer :: Chan Showable -> IO () > printer ch = getChanContents ch >>= mapM_ (\(Showable a) -> print a) > > However, this solution requires a new wrapper datatype (or at least a > new constructor) to be defined for every typeclass to be used in > Chan-based communication; furthermore, all of the datatypes will be > identical except for the name of the typeclass. It seems like I > should be able to create a type that's parameterized by typeclass, > i.e. something like: > data Wrapper c = forall a. c a => Wrapper a > writer :: Chan (Wrapper Show) -> IO () We can do the following: > {-# OPTIONS -fglasgow-exts #-} > > import Data.IORef > > data W r = forall a. W a (a->r) > > -- emulate the channel > type Chan a = IORef [W a] > > writeChan ch x = do > c <- readIORef ch > writeIORef ch (x:c) > > getChanContents ch = readIORef ch > > -- Channel is parameterized by the answer type! > writer :: Chan String -> IO () > writer ch = mapM_ (writeChan ch) > [W 42 show, W pi show, W "hello" show, W 'c' show] > > printer :: Chan String -> IO () > printer ch = getChanContents ch >>= mapM_ (\(W a h) -> putStrLn $ h a) > > main = do > ch <- newIORef [] > writer ch > printer ch That is, pack the handler along with the data. The channel is parameterized by the answer type of the handler. Indeed, class Show means that we can apply the function 'show' to any value of the type in that class -- and get a string. If we use the Showable wrapper as in the original code, applying show is _the only thing_ we can do with that value. As we're interested in the answer type anyway (because there is nothing else we can do with the value), we can parameterize the class by the answer type. If we can perform several operations on the value, we can parameterize the channel by a tuple of all answer types. A cynic might remark that all this exercise with existentials is for nothing: Indeed, "W x show" is precisely equivalent to just "show x". Because of the non-strictedness, we can apply (or partially apply) all the handlers to the value in question and pass these applications through the channel. Only the needed ones would be evaluated.

1 0

Announce: Haskell ACID Relational DBMS v0.1
by S. Alexander Jacobson 13 Apr '04

13 Apr '04

In thinking about a data storage model for a web app I wanted to develop, and in finding Haskell so concise and expressive, I wondered if one could write a relational DBMS in Haskell in under 1000 lines of code. The answer appears to be yes! Features: * non-destructive-update Haskell DBMS (can use a relational database without escaping to the IO monad!) * supports user defined types * supports user defined relations and functions * command pattern structure for write-ahead logging * Inner,Outer,Left,Right joins on arbitrary (user-defined) relations (not just "=") * in-memory/in-process means no disk/marshalling overhead Risks include: * functions/aggregates not yet implemented e.g. (a<b+c) or (a<max(b)) * no performance testing -- joins expensive! * no proof of correctness * written by non-academic new haskell developer * Not SQL. No Sockets. -- should be part of the app wrapper used to maintain consistency! * License: GPL Note: I am an expert neither in Haskell, nor in relational databases, nor in relational algebra/set theory/category theory. So comments/suggestions/recommendations on any aspect of this code are welcome. Comment on Haskell: WOW!!!!!! I basically wrote this without testing just thinking about my program in terms of transformations between types. I wrote the test/example code at the end and had almost no implementation errors in the code! The compiler/type-system is really really good at preventing you from making coding mistakes! I've never in my life had a block of code this big work on the first try!!! I am WAYYY impressed. Note: Code working means doing what I think it will do. I might be wrong about relational theory, but that is a separate class of problem. -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com

1 0

[Haskell] concurrent haskell, higher-order types and parameterizing by typeclass
by Abraham Egnor 13 Apr '04

13 Apr '04

I have a system composed of threads communicating via channels; I'd like the communicated types to be instances of a particular typeclass (say Show for purposes of discussion), but not all the same type. Since Chan is paramterized by the communicated datatype, the best way I've found to do this is via a wrapper type: data Showable = forall a. Show a => Showable a writer :: Chan Showable -> IO () writer ch = mapM_ (writeChan ch) [Showable 42, Showable pi, Showable "hello", Showable 'c'] printer :: Chan Showable -> IO () printer ch = getChanContents ch >>= mapM_ (\(Showable a) -> print a) However, this solution requires a new wrapper datatype (or at least a new constructor) to be defined for every typeclass to be used in Chan-based communication; furthermore, all of the datatypes will be identical except for the name of the typeclass. It seems like I should be able to create a type that's parameterized by typeclass, i.e. something like: data Wrapper c = forall a. c a => Wrapper a writer :: Chan (Wrapper Show) -> IO () ... Alternatively, are there any ideas as to how I could communicate heterogeneous instances of a given typeclass in a typesafe manner (i.e. without escaping to Data.Dynamic)? Abe

2 1

RE: [Haskell] overuse of maybe and [] in prelude and libs
by Simon Marlow 13 Apr '04

13 Apr '04

> But, either way, I'm assuming I can't do this > (making up syntax): > > import Data.FiniteMap using MyPrelude as Prelude > > So that every place in FiniteMap that Prelude > functions are called, MyPrelude functions are > called instead? Then I could simply redefine just > and nothing as return and mzero. Not possible with GHC, I'm afraid. At least, not at the moment. We would have to retain a strong separation between Data.FiniteMap and Prelude, such as you would do if the Prelude were dynamically linked, and GHC doesn't do that. Indeed, doing so would probably have a significant impact on performance, because the compiler wouldn't be able to take advantage of any knowledge about the Prelude except for the types of functions when compiling Data.FiniteMap. Cheers, Simon

1 0

haddock/ghc feature request
by Johannes Waldmann 13 Apr '04

13 Apr '04

I have a bunch of (polymorphic) function declarations like foo :: C a => A a -- ^ comment -> B a -- ^ comment foo = ... and haddock does a very fine job on them. but then I wanted (needed) to specialize them, and to avoid duplicating information, I wrote type Foo a = A a -- ^ comment -> B a -- ^ comment foo :: C a => Foo a {-# SPECIALIZE foo :: Foo Int #-} problem is, haddock does not want to parse the comments in the type Foo definition. (I think in case of such errors (malformed annotation), haddock should try to ignore and continue, instead of just give up.) On the other hand, it would be still better if ghc would have something like -fauto-specialize-all (that is, for all instances that are needed for the current `main' definition) so that I wouldn't have to change the source code at all. I vaguely remember there was a preprocessor (independent of ghc, written by someone else) that did "full specialization"? -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- ------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------

1 0

CICLOPS 2004: Second CFP
by Manuel Carro 09 Apr '04

09 Apr '04

[Please accept our apologies if you receive this message several times] --------------------------------------------------------------------------- C A L L F O R P A P E R S CICLOPS 2004 Colloquium on Implementation of Constraint and LOgic Programming Systems to be held at Saint-Malo (France) at the occasion of ICLP'04 September, 2004 http://clip.dia.fi.upm.es/Conferences/CICLOPS-2004 --------------------------------------------------------------------------- Topics of interest ------------------ This workshop aims at discussing and exchanging experience on the design, implementation, and optimization of logic, constraint (logic) programming systems, and systems intimately related to logic as a means to express computations. Experience backed up by real implementations and their evaluation will be given preference, as well as descriptions of work in progress in that direction. Topics include, but are not limited to: * Standard and alternative sequential implementation schemes (e.g., generalization / modification of the WAM, translation to lower-level and/or general-purpose languages, etc.) * Interaction between high-level optimizations / transformations / specialization and low-level issues. * Compile-time analysis and its application to code generation. * Low-level cost models to guide high-level optimizations. * Memory management, indexing, and garbage collection issues. * Balance between compile-time effort and run-time machinery. * Implementation of parallel and concurrent logic and constraint programming systems. * Implementation techniques for declarative programming paradigms with basis on, or extending, logic and constraint programming, such as non-monotonic reasoning, inductive logic programming, etc. * Implementation of systems closely related to, or based on, logic, such as theorem provers and natural language processing systems. * Performance evaluation of logic and constraint programming systems. * User oriented tools for performance evaluation and profiling. * Software design with and for LP/CP systems: components, patterns, etc. * Design and implementation of programming environments. * Experiences from using systems in real-life applications. Important dates --------------- * submission deadline: April 26 * notification of acceptance: May 24 * final version due: June 14 * workshop dates: still to be decided (they depend on the organization of ICLP 2004) Workshop Goals -------------- Our intent is to bring together, in an informal setting, people involved in research on sequential and parallel implementation technologies for logic and constraint programming languages and systems, in order to promote the exchange of ideas and feedback on recent developments. We hope that the workshop will provide a meeting point for people working on implementation technology for different aspects of logic and constraint-based languages and systems. Rationale and History --------------------- The last years have witnessed continuous progress in the technology available both for academic and commercial computing environments. Examples include more processor performance, increased memory capacity and bandwidth, faster networking technology, and operating system support for cluster computing. These improvements, combined with recent advances in compilation and implementation technologies, are causing high-level languages to be regarded as good candidates for programming complex, real world applications. Techniques aiming at achieving flexibility in the language design make powerful extensions easier to implement; on the other hand, implementations which reach good performance in terms of speed and memory consumption make declarative languages and systems amenable to develop non-trivial applications. Logic Programming and Constraint Programming, in particular, seem to offer one of the best options, as they couple a high level of abstraction and a declarative nature with an extreme flexibility in the design of their implementations and extensions and of their execution model. This adaptability is key to, for example, the implicit exploitation of alternative execution strategies tailored for different applications (e.g., for domain-specific languages) without jeopardizing efficiency unnecessarily. This workshop continues a tradition of successful workshops on Implementations of Logic Programming Systems, previously held with in Budapest (1993) and Ithaca (1994), the Compulog Net workshops on Parallelism and Implementation Technologies held in Madrid (1993 and 1994), Utrecht (1995) and Bonn (1996), the Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages held in Port Jefferson (1997), Manchester (1998), Las Cruces (1999), and London (2000), and more recently the Colloquium on Implementation of Constraint and LOgic Programming Systems in Paphos (Cyprus, 2001), Copenhagen (2002), and Mumbai (2003), and the CoLogNet Workshops on Implementation Technology for Computational Logic Systems held in Madrid (2002) and Pisa (2003). Submission Information ---------------------- Authors are invited to submit papers written in English and not exceeding 12 pages. To speed up the process of refereeing, authors are requested to submit their paper in Postscript or PDF form. Hard copies may be sent to the contact address below only if access to electronic media is not available; please contact the organizers beforehand if that is the case. Submissions should contain full return mail and email address (if applicable) and FAX number (if applicable) of the contact author. Prospective authors are kindly requested to first send an indication of interest together with a paper title and abstract, in plain text format, to the organizers at the e-mail address at the bottom of the page. LaTeX style files are available via WWW at the Workshop web site. We strongly encourage their use, both in the preparation of submissions and, specially, for the final version. In order to obtain homogeneous workshop proceedings, authors of accepted papers will be requested to send the sources to the organizers. Authors who wish to prepare papers in formats other than LaTeX are kindly requested to contact the organization beforehand in order to make sure that we have available the right tools to process the files (if needed), or in order to receive detailed format instructions otherwise. Organization ------------ Program Committee: * Manuel Carro (Spain) * Ricardo Lopes (Portugal) * José F. Morales (Spain) * Enrico Pontelli (USA) * Vítor Santos (Brazil) * Tom Schrijvers (Belgium) * Christian Schulte (Sweden) * Paul Tarau (USA) * Neng-Fa Zhou (USA) Workshop Coordinators: Manuel Carro (contact person) José F. Morales http://lml.ls.fi.upm.es/~mcarro http://clip.dia.fi.upm.es/~jfran Phone: +34-91-3367455 Phone: +34-91-3367448 Fax: +34-91-3366595 Fax: +34-91-3366595 Invited Speaker: To be announced Contact Please address any question regarding the workshop organization to the address ciclops-org(a)clip.dia.fi.upm.es -- +---------------------------------------------------------------------------+ |Manuel Carro --- Facultad de Informática -- U. Politécnica de Madrid (UPM) | |mcarro_at_fi_dot_upm_dot_es --- Ph: +34-91336-7455 --- FAX: +34-91336-7412 | |http://lml.ls.fi.upm.es/~mcarro --- http://clip.dia.fi.upm.es/Software/Ciao|

1 0

Re: sequences
by Robert Will 09 Apr '04

09 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

1 0

Re: sequences
by Robert Will 09 Apr '04

09 Apr '04

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

1 0

RE: [Haskell] overuse of maybe and [] in prelude and libs
by Simon Peyton-Jones 09 Apr '04

09 Apr '04

Alex You've become a very sophisticated Haskell programmer! We did at one stage do something like this, by making list comprehensions into monad comprehensions. So [ x*x | x <- xs, pred x] meant the same as do { x <- xs; if pred x then mzero else return (); return (x*x)} But in the next iteration of the language we undid the change, a controversial decision that some still regret. Because naïve users were getting too many perplexing error messages about monads and functors when they thought they were just manipulating lists. Haskell is pretty good about letting you install a different Prelude, so you could try it yourself. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of S. Alexander | Jacobson | Sent: 08 April 2004 04:42 | To: Haskell Mailing List | Subject: [Haskell] overuse of maybe and [] in prelude and libs | | It feels like the Prelude insists on using [] and | Maybe too much. I keep writing things like this: | | foo = foldl union emptySet $ maybe mzero return $ lookup pairs key | goo = maybe emptySet toSomething $ lookup pairs key | | which really should look like this: | | foo = concat $ lookup pairs key | goo = fmap toSomething $ lookup pairs key | | But, even if we don't have a Monadic/Functor Set, | foo should at least be: | | foo = foldl union emptySet $ lookup key | | In other words, shouldn't Prelude define concat | and lookup as: | | concat = foldr mplus mzero -- (Also, see PS) | | lookup key [] = mzero | lookup key ((x,y):xyz) | | key == x = return y | | otherwise = lookup key xyz | | And if it is a fundamental problem adding | constraints to instances, why not add all | automatically derivable classes as constraints to | all the Prelude classes (esp. Monad and Functor!) | and automatically derive instances of all | derivable classes unless the programmer defines | his/own methods. | | -Alex- | | PS Shouldn't concat be defined with foldl and not | foldr? Doesn't foldr imply that you can't concat | infinite lists? (I know this is a FAQ, but | where?) | | _________________________________________________________________ | S. Alexander Jacobson mailto:me@alexjacobson.com | tel:917-770-6565 http://alexjacobson.com | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

3 3