September 2007 - Haskell

ANN: ListLike, a generic interface over list-like structures
by John Goerzen 17 Sep '07

17 Sep '07

Hi, I'm pleased to announce the first release of ListLike, a generic interface to the various list-like structures in Haskell. This grew out of the annoyance at having to handle Strings and ByteStrings differently in my code, and has expanded on well past there. ListLike implements an API very similar to Data.List, but based on a typeclass. The module ships with instance definitions for lists, ByteStrings, lazy ByteStrings, Arrays, and even Maps. Additional classes are available for types that implement some additional features: String-like behavior, infinite list capability, and I/O. Finally, an extensive set of default functions is provided. Only minimal effort -- as little as four functions -- are needed to make your list-like type an instance of ListLike. ListLike is backed by an extensive suite of QuickCheck tests wrapped in HUnit, which tests virtually every function against every type. As of right now, 1567 test cases are executed, and all pass. Homepage: http://software.complete.org/listlike/ Download from: http://software.complete.org/listlike/downloads API ref: http://software.complete.org/listlike/static/doc/ Hackage page: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ListLike-1.0.0 -- John

3 4

ANN: monadLib 3.3.0 released
by Iavor Diatchki 17 Sep '07

17 Sep '07

Hello, I have put up a new version of monadLib, which is available from hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monadLib-3.3.0 The changes in this version are fairly small: * added an identity transformer, which is useful as a placeholder in some applications, * removed the RunStateM class because it does not seem to add extra functionality, * added a family of deriving functions that can be used to implement many monadLib functions for user-defined monads (e.g., monads defined via a newtype declaration). As usual, comments, bug-reports, and feedback are most welcome! -Iavor

1 0

question about a failure to generalize
by Tom Pledger 17 Sep '07

17 Sep '07

Norman Ramsey wrote: : | This code fails to compile because the compiler is willing to | use 'fold' at only one type (CmmExpr as it happens) : When it failed to compile, was fold = foldRegsUsed a top-level declaration in the module, rather than local to foldRegsUsed? If so, try working around the monomorphism restriction by changing from a pattern binding to a function binding. fold f = foldRegsUsed f Regards, Tom

3 3

Blocked STM & GC question
by Ashley Yakeley 17 Sep '07

17 Sep '07

If I have a thread that's blocked on an STM retry or TChan read, and none of its TVars are referenced elsewhere, will it get stopped and garbage-collected? I have in mind a pump thread that eternally reads off a TChan and pushes the result to some function. If the TChan is forgotten elsewhere, will the permanently blocked thread still sit around using up some small amount of memory, or will it be reaped by the garbage collector? -- Ashley Yakeley Seattle WA

2 1

1st CFP: 3rd Int'l Workshop on Automated Specification and Verification of Web Systems (WWV'07)
by Demis 17 Sep '07

17 Sep '07

