October 2005 - Haskell

Haskell-mode 2.0
by Stefan Monnier 02 Feb '09

02 Feb '09

I have recently taken over maintainership of Haskell-mode, and after making a bunch of changes, I figured it would be a good idea to make a new release. You can find this new release at: http://www-perso.iro.umontreal.ca/~monnier/elisp/ If you think it should also be found at http://www.haskell.org/haskell-mode/, then please tell John Peterson to get back to me (my email to him seem to go straight to the bitbucket. John?). This release has several changes that have all been only lightly tested, especially w.r.t compatibility with various Emacsen. See appended the NEWS file that describes some of the notewirthy changes. Stefan Changes since 1.45: * keybindings C-c <char> have been replaced by C-c C-<char> so as not to collide with minor modes. * The following modules are now automatically activated without having to add anything to haskell-mode-hook: haskell-font-lock (just turn on global-font-lock-mode). haskell-decl-scan (just bind `imenu' to some key). * In recent Emacsen, haskell-doc hooks into eldoc-mode. * haskell-hugs and haskell-ghci are superceded by inf-haskell. * Indentation rules have been improved when using layout inside parens/braces. * Symbols like -> and \ can be displayed as actual arrows and lambdas. See haskell-font-lock-symbols. * Tweaks to the font-lock settings. Among other things paren-matching with things like \(x,y) should work correctly now. * New maintainer <monnier(a)gnu.org>.

3 6

GADTs and GHC
by Simon Peyton-Jones 27 Dec '05

27 Dec '05

