March 2002 - Haskell - Haskell.org

RE: Standard Library report: List union
by Simon Peyton-Jones 17 Mar '02

17 Mar '02

There's a remark at the beginning of 7.2 that says: delete, (\\), union and intersect preserve the invariant that lists don't contain duplicates, provided that their first argument contains no duplicates. The same applies to unionBy etc. This design is one you might reasonably disagree with. I'd have thought it would be more sensible to have the invariant that *both* arguments to union and intersect are assumed to be sets (no dups). But I don't propose to change this now. Simon | -----Original Message----- | From: Jay Cox [mailto:sqrtofone@yahoo.com] | Sent: 05 March 2002 01:51 | To: Jon Fairbairn | Cc: haskell(a)haskell.org | Subject: Re: Standard Library report: List union | | | On Mon, 4 Mar 2002, Jon Fairbairn wrote: | | > The current library report defines unionBy like this: | > | > unionBy eq xs ys = xs ++ deleteFirstsBy eq (nubBy eq ys) xs | > | > why does it take the nub of ys, but not xs? I'd have expected | > | > unionBy eq xs ys = (nubBy eq xs) ++ deleteFirstsBy eq | (nubBy eq ys) | > xs | > | > Jón | | Pure guess, but... (no really!) | | | For the sake of argument, lets define a ulist as a list where | for all elements x in list l, there is no element n with | index not equal to that of x (index being position of the | element in the list) such that eq n x == True. | | In other words every element in a ulist appears only once. | | Suppose you (unionBy eq x y) to get a result. | Suppose also that x is a ulist | A. x is a ulist by argument. | B. the result of (nubBy eq ys), lets call it z, is a ulist. | C. the result of (deleteFirstsBye eq z xs) is a list which | has no elements in common with xs). because (deleteFirstsBy | eq) "deletes" elements and doesnt add,the result is a ulist. | D. Adding new, unique, elements (elements not equal to a | element in the ulist in question) to a ulist results in a | ulist. E. Therefore (unionBy eq x y) is a ulist. | | | Why should this be important? | | what if you wanted to fold the function (unionBy eq) over a | list of lists to get a ulist? Assuming you start with an | initial ulist, by your suggestion you'd be applying (nubBy | eq) to a ulist (generated by the the repeated application | (unionByeq), which would be the same as applying the identity | function to a ulist. (meaning you have essentially one big | nasty no-op)! | | | However, in taking a look at unionBy, one might wonder why it | isnt defined like so (assuming xs would be the accumulated | ulist in the fold. | | | unionBy eq xs ys = (deleteFirstsBy eq (nubBy eq ys) xs) ++ xs | | or maybe better (to mirror (++)) | | unionBy' eq ys xs = (deleteFirstsBy eq (nubBy eq ys) xs) ++ xs | | in using this definition, the number of conses with (:) | should be linear (or less) with with the number of elements | to be added to the first_ulist in the following folds. | | | foldl (unionBy eq) first_ulist list_of_lists | foldr (unionBy' eq) first_ulist list_of_lists | | So, is there aother reason I cannot think of? I'm sure I | haven't covered all bases here. | | Thanks, | | Jay Cox | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

2 1

Isn't this tail recursive?
by Jyrinx 16 Mar '02

16 Mar '02

For practice, I'm playing with reimplementing the solution to the word count problem on the Great Computer Language Shootout (www.bagley.org/~doug/shootout) My current solution looks tail recursive to me: --- snip --- -- wc-luke.hs -- Reimplimentation of the Haskell word count program for the Great -- Computer Language Shootout -- Luke Maurer -- jyrinx(a)mindspring.com module Main where import IO data CharKind = Normal | White | Newline charKind :: Char -> CharKind charKind c = case c of '\n' -> Newline ' ' -> White '\t' -> White _ -> Normal countAll :: String -> (Int, Int, Int) countAll str = countAll' str 0 0 0 0 where countAll' [] _ nl nw nc = (nl, nw, nc) countAll' (c:cs) newWord nl nw nc = case charKind c of -- The following should all be tail calls ... right? Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) White -> countAll' cs 1 nl nw (nc + 1) Newline -> countAll' cs 1 (nl + 1) nw (nc + 1) main = do -- We need a 4K buffer, as per the rules hSetBuffering stdin (BlockBuffering (Just 4096)) file <- getContents let (l, w, c) = countAll file putStrLn ((show l) ++ " " ++ (show w) ++ " " ++ (show c)) --- snip --- In the case expression at the end of countAll, each of the values looks to me like a recursive tail call - I should think (hope?) that it would be optimized by GHC into a goto statement (a la Scheme). Instead, my program eats up memory (I've got 256 MB) until the RTS whines about a stack overflow. Am I wrong about the tail call? Is there some optimization I should be aware of (I'm compiling with -O2)? Is this a flaw in GHC? (BTW, as a beginner, I'd be glad to hear general commentary on my code ...) Thanks! Jyrinx jyrinx_list at mindspring dot com

7 14

Re: Hugs plugin, Haskell Browser
by C.Reinke 15 Mar '02

15 Mar '02

> 2. When I hear "translate to HTML" I imagine that underlined > words which can be clicked to see, say, definition of > function. Sadly, most htmlizers are focused on highlighting > rather than navigation. Why generate HTML pages if noone reads them?-) Take this obscure location, for instance: http://www.haskell.org/libraries/#docu admittedly, Jan Skibinski's Haskell module browser is currently only available via archives, but it wasn't HTML-based anyway, and the other two links still work. Here's another example of text colouring that can be clicked on (few people do, so it has become quite silent on the mailing list, try the first months for more action..): http://haskell.org/mailman/listinfo/haskelldoc Hth, Claus