[ We apologize for multiple copies ] *********************************************************************** 1st Call for Papers 3rd International Workshop on Automated Specification and Verification of Web Systems (WWV'07) San Servolo island, Venice (Italy) December 14, 2007 http://wwv07.dimi.uniud.it/ IMPORTANT DATES Abstract Submission October 14, 2007 Full Paper Submission October 21, 2007 Acceptance Notification November 12, 2007 Camera Ready November 23, 2007 Workshop December 14, 2007 SCOPE The increased complexity of Web sites and the explosive growth of Web-based applications has turned their design and construction into a challenging problem. Nowadays, many companies have diverted their Web sites into interactive, completely-automated, Web-based applications (such as Amazon, on-line banking, or travel agencies) with a high complexity that requires appropriate specification and verification techniques and tools. Systematic, formal approaches to the analysis and verification can address the problems of this particular domain with automated and reliable tools that also incorporate semantic aspects. We solicit original papers on formal methods and techniques applied to Web sites, Web services or Web-based applications, such as: * rule-based approaches to Web site analysis, certification, specification, verification, and optimization * formal models for describing and reasoning about Web sites * model-checking, synthesis and debugging of Web sites * abstract interpretation and program transformation applied to the semantic Web * intelligent tutoring and advisory systems for Web specifications authoring * Web quality and Web metrics * Web usability and accessibility * Testing and evaluation of Web systems and applications The WWV series provides a forum for researchers from the communities of Rule-based programming, Automated Software Engineering, and Web-oriented research to facilitate the cross-fertilization and the advancement of hybrid methods that combine the three areas. LOCATION WWV'07 will be held in December in the convention centre of the island of San Servolo, Venice, Italy. SUBMISSION PROCEDURE Submissions must be received by October 21, 2007. In addition, an ASCII version of the title and abstract must have been submitted by October 14, 2007. Submitted papers should be at most 15 pages in the Electronic Notes in Theoretical Computer Science (ENTCS) style, and should include an abstract and the author's information. See the author's instructions of ENTCS style at http://www.entcs.org. PUBLICATION Accepted papers will be published in a preliminary proceedings volume, which will be available during the workshop. Publication of the workshop post-proceedings in the Elsevier series Electronic Notes in Theoretical Computer Science (ENTCS, ISSN: 1571-0661) is envisaged. INVITED SPEAKERS Paolo Traverso ITC-IRST, Italy Joost Visser Software Improvement Group, The Netherlands PROGRAM CO-CHAIRS Santiago Escobar Technical University of Valencia, Spain Massimo Marchiori University of Padova, Italy WORKSHOP CHAIR Demis Ballis University of Udine, Italy PROGRAM COMMITTEE (in progress) Jesus Almendros University of Almeria, Spain Maria Alpuente Technical University of Valencia, Spain Demis Ballis University of Udine, Italy Gilles Barthe INRIA Sophia-Antipolis, France Tevfik Bultan University of California, Santa Barbara, USA Santiago Escobar Technical University of Valencia, Spain Moreno Falaschi University of Siena, Italy Nora Koch Ludwig Maximilians Universität München, Germany Temur Kutsia RISC, Linz, Austria Massimo Marchiori University of Padova, Italy Tiziana Margaria University of Potsdam, Germany Sebastian Schaffert Salzburg Research, Austria

1 0

HaL2: Meeting Haskell in Leipzig 2, videos and presentations online
by klaus meier 16 Sep '07

16 Sep '07

Hello haskell friends! The Videos and presentations of the talks given at HaL2 are now online: http://iba-cg.de/haskell.html Meeting HaL2, Leipzig Germany 10th of July Talks: (first in english, remaining in german) 1 Johan Jeuring (Uni Uetrecht) talks about "Generic Programming in Haskell" 2 Wolfgang Jeltsch (TU Cottbus) talks about "Grapefruit, a Haskell- library for the declarative description of graphic user interfaces" 3 Henning Thielemann (Uni Halle) talks about "Calculation of sound in Haskell" 4 Leif Frenzel (Karlsruhe) introduced Cohatoe: "Writing eclipse- plugins in haskell" We hope to see you on the next HaL meeting in the first quarter of 2008. Greetings, Alf Richter

2 1

Records
by Barney Hilken 16 Sep '07

16 Sep '07

Now that I have a version of ghc with type classes, I have had a go at implementing records based on the ideas I mentioned on this list a few months ago. The code of my first attempt is available at http:// homepage.ntlworld.com/b.hilken/files/Records.hs I am releasing this to get feedback. I think Haskell needs a records system of this kind of generality, and this code at least allows you to play around. From the comment section of the file: ----------------------- Record construction: EmptyRec is the empty record. N =: x is the record with one field labelled N carrying data x. t +: u is the union of records t and u. Any overlap of labels gives a static error. Record destruction: t .: N is the value of field N in record t. A lack of field N gives a static error. t -: N is record t with field N deleted. A lack of field N gives a static error. Record update: t |: u is the record with fields from u where it has them, t otherwise. If u has any fields not in t, or of different types from t, there is a static error. Note that the result has the same type as t. All these records have types: EmptyRec is the type of the empty record. N :=: a is the type of a record with one field labelled N carrying data of type a. r :+: s is the union of record types r and s. Any overlap of labels gives a static error. r :.: N is the type of field N in a record of type r. A lack of field N gives a static error. r :-: N is record type r with field N deleted. A lack of field N gives a static error. Finally some classes to govern the polymorphism: r `Contains` N means that r is a record type with a field labelled N. r `Disjoint` s means that r and s are record types with no fields in common. r `Subrecord` s means that r and s are record types, and every field of r also occurs in s (with the same type). The types of the basic operators are as follows: (=:) :: n -> a -> n :=: a (+:) :: r `Disjoint` s => r -> s -> r :+: s (.:) :: r `Contains` n => r -> n -> r :.: n (-:) :: r `Contains` n => r -> n -> r :-: n (|:) :: r `Subrecord` s => s -> r -> s ---------------------------------- Note that these records are a lot more expressive than the Hugs system, as you can not only extend records by adding fields, but also take unions of arbitrary (disjoint) records. Record update is designed for functions with lots of named optional arguments. If you define f opts = ... options.:Optj ... where options = (Opt1 =: val1 +: ... +: Optn =: valn) |: opts then the user can write (for example): f (Optk =: u +: Optl =: v) to set just two of the options, leaving the rest as default. This also cannot be done in the Hugs system. The main disadvantage of the current implementation is that you have to tell the compiler in which order to store the fields, by defining one of the following: type instance NameCmp N M = NameLT type instance NameCmp N N = NameEQ type instance NameCmp N M = NameGT for each pair of labels N & M in such a way as to give a linear order on labels. You need n^2 definitions, where n is the number of labels. I would do this in Template Haskell, but it won't yet allow you to declare type instances. Maybe some compiler support? Error messages tend to be cryptic. They mostly complain of missing instances, and can run to several pages. There is really no way to improve this without building it all in to the compiler! All comments gratefully received, including suggestions on syntax, choice of operators, implementation, explanation, etc. Barney.

1 0

Linear Equation Solver Using Arrays
by Xiao-Yong Jin 15 Sep '07

15 Sep '07

Dear Haskellers, My thanks to people on the irc channel, especially `int-e'. With their help, I managed to write a linear equation solver using STUArrays. It is basically a direct rewrite of a C version, which adopts Crout's LU decomposition method with implicit pivoting, in chapter 2.3 of the book Numerical Recipes. I must admit that the code is in a really bad style, somewhat ugly, because of the limit of my Haskell knowledge. The code is attached in this email for your amusement. I would be really thankful if you can give me any kind of comments, idea, improvement, criticism, because I sincerely want to make the code better. Best regards, Xiao-Yong -- c/* __o/* <\ * (__ */\ <

1 0

question about a failure to generalize
by nr＠eecs.harvard.edu 15 Sep '07

15 Sep '07

Dear Haskellers, I've had a Haskell program rejected for reasons I don't understand. Here's the relevant bit of code; the problem is that I expected the type-inference engine to generalize the abbreviation 'fold' to an overloaded function, but it doesn't---to make the code work, I had to expand 'fold' into 'foldRegsUsed' everywhere it appears. I'm baffled because 'fold' isn't mutually recursive with anything, so I would have expected ordinary Hindley-Milner style inference to generalize it to something of the type UserOfLocalRegs a => (b -> LocalReg -> b) -> b -> a -> b But that's not what happens. This code fails to compile because the compiler is willing to use 'fold' at only one type (CmmExpr as it happens): class UserOfLocalRegs a where foldRegsUsed :: (b -> LocalReg -> b) -> b -> a -> b instance UserOfLocalRegs Middle where foldRegsUsed f z m = middle m where middle (MidComment {}) = z middle (MidAssign _lhs expr) = fold f z expr middle (MidStore addr rval) = fold f (fold f z addr) rval middle (MidUnsafeCall tgt _ress args) = fold f (fold f z tgt) args middle (CopyIn _ _formals _) = z middle (CopyOut _ actuals) = fold f z actuals fold = foldRegsUsed What rule of the language have I overlooked? Norman

1 0

Re: Numeric programming on toy problems in Haskell
by Philip K.F. Hölzenspies 12 Sep '07

12 Sep '07

Dear Isaac, all, > Integral looks reasonable (are those really supposed to be div and > mod in defining quotRem, not quot and rem? I'm not sure). Yes, you're right. I changed to quot and rem. Also, the denominator and numerator functions were a bit needlessly complex. > There's no(?) excuse for using GHC extensions... just use > (Prelude.)fromRational instead of GHC.Float.fromRat (if using GHC, > it will optimize to the same thing, at least if optimizations are > on); and remove {-# OPTIONS -fglasgow-exts #-}. You were right about fromRat. I changed it into fromRational, saving me a GHC specific import. The GHC extensions are used, however, because of laziness; i.e. automatic derivation of Enum, Num, Fractional, Real and RealFrac. Without the GHC extensions, only Eq and Ord can be derived automatically. If I'm wrong about this, please let me know, because I would prefer a compiler independent solution as well. With respect to optimization; I think considering optimizability (?) in the design of such a module is a bit of a paradox. If optimization is a criterion, use the fine-grained typing and don't chuck all your numeric types into a single Number type. > (Have you seen Scheme's (dynamically typed) numeric ladder? It adds > a separate, additional concept of being able to tell, from a numeric > value, whether it is exact or not - e.g. for this Number > implementation, (1 + 1/3) is exact, and (sin pi) isn't, I think.) No, I haven't, I'm afraid. Like I said, this was pretty much a quick'n'dirty solution so that I could get on with my little puzzles (and because I learned FP in Miranda and never quite lost the 'num' affinitiy). There is a lingering idea that I could / should rework the Floating and RealFloat instances to be arbitrarily precise for most functions, by using continued fractions (only works for continued fractions that show regularity). Another option I was considering was to have all those operations be represented symbolically until such a time when they really needed to be approximated (for show, toInteger or toFloat). At that time I could either have my own simplifier and approximator, or I could link to other tools (maple, gnu something?). The idea was stalled, because I only use this for toy problems ;) If someone feels inspired, feel free to take this module and rework. I'm also open for suggestions on how to do this myself in case I ever un-stall this ;) Regards, Philip PS. Version with minor revisions is available, again from: http://www.cs.utwente.nl/~holzensp/Number.hs

3 2