Dear Haskell folk One of the interesting things about ICFP was the number of times GADTs came up, either in papers or in discussions in the breaks. Francois's invited talk was very inspiring, and that was just the beginning. Stephanie and Dimitrios and I are now busy revising our wobbly-types GADT paper (which is implemented in GHC, but never published http://research.microsoft.com/%7Esimonpj/papers/gadt/index.htm) We have a *far* simpler story now... but that means it'll reject some programs that would be accepted by the earlier version. We don't think this loss of expressiveness is important, but we'd like to check. Hence this message: If you use GADTs, would you to send us your GADT code, so we can check that we can still compile it? (A secondary reason for asking is that it'd be interesting just to see the way you are using GADTs.) If you send your code just to me, I'll collect it. You could a) send a complete Haskell program, which should compile and run b) send a Haskell module, or collection of modules, which should compile, but which isn't a complete program c) send a Haskell module using GADTs, but lacking the support modules that would enable it to compile d) send Omega code, which GHC won't understand, but which demonstrates some cunning use of GADTs All of these would be useful, even (c) and (d) --- we can eyeball the code. As a bonus, in the case of (a) or (b) I'll add your code to GHC's regression suite, so that all future releases will guarantee to run your code. [Or at least if not it'll be deliberate!] Tell me if you'd like this; it'll become visible in GHC's CVS repository. Thanks Simon

2 1

Writing large n-dim un-boxed array of Int32 quickly?
by Rene de Visser 31 Oct '05

31 Oct '05

Hello, I want to write a multi-dimensional unboxed arrary of Int32 to a file. (And also read it back later). What I tried so far is import NewBinary.Binary ... mapM_ (put bin) $ elems array ... but this was exceedlying slow. The array contains about 10 000 000 entries. Any suggestions? Rene.

4 5

Monads vs. continuations
by Gregory Woodhouse 31 Oct '05

31 Oct '05

Newbie alert: I have some superficial familiarity with continuations as they occur in traditional denotational semantics, but certainly not a deep understanding. I also have a special interest in distributed and/or concurrent processing, so it only seemed natural to me that the monad concept was one I'd want to confront head on. Now, I warn you: I am quite new to Haskell (though I have some prior exposure to Scheme and a background in mathematics). Now, I've just started reading through Thompson's text and came across this example: goUntilEmpty :: IO () goUntilEmpty = do line <- getLine if (line == []) then return () else (do putStrLn line goUntilEmpty) Okay, this seems sensible enough. Loosely speaking, I see this code as getting a line, checking to see if it's empty. If it is, it just quits (returning the "empty" value). Otherwise, it prints line, and invokes itself through a *new* do statement. That seems awfully like using a continuation to track the input stream as part of the environment. But it seems obvious to me that here is something I'm not understanding here. I think of the do as providing an appropriate continuation (one in which the line just read is gone) to pass to the next call. Okay, maybe I'm taking things a bit too literally here, but I seem to recall that a monad is an algebraic object with right and left identity and an associative composition. I understand the monad here takes a value (()) and returns an object IO (), and do becomes a functor of sorts, taking ordinary functions and mapping them to new functions having their codomain in a new category (an instance of a monad?) This is where it seems to me that I must be getting the terminology wrong. Can someone help me out here? === Gregory Woodhouse gregory.woodhouse(a)sbcglobal.net "The most incomprehensible thing about the world is that it is at all comprehensible." --Albert Einstein (1879-1955)

4 5

RE: [Haskell] really undecidable instances?
by Simon Peyton-Jones 30 Oct '05

30 Oct '05

This one can't. But it's hard to formulate a general rule. -fallow-undecidable-instances simply says that you, the programmer, take responsibility for termination. Without the flag, GHC uses a simple but sometimes over-conservative rule Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Wolfgang | Jeltsch | Sent: 17 October 2005 14:17 | To: Haskell ML | Subject: [Haskell] really undecidable instances? | | Hello, | | what ist the problem with instance declarations like the following: | | instance C Int a => D Char [a] | | Why are such declarations only allowed with -fallow-undecidable-instances in | GHC? How can they result in undecidability? | | Best wishes, | Wolfgang | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

4 4

RE: [Haskell] How to zip folds: A library of fold transformers
by Simon Peyton-Jones 29 Oct '05

29 Oct '05

Oleg: I'm sure you're aware of the close connection between your FR stuff (nice) and the foldr/build list-fusion work? (So-called "short-cut deforestation".) To make short-cut deforestation work, one has to write map, filter etc in precisely the style you give. I have not grokked your zip idea, though it looks cunning. I wonder if it could be formulated in such a way that we could do foldr/build fusion down both branches of a zip? John Launchbury et al had a paper about hyper-functions which tackled the zip problem too. http://citeseer.ist.psu.edu/krstic01hyperfunctions.html. Also Josef Svengingsson (ICFP'02). I don't know how these relate to your solution. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of | oleg(a)pobox.com | Sent: 12 October 2005 01:25 | To: haskell(a)haskell.org | Subject: [Haskell] How to zip folds: A library of fold transformers | | | We show how to merge two folds into another fold | `elementwise'. Furthermore, we present a library of (potentially | infinite) ``lists'' represented as folds (aka streams, aka | success-failure-continuation--based generators). Whereas the standard | Prelude functions such as |map| and |take| transform lists, we | transform folds. We implement the range of progressively more complex | transformers -- from |map|, |filter|, |takeWhile| to |take|, to |drop| | and |dropWhile|, and finally, |zip| and |zipWith|. | | Emphatically we never convert a stream to a list and so we never use | value recursion. All iterative processing is driven by the fold | itself. | | The implementation of zip also solves the problem of ``parallel | loops''. One can think of a fold as an accumulating loop. One can | easily represent a nested loop as a nested fold. Representing parallel | loop as a fold is a challenge, answered at the end of the message. We | need recursive types -- but again, never value recursion. | | This library is inspired by Greg Buchholz' message on the Haskell-Cafe list | and is meant to answer open questions posed at the end of that message | http://www.haskell.org/pipermail/haskell-cafe/2005-October/011575.html | | This message a complete literate Haskell code. | | > {-# OPTIONS -fglasgow-exts #-} | > module Folds where | | First we define the representation of a list as a fold: | | > newtype FR a = FR (forall ans. (a -> ans -> ans) -> ans -> ans) | > unFR (FR x) = x | | It has a rank-2 type. The defining equations are: if flst is a value | of a type |FR a|, then | unFR flst f z = z if flst represents an empty list | unFR flst f z = f e (unFR flst' f z) | if flst represents the list with the head 'e' | and flst' represents the rest of that list | | >From another point of view, |unFR flst| can be considered a _stream_ | that takes two arguments: the success continuation of the type | |a -> ans -> ans| and the failure continuation of the type |ans|. The LogicT | paper discusses such types in detail, and shows how to find that "rest | of the list" flst'. The slides of the ICFP05 presentation by | Chung-chieh Shan point out to more related work in that area. | | But we are here to drop, take, dropWhile, etc. Our functions will | take a stream and return another stream, of the |FR a| type, which | represents truncated, filtered, etc. source stream. | | Let us define two sample streams: a finite and an infinite one: | | > stream1 :: FR Char | > stream1 = FR (\f unit -> foldr f unit ['a'..'i']) | > stream2 :: FR Int | > stream2 = FR (\f unit -> foldr f unit [1..]) | | and the way to show the stream. This is the only time we convert |FR a| | to a list -- so we can more easily show it. | | > instance Show a => Show (FR a) where | > show l = show $ unFR l (:) [] | | | The map function is trivial: | | > smap :: (a->b) -> FR a -> FR b | | *> smap f l = FR(\g -> unFR l (g . f)) | | which can also be written as | | > smap f l = FR((unFR l) . (flip (.) f)) | | For example, | | > test1 = show $ smap succ stream1 | | | Next is the filter function: | | > sfilter :: (a -> Bool) -> FR a -> FR a | > sfilter p l = FR(\f -> unFR l (\e r -> if p e then f e r else r)) | | > test2 = sfilter (not . (`elem` "ch")) stream1 | | The function takeWhile is quite straightforward, too | | > stakeWhile :: (a -> Bool) -> FR a -> FR a | > stakeWhile p l = FR(\f z -> unFR l (\e r -> if p e then f e r else z) z) | | > test3 = stakeWhile (< 'z') stream1 | > test3' = stakeWhile (< 10) stream2 | | As we can see, stakeWhile well applies to an infinite stream. | | The functions take, drop, dropWhile ask for more complexity. | | > stake :: (Ord n, Num n) => n -> FR a -> FR a | > stake n l = FR(\f z -> | > unFR l (\e r n -> if n <= 0 then z else f e (r (n-1))) (const z) n) | | > test4 = stake 20 stream1 | > test4' = stake 5 stream1 | > test4'' = stake 11 stream2 | > test4''' = (stake 11 . smap (^2)) stream2 | | The function sdrop shows the major deficiency: we're stuck with the | (<=0) test for the rest of the stream. In this case, some delimited | continuation operators like `control' can help, in limited | circumstances. | | > sdrop :: (Ord n, Num n) => n -> FR a -> FR a | > sdrop n l = FR(\f z -> | > unFR l (\e r n -> if n <= 0 then f e (r n) else r (n-1)) (const z) n) | | > test5 = sdrop 20 stream1 | > test5' = sdrop 5 stream1 | > test5'' = stake 5 $ sdrop 11 stream2 | | The function dropWhile becomes straightforward | | > sdropWhile :: (a -> Bool) -> FR a -> FR a | > sdropWhile p l = FR(\f z -> | > unFR l (\e r done -> | > if done then f e (r done) | > else if p e then r done else f e (r True)) (const z) False) | | > test6 = sdropWhile (< 'z') stream1 | > test6' = sdropWhile (< 'd') stream1 | > test6'' = stake 5 $ sdropWhile (< 10) stream2 | | The zip function is the most complex. | | Here we need a recursive type: an iso-recursive type to emulate the | equi-recursive one. | | > newtype RecFR a ans = RecFR (a -> (RecFR a ans -> ans) -> ans) | > unRecFR (RecFR x) = x | | This is still a newtype: there is no extra consing. | | I will not pretend that the following is the most perspicuous piece of code: | | *> szip :: FR a1 -> FR a2 -> FR (a1,a2) | *> szip l1 l2 = FR(\f z -> | *> let l1' = unFR l1 (\e r x -> unRecFR x e r) (\r -> z) | *> l2' = unFR l2 (\e2 r2 e1 r1 -> f (e1,e2) (r1 (RecFR r2))) (\e r-> z) | *> in l1' (RecFR l2')) | | It can be simplified to the following: | | > szipWith :: (a->b->c) -> FR a -> FR b -> FR c | > szipWith t l1 l2 = FR(\f z -> | > unFR l1 (\e r x -> unRecFR x e r) (\x -> z) | > (RecFR $ | > unFR l2 (\e2 r2 e1 r1 -> f (t e1 e2) (r1 (RecFR r2))) (\e r -> z))) | > | > szip :: FR a -> FR b -> FR (a,b) | > szip = szipWith (,) | | | One can easily prove that this function does correspond to zip for all | finite streams. The proof for infinite streams requires more | elaboration. | | > test81 = szip stream1 stream1 | > test82 = szip stream1 stream2 | > test83 = szip stream2 stream1 | > test84 = stake 5 $ szip stream2 (sdrop 10 stream2) | | As one may expect (or not), these tests give the right results | | *Folds> test83 | [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e'),(6,'f'),(7,'g'),(8,'h'),(9,'i') ] | *Folds> test84 | [(1,11),(2,12),(3,13),(4,14),(5,15)] | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

2 1

Problem with superclass entailment in "A Static Semantics for Haskell"
by Stefan Wehr 29 Oct '05

29 Oct '05

Hi all, I believe there is a problem in the rule for instance declarations in "A Static Semantics For Haskell" [1] because the premise which ensures that instances for all superclasses are defined seems to hold trivially. [2] seems to have the same problem. I now describe the problem by showing how an incorrect program is accepted by the rules given in [1]. I omit many, many details that are irrelevant to this problem. Consider the following program: class C a class C a => D a instance D Int The instance environment IE for this program is built recursively by the rule for modules bodies (Fig. 15) and looks like this: IE = {forall a. D a => C a, D Int} We would expect that the rule for instance declarations (Fig. 26) rejects the program because there is no instance declaration for C Int. However, the rule uses the *whole* instance environment IE to check whether there is an instance declaration for C Int. But this holds trivially, because we have D Int in IE and the implication (forall a. D a => C a) lets us the conclude that C Int holds!! In other words: The rule uses the implication (forall a. D a => C a) to make sure that the very same implication is valid for a = Int. A possible solution might be to remove the constraint D Int before checking whether C Int holds. However, I am not sure whether the resulting rule is complete. An alternative solution would be to use a weaker entailment judgment. Any thoughts? Am I just missing some implicit condition on the instance environment? References: [1] @Article{Faxen02, title = "A static semantics for {Haskell}", author = "Karl-Filip Fax{\'e}n", journal = "Journal of Functional Programming", year = "2002", number = "4\&5", volume = "12", pages = "295--357", } [2] @Article{Hall1996, author = "Cordelia V. Hall and Kevin Hammond and Simon L. {Peyton Jones} and Philip L. Wadler", title = "Type classes in {Haskell}", journal = "ACM Transactions on Programming Languages and Systems", volume = "18", number = "2", pages = "109--138", year = "1996", } Cheers, Stefan Wehr -- Stefan Wehr Web: http://www.stefanwehr.de PGP: Key is available from pgp.mit.edu, ID 0B9F5CE4

1 0

FM'06 Announcement and Call for Submissions
by events-admin＠fmeurope.org 28 Oct '05

28 Oct '05

FM'06: 14TH INTERNATIONAL SYMPOSIUM ON FORMAL METHODS 21 - 27 August 2006 McMaster University, Hamilton, Ontario, Canada http://fm06.mcmaster.ca/ ANNOUNCEMENT AND CALL FOR SUBMISSIONS FM'06 is the fourteenth in a series of symposia organized by Formal Methods Europe, http://www.fmeurope.org, an independent association whose aim is to stimulate the use of, and research on, formal methods for software development. The symposia have been notably successful in bringing together innovators and practitioners in precise mathematical methods for software development, industrial users as well as researchers. Submissions are welcomed in the form of original papers on research and industrial experience, proposals for workshops and tutorials, entries for the exhibition of software tools and projects, and reports on ongoing doctoral work. FM'06 welcomes all aspects of formal methods research, both theoretical and practical. We are particularly interested in the experience of applying formal methods in practice. The broad topics of interest of this conference are: * Tools for formal methods: tool support and software engineering, environments for formal methods. * Theoretical foundations: specification and modelling, refining, static analysis, model-checking, verification, calculation, reusable domain theories. * Formal methods in practice: experience with introducing formal methods in industry, case studies. * Role of formal methods: formal methods in hardware and system design, method integration, development process. TECHNICAL PAPERS Full papers should be submitted via the web site. Papers will be evaluated by the Program Committee according to their originality, significance, soundness, quality of presentation and relevance with respect to the main issues of the symposium. Accepted papers will be published in the Symposium Proceedings, to appear in Springer's Lecture Notes in Computer Science series, http://www.springeronline.com/lncs . Submitted papers should have not been submitted elsewhere for publication, should be in Springer's format, (see Springer's web site), and should not exceed 16 pages including appendices. A prize for the best technical paper will be awarded at the symposium. INDUSTRIAL USAGE REPORTS One day will be dedicated to sharing the experience -- both positive and negative -- with using formal methods in industrial environments. The Industry Day is organized by ForTIA, the Formal Techniques Industry Association, http://www.fortia.org . This year's Industry Day investigates the use of formal methods in security and trust. Invited papers on organizational and technical issues will be presented. Inquiries should be directed to the Industry Day Chairs; see the web site for details. WORKSHOPS We welcome proposals for one-day or one-and-a-half-day workshops related to FM'06. In particular, but not exclusively, we encourage proposals for workshops on various application domains. Proposals should be directed to the Workshop Chair. TUTORIALS We are soliciting proposals for full-day or half-day tutorials. The tutorial contents can be selected from a wide range of topics that reflect the conference themes and provide clear utility to practitioners. Each proposal will be evaluated on importance, relevance, timeliness, audience appeal and past experience and qualification of the instructors. Proposals should be directed to the Tutorial Chair. POSTER AND TOOL EXHIBITION An exhibition of both research projects and commercial tools will accompany the technical symposium, with the opportunity of holding scheduled presentations of commercial tools. Proposals should be directed to the Poster and Tools Exhibition Chair. DOCTORAL SYMPOSIUM For the first time, FM'06 will feature a doctoral symposium. Students are invited to submit work in progress and to defend it in front of "friendly examiners". Participation for students who are accepted will be subsidized. Submissions should be directed to the Doctoral Symposium Chair. SUBMISSION DATES Technical Papers, Workshops, Tutorials: Friday, February 24, 2006 Posters and Tools, Doctoral Symposium: Friday, May 26, 2006 NOTIFICATION DATES Technical Papers: Friday, April 28, 2006 Workshops, Tutorials: Friday, March 10, 2006 Posters and Tools, Doctoral Symposium: Friday, June 9, 2006 ORGANIZATION General Chair: Emil Sekerinski (McMaster) Program Chairs: Jayadev Misra (U. Texas, Austin), Tobias Nipkow (TU Munich) Workshop Chair: Tom Maibaum (McMaster) Tutorial Chair: Jin Song Dong (NUS) Tools and Poster Exhibition Chair: Marsha Chechik (U. Toronto) Industry Day Chairs: Volkmar Lotz (SAP France), Asuman Suenbuel (SAP US) Doctoral Symposium Chair: Augusto Sampaio (U. Pernambuco) Sponsorship Chair: Juergen Dingel (Queens U.) PROGRAM COMMITTEE Jean-Raymond Abrial (ETH Zurich) Alex Aiken (Stanford U.) Keijiro Araki (Kyushu U.) Ralph Back (Abo Akademi) Gilles Barthe (INRIA) David Basin (ETH Zurich) Ed Brinksma (U. Twente) Michael Butler (U. Southampton) Rance Cleaveland (U. Stony Brook) Jorge Cuellar (Siemens) Werner Damm (U. Oldenburg) Frank de Boer (U. Utrecht) Javier Esparza (U. Stuttgart) Jose Fiadeiro (U. Leicester) Susanne Graf (VERIMAG) Ian Hayes (U. Queensland) Gerard Holzmann (JPL) Cliff Jones (U. Newcastle) Gary T. Leavens (Iowa State U.) Rustan Leino (Microsoft) Xavier Leroy (INRIA) Dominique Mery (LORIA) Carroll Morgan (UNSW) David Naumann (Stevens) E.-R. Olderog (U. Oldenburg) Paritosh Pandya (TIFR) Sriram Rajamani (Microsoft) John Rushby (SRI) Steve Schneider (U. Surrey) Vitaly Shmatikov (U. Texas, Austin) Bernhard Steffen (U. Dortmund) P.S. Thiagarajan (NUS) Axel van Lamsweerde (U. Louvain) Martin Wirsing (LMU Munich) Pierre Wolper (U. Liege) LOCAL ORGANIZATION Publicity: Wolfram Kahl, Alan Wassyng, Jeff Zucker Tools, Posters, Book Exhibition: Spencer Smith Social Events: Ridha Khedri Local Arrangements:: William Farmer, Mark Lawford Events Co-ordinator: Ryszard Janicki _______________________________________________ events mailing list events(a)fmeurope.org http://www.fmeurope.org/mailman/listinfo/events

1 0

RE: [Haskell] PROPOSAL: class aliases
by Simon Peyton-Jones 28 Oct '05

28 Oct '05

| This is a proposal for a language extension which will hopefully mitigate the | issues holding back evolution of the standard prelude as well as provide | useful class abstraction capabilities in general. A short summary would be "type synonyms for class constraints". You'd definitely want the syntax to look as much like a type synonym decl as possible. I've considered this before, but never done anything about it because superclasses are so close. Specifically, what is the difference between (i) class (C a, D a) => CD a and (ii) class alias CD a = (C a, D a) Note that (i) is Haskell 98. * In both cases one can write f :: (CD a) => ... instead of the more voluminous f :: (C a, D a) * However with (i), for each type T one must write instance C T where { ...meths for C... } instance D T where { ...meths for D... } instance CD T where {} whereas with (ii) one can write instance CD T where { ...meths for C... ...meths for D... } I believe that this latter is the sole difference. Am I right? [Implementation aspects aside.... with (i) GHC will pass one dictionary CD containing a pair of dictionaries, one for C and one for D.] If so, than rather than invent a whole new mechanism, why not simply extend the existing superclass mechanism to allow a single instance decl to declare instances for several classes? For example, one add to Haskell 98 the following: an instance declaration for a class CD with superclasses C and D may give the instances for its superclasses C and D [One could quibble about details. E.g Should the class decl for CD *say* whether the instance decl *must* contain decls for the superclass methods? Or can one vary it on a instance-by-instance basis, which might be more flexible?] Anyway, my main point it: would a smaller change not suffice? Simon

9 10

[Fwd: Bug in Data.IntSet?]
by Ketil Malde 28 Oct '05

28 Oct '05

Sigh. My system insists on rewriting outgoing mail headers, and ghc-users refuses non-subscribers to post there. I'm too tired to fight this at the moment, so I'll send it here in the hope that it will be picked up by the right adressee. -k -------- Original Message -------- Subject: Bug in Data.IntSet? Date: Thu, 27 Oct 2005 15:25:30 +0200 From: Ketil Malde <ketil(a)ii.uib.no> To: glasgow-haskell-users <glasgow-haskell-users(a)haskell.org> AFAICT, there is a bug in Data.IntSet.split Here's an excerpt from GHCi: *Main> let m=482 in Data.IntSet.split (16*m) $ Data.IntSet.fromList (List.map (m*) [17,18,19,30,40]) ({8194,8676,9158},{14460,19280}) *Main> let m=481 in Data.IntSet.split (16*m) $ Data.IntSet.fromList (List.map (m*) [17,18,19,30,40]) ({},{8177,8658,9139,14430,19240}) *Main> let m=481 in Data.Set.split (16*m) $ Data.Set.fromList (List.map (m*) [17,18,19,30,40]) ({},{8177,8658,9139,14430,19240}) *Main> let m=482 in Data.Set.split (16*m) $ Data.Set.fromList (List.map (m*) [17,18,19,30,40]) ({},{8194,8676,9158,14460,19280}) *Main> let m=482 in Data.Set.split (16*m) $ Data.Set.fromList (List.map (m*) [17,18,19,30,40]::[Int]) ({},{8194,8676,9158,14460,19280}) % ghci --version The Glorious Glasgow Haskell Compilation System, version 6.4.1 -k

3 2