3 2

RE: Isn't this tail recursive?
by Ronny Wichers Schreur 15 Mar '02

15 Mar '02

Simon Marlow writes (to the Haskell mailing list) >The function as written is only strict in its list argument, and >its usage site only demands the 'l' argument strictly. So [..] >the compiler can't possibly evaluate the accumulating parameters >of countAll' strictly. The Clean compiler uses an optimisation that works in this case. After observing that main evaluates all elements of the tuple result (because of the shows), the compiler creates a special version of countAll with (Clean) type countAll :: String -> (!Int, !Int, !Int) and the same for countAll`. It than calls the strictness analyzer again for these functions. Cheers, Ronny Wichers Schreur

1 0

ANNOUNCE: Hat 1.12
by Malcolm Wallace 15 Mar '02

15 Mar '02

------------------------------------ hat-1.12, nhc98-1.12, and hmake-3.02 ------------------------------------ We are pleased to announce a new release of Hat, the Haskell tracing (an debugging) system, together with supporting releases of the nhc98 compiler and the hmake compilation manager. This release of Hat is a major release. It incorporates new trace-browsing tools, and for the first time has support to compile programs for tracing with GHC in addition to nhc98. for information on hat: http://www.cs.york.ac.uk/fp/hat/ for information on nhc98: http://www.cs.york.ac.uk/fp/nhc98/ for information on hmake: http://www.cs.york.ac.uk/fp/hmake/ for downloads: http://www.cs.york.ac.uk/fp/nhc98/download.html (Hat and hmake are packaged together with nhc98 in a single download.) If you haven't already tried out the Hat tracing system, now is a good time to have a go! New features worth noting are: * There is a new tutorial introduction to Hat, showing how to generate program traces, how to explore them, and how they can help you to debug Haskell programs. * All the interactive trace browsing tools are implemented in Haskell, including a new, simpler, textual version of hat-trail. They all inter-operate, and use a similar command syntax. * The trace-generating machinery can now be used with GHC in addition to nhc98: just use `hmake -ghc -hat' instead of `hmake -nhc98 -T'. (However, for the moment, you still need to download and install the nhc98 distribution, even when you intend to trace programs only with GHC.) In addition there have also been many minor bugfixes to nhc98 and hmake. Bug reports should be sent to nhc-bugs(a)haskell.org. Discussion of the Hat system belongs on nhc-users(a)haskell.org. Regards, The Hat team at York

1 0

ICFP'02: 6 days to go.
by Simon Peyton-Jones 15 Mar '02

15 Mar '02

======================================== Last chance for your ICFP'02 paper: 6 days to go. Don't let me down! Simon ======================================== ICFP 2002 International Conference on Functional Programming October 4-6, 2002, Pittsburgh, USA Final call for papers -------------------------------------------- Submission deadline: 21 March 2002 18:00 UTC -------------------------------------------- Program Chair: Simon Peyton Jones (Microsoft Research) Full call for papers including submission details: http://icfp2002.cs.brown.edu/CfP/ ICFP 2002 seeks original papers on the full spectrum of the art, science, and practice of functional programming. The conference invites submissions on all topics ranging from principles to practice, from foundations to features, and from abstraction to application. The scope covers all languages that encourage programming with functions, including both purely applicative and imperative languages, as well as languages that support objects and concurrency. Topics of interest include, but are not limited to, the following: Foundations: formal semantics, lambda calculus, type theory, monads, continuations, control, state, effects. Design: modules and type systems, concurrency and distribution, components and composition, relations to object-oriented and logic programming, multiparadigm programming. Implementation: abstract machines, compile-time and run-time optimization, just-in-time compilers, memory management, foreign-function and component interfaces. Transformation and analysis: abstract interpretation, partial evaluation, program transformation, theorem proving, specification and verification. Software development techniques for functional programming: design patterns, specification, verification and validation, debugging, test generation, etc. Human productivity of functional programming: visual, graphical (etc) approaches, evaluating language usability, empirical studies of human effectiveness, etc. Applications and domain-specific languages: scientific and numerical computing, symbolic computing and artificial intelligence, systems programming, databases, graphic user interfaces, multimedia programming, Web programming. Practice and experience: functional programming in education and industry, ramifications on other paradigms and computing disciplines. Functional pearls elegant, instructive examples of functional programming. General Chair: Mitchell Wand (Northeastern University) Program Committee Matthias Blume (Lucent) Margaret Burnett (Oregon State University) Manuel Chakravarty (University of New South Wales) Matthew Flatt (University of Utah) Haruo Hosoya (Kyoto University) Uwe Nestmann (EPFL, Lausanne) Chris Okasaki (United States Military Academy) Norman Ramsey (Harvard University) David Sands (Chalmers University) Olin Shivers (Georgia Tech) Stephanie Weirich (Cornell) Joe Wells (Heriot Watt University)

1 0

LAST CALL FOR PAPERS: Generators and Components (GCSE/SAIG'02)
by Charles Consel 15 Mar '02

15 Mar '02

LAST CALL FOR PAPERS Submission Deadline: March 21, 2002 The First ACM SIGPLAN/SIGSOFT Conference on Generators and Components (GCSE/SAIG'02) Supported by the National Science Foundation (NSF) Pittsburgh, PA, October 6-8, 2002. http://www.cs.yale.edu/~taha/gcse-saig/cfp02.html Invited Speakers: * Neil Jones, University of Denmark * Catuscia Palamidessi, Penn State University * Janos Sztipanovits, Vanderbilt University Program generation has the prospect of being an integral part of a wide range of software development processes. Many recent studies investigate different aspects of program generation, including their semantics, their application, and their implementation. Existing theories and systems address both high-level (source) language and low-level (machine) language generation. A number of programming languages now support program generation and manipulation, with different goals, implementation techniques, and targeted at different applications. The goal of this conference is to provide a meeting place for researchers and practitioners interested in this topic. A particular area of interest is component-based software development, which bears the promise of considerable productivity increases to software development comparable to the introduction of the assembly line in manufacturing. But due to the very same sophistication that makes components useful, their maintenance can be hard. Generative programming presents a promising approach to alleviating the above problems, as changes affecting components can now be more effectively managed during the generation process rather than at the component level. The goal of this joint event is to foster further cross-fertilization between the software engineering research community on the one hand, and the programming languages community on the other, in addition to supporting the original research goals of both GCSE and SAIG communities. We seek papers both in software engineering and programming languages, and especially those that bridge the gap. Being accessible to both communities at the same time is also valued. The conference solicits submissions related (but not limited) to: * Generative Programming: Reuse, meta-programming, partial evaluation, multi-stage and multi-level languages, * Semantics, type systems, symbolic computation, linking and explicit substitution, in-lining and macros, templates, program transformation, * Runtime code generation, compilation, active libraries, synthesis from specifications, development methods, generation of non-code artifacts, formal methods. Reflection. * Component-Based Software Engineering: Reuse, distributed platforms, distributed systems, evolution, analysis and design patterns, development methods, formal methods * Integration of Generative and Component-Based Approaches * Domain Engineering, analysis, and languages * Separation of Concerns: Aspect-Oriented Programming, Intentional * Programming, and Multi-Dimensional Separation of Concerns * Product Lines and generic architectures for that purpose. * Industrial Applications of Components and Generative Programming Reports on applications of these techniques to real-world problems are especially encouraged, as are submissions that relate ideas and concepts from several of these topics, or bridge the gap between theory and practice. The program committee is happy to advise on the appropriateness of a particular subject. General Chair: Walid Taha, Yale University, USA. Program Chair (GCSE focus): Don Batory, University of Texas at Austin, USA. Program Chair (SAIG focus): Charles Consel, INRIA, LaBRI, France. Program Committee (GCSE focus): Jan Bosch , University of Groningen Greg Butler, Concordia University Prem Devanbu, University of California at Davis Cristina Gacek, University of Newcastle upon Tyne Stan Jarzabek, National University of Singapore Kyo Kang, Pohang University of Science and Technology Peter Knauber, Fraunhofer Institute for Experimental Software Engineering Hausi Muller, University of Victoria Nenad Medvidovic, University of Southern California Wolfgang Pree, University of Constance Yannis Smaragdakis, Georgia Institute of Technology Douglas R. Smith , Kestrel Institute Program Committee (SAIG focus): Craig Chambers, University of Washington Shigeru Chiba, Tokyo Institute of Technology Pierre Cointe, Ecole des Mines de Nantes Dawson Engler, Stanford University Siau cheng Khoo, National University of Singapore Gregor Kiczales, University of British Columbia Martin Odersky, Ecole Polytechnique Fédérale de Lausanne Calton Pu, Georgia Institute of Technology Peter Thiemann, Universität Freiburg Andrew Tolmach, Portland State University Submission Details: Authors are invited to submit papers of at most 5000 words (excluding figures), in postscript format (letter or A4), using the electronic submission form by March 21st, 2002. This deadline is firm. Both position and technical papers are welcome (Please indicate at time of submission.) Authors will be notified of acceptance by May 14th, 2002. Final version of the papers must be submitted by July 14, 2002. Format: The three day conference will contain slots for technical papers (45 minutes) and position papers (30 minutes). Both times include discussion. Position papers are expected to describe important future directions, ongoing work, and survey previous results. This category is best thought of as one for "competitive invited papers". Technical papers are expected to contain novel results. All papers will be reviewed by the program committee for the above-mentioned criteria, in addition to correctness and clarity. Simultaneous submission to other venues is not allowed, as is submission of previously published material. In addition, there will be time allocated for open discussions at the end of the conference. Proceedings will be published as an LNCS volume. Special Note on Combined Event: While the Program Committee is divided into two focus areas corresponding the parent events (GCSE and SAIG), there will be one unified program committee meeting. At the time of submission, authors must indicate whether they intend the paper for the GCSE audience, SAIG audience, or BOTH. The last category is the default, and is strongly encouraged. Papers submitted explicitly to only one focus will be accepted or rejected by the respective Program Chair. For papers submitted to BOTH, it is enough that one of the two Program Chairs accepts the paper. All members of the PC will allowed to bid for and review all papers, and cross-bidding is encouraged. The conference itself will not be divided along focus lines. Rather, an attempt will be made to ensure that each session is of interest to both parent communities.

1 0

uniqueness typing
by Andre W B Furtado 15 Mar '02

15 Mar '02

I found the following text when visiting the Clean (a functional language) site: "Clean is the only functional language in the world which has a special type system, uniqueness typing. It enables to update function arguments destructively retaining the purity of the language." Then I have some questions: 1. Can anyone explain what does "update function arguments destructively" mean? 2. If this is a desirable thing, why does Haskell not implement it? Thanks, -- Andre

3 2

Strictness (was: Is this tail recursive?)
by Brian Huffman 15 Mar '02

15 Mar '02

At 22:47 13/03/02 -0600, Jay Cox wrote: >Perhaps what could be done about this strictness business is to make a >kind of strictness annotation. Perhaps something that says (force the >second argument of function F before every call to F (including any time F >calls itself)). >... >here's a rough example. !a mean !a will be forced at its application (for >not knowing proper language to call it). > >strict_foldl :: (a -> b -> a) -> !a -> [b] -> a >strict_foldl = foldl > >of course, there has to be a number of things that must be propagated >whence you start adding these things. like for instance. >.... >How about it? Has there been any other proposals? (like maybe going as >far as a "Strictness Type" system?) In Haskell you can produce the desired behavior by using pattern guards. Since the pattern guards always get evaluated before the result does, they can be used to make things more strict. Here is the foldl example: strict x = seq x True foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f z [] = z foldl' f z (x:xs) | strict z = foldl' f (f z x) xs You can make multiple arguments strict by using && or similar, e.g.: f x y | strict x && strict y = ... f x y | all strict [x,y] = ... Of course, with the second example x and y must have the same type. Hope this helps. - Brian Huffman

2 1

Re: Strictness (was: Is this tail recursive?)
by Andrew Butterfield 15 Mar '02

15 Mar '02

At 22:47 13/03/02 -0600, Jay Cox wrote: >Perhaps what could be done about this strictness business is to make a >kind of strictness annotation. Perhaps something that says (force the >second argument of function F before every call to F (including any time F >calls itself)). >... >here's a rough example. !a mean !a will be forced at its application (for >not knowing proper language to call it). > >strict_foldl :: (a -> b -> a) -> !a -> [b] -> a >strict_foldl = foldl > >of course, there has to be a number of things that must be propagated >whence you start adding these things. like for instance. >.... >How about it? Has there been any other proposals? (like maybe going as >far as a "Strictness Type" system?) I think the Clean type system does stuff like this - it certainly supports strictness analysis and annotations: - see http://www.cs.kun.nl/~clean/ for more details >_______________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell ------------------------------------------------------------------------ Dr. Andrew Butterfield (http://www.cs.tcd.ie/Andrew.Butterfield/) Course Director, B.A. (Mod.) Information & Communications Technology Dept.of Computer Science, Trinity College, Dublin University Tel: +353-1-608-2517, Fax: +353-1-677-2204 ------------------------------------------------------------------------

2 1