Haskell Communities and Activities Report

The #haskell IRC channel is a real-time text chat where anyone can join to discuss Haskell. #haskell averages about one hundred eighty users. Point your IRC client to irc.freenode.net and join the #haskell channel.

The #haskell.se channel is the same subject but discussion happens in Swedish. This channel tends to have a lot of members from Gothenburg.

There is also a #darcs channel – if you want real-time discussion about darcs (→6.6), drop by!

The Haskell Weekly News (HWN) is a weekly newsletter covering developments in Haskell. Content includes announcements of new projects, discussions from the various Haskell communities, notable project commit messages, and more.

It is published in html form on The Haskell Sequence (→1.4.1), via mail on the Haskell mailing list, and via RSS. Headlines are published on haskell.org (→1.1).

Further reading

• Archives, and more information can be found at:

  http://www.haskell.org/haskellwiki/Haskell_Weekly_News

The Haskell Sequence is a community-edited Haskell news and discussion site. Its main feature is a slashdot-like front page with stories and discussion about things going on in the Haskell community, polls, questions, or just observations. Submissions are voted on by the community before being posted on the front page, similar to Kuro5hin.

The Haskell Sequence also syndicates Haskell mailing list posts, Haskell-related blogs, and other RSS feeds in a single location. Free space for Haskell-related blogs, which require no voting before being posted, is also available to anyone.

Further reading

The Haskell Sequence is available at http://sequence.complete.org.

There are plenty of academic papers about Haskell, and plenty of informative pages on the Haskell Wiki. But there’s not much between the two extremes. The Monad.Reader aims to fit in there; more formal than a Wiki page, but less formal than a journal article.

Want to write about a tool or application that deserves more attention? Have a cunning hack that makes coding more fun? Got that visionary idea people should know about? Write an article for The Monad.Reader!

Further reading

See the TmrWiki for more information: http://www.haskell.org/tmrwiki/FrontPage.

The contract to publish the book with Cambridge University Press has recently been signed (including a clause about film rights, so expect “Haskell the Movie” in a couple of years :-)), and it is now entering the final production stage, with an estimated publication date in the last quarter of 2006. Further details, including a preview of the first five chapters and powerpoint lecture slides for all chapters, are available on the web from http://www.cs.nott.ac.uk/~gmh/book.html.

The Haskell Tutorial WikiBook has made considerable progress over the last six months. It has now reached the stage where a beginner to Haskell should find it useful, although much still remains to be done.

Much of the recent work has been done by Eric Kow (Kowey). Jeff Newburn also gave permission for his “All About Monads” tutorial to be imported. Thanks to these, and to all the other contributors.

Future work needs to focus on:

• Adding exercises and worked examples. The first section in particular presents Haskell from the bottom up with very little to explain how the material relates to real world programming.

• Integrating the existing material. At present there are three distinct sections that read like three different tutorials, partly because that is how they started.

All contributions are welcome.

Further reading

http://en.wikibooks.org/wiki/Programming:Haskell

We have been quite busy on GHC during the last six months. Here are the highlights:

• We switched to darcs (→6.6) for our version control. Thanks to all those who helped out, especially John Goerzen who migrated the repository over from CVS and helped with the initial setup. Following the darcs switchover, the GHC source tree has been reorganised and flattened, and the build system simplified.
• The multiprocessor support has had an overhaul. There are now per-CPU run queues, so thread affinity should be better and the scheduler is lock-free in the common case. There are some new RTS flags to control thread migration (although there is still no real load balancing). You don’t need a separate set of libraries for running parallel code – the ordinary libraries work (this required a small performance hit for sequential code, unfortunately). The threaded and SMP runtimes were merged, so only -threaded is required for parallel now, -smp is a synonym for -threaded.
• Better GC behaviour for IORefs/STRefs, STArrays/IOArrays, and when there are a large number of blocked threads. Now these objects are only scanned during GC if they were mutated since the previous GC. This alleviates some pathological cases of poor GC performance, and gave GHC itself a performance boost (GHC uses IORefs for type variables). Large arrays are still scanned in their entirety; hopefully we’ll improve this in the future.

• Refactoring in the compiler front-end (thanks to Lemmih).
• Loosen the rules for instance declarations (thanks to Ross Paterson).

  http://www.haskell.org//pipermail/glasgow-haskell-users/2006-February/009633.html

• Implementation of “boxy types” to support type inference for impredicative types:

  http://research.microsoft.com/~simonpj/papers/boxy Huge thanks to Stephanie Weirich and Dimitrios Vytiniotis for their work on this project.

• The design of lexically-scoped type variables has changed, and will likely change further. These changes have arisen out of the work with Stephanie and Dimitrios; frankly we aren’t yet sure what the exact design should be and, until we are, the implementation has rough edges.
• Name completion in GHCi. If you have readline, then you can use the TAB key on the command line to complete against names in scope.
• Full support for Unicode (UTF-8) source files. UTF-8 is currently the only encoding supported by GHC, we plan to add support for more encodings before 6.6 is released.

• Bang patterns are now implemented, as an experimental feature

  http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/BangPatterns

• The Data.ByteString (→4.6.3) library was added (thanks particularly to Don Stewart and others who contributed to the code).

• The native code generator can handle loops (thanks Wolfgang Thaller).

• Performance improvements for x86_64: more arguments are passed in registers.

• Experimental “breakpoint” feature in GHCi (thanks Lemmih).

Release cycle

• 6.4.2 was released recently, with a significant number of bugfixes relative to 6.4.1. Nevertheless, problems have been found in 6.4.2; there is an unidentified bug affecting MacOS X, and problems have been reported in the threaded RTS on Solaris and FreeBSD (in fact, these problems may have been present in 6.4.1 but unnoticed until now, because in 6.4.2 GHC itself was switched to the threaded RTS).

• There will probably be a 6.4.3, with a few important fixes only.
• 6.6, with all the new features above, is scheduled for sometime this summer. To get an idea of what is still to do for 6.6, check the ticket system on the Trac:

  http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status=reopened&milestone=6.6&order=priority

  Help is welcome as usual, and will probably speed the release along!

Forthcoming excitements

• We are working hard on developing a data-parallel extension to GHC, in collaboration with Gabriele Keller, Manuel Chakravarty, and Roman Leshchinskiy. The basic idea was pioneered by Guy Blelloch in NESL, and subsequently developed in various ways by Gabi, Manuel, and Roman; for example, see http://www.cse.unsw.edu.au/~chak/papers/CKLP01.html
• We plan to implement Associated Types during the next few months: http://research.microsoft.com/~simonpj/papers/assoc-types/
• Part of the reason that we have been slow to implement associated types is that they can’t be translated into System F (GHC’s internal language without great difficulty). We have recently figured out a new design for GHC’s internal language, which we call System FC:

  http://research.microsoft.com/~simonpj/papers/ext-f

  Kevin Donnelly is spending the summer at Microsoft as an intern, to implement FC in GHC.

• The multiprocessor GHC runs Haskell in parallel, but when garbage collection happens only one processor does the job. How embarrassing. Roshan James, also an intern this summer, is going to build a parallel garbage collector.

We are planning to run a “GHC Hackathon” just before ICFP in Portland, in September 2006. We’ll give some tutorials on how GHC works inside, and then spend some time writing code together. If you are interested, keep an eye on GHC’s web site.

The May 2006 release of Hugs was the first for over three years to include a Windows distribution, thanks to Neil Mitchell, who has also contributed a new version of WinHugs, the Windows graphical interface to Hugs. Other major features, already seen in the Unix-only release, are support for the Cabal infrastructure (→4.1.1), Unicode support (contributed by Dmitry Golubovsky) and lots of up-to-date libraries.

Obsolete non-hierarchical libraries (hslibs and Hugs-specific libraries) have been removed from the default search path, and will disappear altogether in the next release.

The source distribution is available in two forms: a huge omnibus bundle containing the Hugs programs and lots of useful libraries, or a minimal bundle, with most of the libraries hived off as separate Cabal packages.

There is also a new bug tracking system and development wiki at http://hackage.haskell.org/trac/hugs.

As ever, volunteers are welcome.

nhc98 is a small, easy to install, compiler for Haskell’98. It is in stable maintenance-only mode – the current public release is version 1.18. Maintenance continues in CVS at haskell.org. Recent news is that Niklas (the original author of nhc13) has contributed a workaround for the hi-mem bug which was preventing the compiler from building on many recent Linux platforms. A new release incorporating this patch is expected soon.

The Yhc (→2.4) branch of nhc98 is also making good progress.

Further reading

http://haskell.org/nhc98

The York Haskell Compiler (yhc) is a backend rewrite of the nhc98 (→2.3) compiler to support features such as a platform independent bytecode and runtime system.

It is currently work in progress, it compiles and correctly runs almost every standard Haskell 98 program but FFI support is on going. Contributions are welcome.

Further reading

• Homepage:

  http://www.cs.york.ac.uk/~ndm/yhc/

• Darcs (→6.6) repository:

  http://www.cs.york.ac.uk/fp/darcs/yhc/

Our work on running Haskell on handheld devices based on Palm OS has taken a different direction since the last report. Instead of basing our port on nhc98 (→2.3) we are now using yhc (→2.4) as the basis. Overall everything is easier since yhc has a better separation of compiler and runtime system. We have also added a part-time programmer to this project so more progress is being made. An alpha version is close to working.

Vital is a highly interactive, visual environment that aims to present Haskell in a form suitable for use by engineers, mathematicians, analysts and other end users who often need a combination of the expressiveness and robustness that Haskell provides together with the ease of use of a ‘live’ graphical environment in which programs can be incrementally developed.

In Vital, Haskell modules are presented as ‘documents’ having a free-form layout and with expressions and their values displayed together. These values can be displayed either textually, or pictorially and can be manipulated by an end user by point-and-click mouse operations. The way that values of a given type are displayed and the set of editing operations defined on them (i.e., the ‘look and feel’ of the type) are defined using type classes. For example, an ADT representing directed graphs could be introduced, with its values displayed pictorially as actual directed graphs and with the end user provided with a menu of operations allowing edges to be added or removed, transitive closures to be computed, etc. (In fact, although an end user appears to be operating directly on values, it is actually the Haskell program itself that is updated by the system, using a specialised form of reflection.)

The present implementation includes a collection of interactive tutorial documents (including examples illustrating approaches to exact real arithmetic, pictorial manipulation of DNA and the genetic code, animated diagrams of mechanisms, and the composition and synthesis of MIDI music).

The Vital system can be run via the web: a single mouse-click is all that is needed!

Further reading

http://www.cs.kent.ac.uk/projects/vital/

Pivotal 0.025 is a very early prototype of a Vital-like environment (→3.1.2) for Haskell. Unlike Vital, however, Pivotal is implemented entirely in Haskell. The implementation is based on the use of the hs-plugins library (→4.4.1) to allow dynamic compilation and evaluation of Haskell expressions together with the gtk2hs library (→4.8.1) for implementing the GUI.

At present, the implementation is only in a skeletal state but, nevertheless, it provides some useful functionality. The Pivotal web site provides an overview of its principles of operation, a selection of screen shots (including a section illustrating image transforms in the complex plane), and a (very preliminary!) release of the Haskell code for the system.

A more extensive implementation (based on the use of the GHC API (→2.1) for reflection, in place of the hs-plugins (→4.4.1) mechanism) is planned as soon as the required hooks are available in GHC 6.6.

Further reading

http://www.cs.kent.ac.uk/projects/pivotal/

House is a platform for exploring various ideas relating to low-level and system-level programming in a high-level functional language, or in short for building operating systems in Haskell. House is based on hOp by Sébastien Carlier and Jérémy Bobbio.

Recent work includes

• the introduction of H, the Hardware Monad, an API on top of which various operating system features (e.g., virtual memory management, user-space execution, device drivers and interrupt handling) can be implemented in a fairly safe way. Key properties of the H monad operations are captured as P-Logic assertions in the code. This is described in more detail in our ICFP 2005 paper.

  The House demo system is now implemented on top of the H monad. There is also work in progress on implementing an L4 compatible micro-kernel on top of H.

• adding support for parsing and rendering GIF images. This allowed us to use House to display the slides for the talk at ICFP.

• adding support for scanning the PCI bus and identifying PCI devices.

Further reading

Further information, papers, source code, demos and screenshots are available here: http://www.cse.ogi.edu/~hallgren/House/

The Camila project explores how concepts from the VDM++ specification language and the functional programming language Haskell can be combined. On the one hand, it includes experiments of expressing VDM’s data types (e.g. maps, sets, sequences), data type invariants, pre- and post-conditions, and such within the Haskell language. On the other hand, it includes the translation of VDM specifications into Haskell programs. Moreover, the use of the OOHaskell library (→4.6.7) allows the definition of classes and objects and enables important features such as inheritance. In the near future, support for parallelism and automatic translation of VDM++ specifications into Haskell will be added to the libraries.

Currently, the project has produced first versions of the Camila Library, both distributed as part of the UMinho Haskell Libraries and Tools. The library resorts to Haskell’s constructor class mechanism, and its support for monads and monad transformers to model VDM’s datatype invariants, and pre- and post-conditions. It allows switching between different modes of evaluation (e.g. with or without property checking) by simply coercing user defined functions and operations to different specific types.

Further reading

The web site of Camila (http://wiki.di.uminho.pt/wiki/bin/view/PURe/Camila) provides documentation. Both library and tool are distributed as part of the UMinho Haskell Libraries and Tools.

HASP is a fork of Niklas Broberg’s Haskell Server Pages. Changes includes:

• support for all GHC extensions
• use of the GHC-api (→2.1) for byte-code compilations
• front-end based on FastCGI instead of its own web server
• minor bug fixes and performance tuning.

Some of the features implemented in HASP will be ported back into the main HSP tree. However, experimental features like byte code generation via the GHC api will most likely stay in HASP.

Further reading

• Darcs repository:

  http://darcs.haskell.org/~lemmih/hasp/

• Original HSP:

  http://www.cs.chalmers.se/~d00nibro/hsp/

Status

A complete, GHC-based implementation of the parallel Haskell extension GpH and of evaluation strategies is available. Extensions of the runtime-system and language to improve performance and support new platforms are under development.

System Evaluation and Enhancement

• We have developed an adaptive runtime environment (GRID-GUM) for GpH on computational grids. GRID-GUM incorporates new load management mechanisms that cheaply and effectively combine static and dynamic information to adapt to the heterogeneous and high-latency environment of a multi-cluster computational grid. We have made comparative measures of GRID-GUM’s performance on high/low latency grids and heterogeneous/homogeneous grids using clusters located in Edinburgh, Munich and Galashiels. Results are published in:

  Al Zain A. Implementing High-Level Parallelism on Computational Grids, PhD Thesis, Heriot-Watt University, 2006.

  Al Zain A. Trinder P.W. Loidl H.W. Michaelson G.J. Managing Heterogeneity in a Grid Parallel Haskell, Journal of Scalable Computing: Practice and Experience 7(3), (September 2006).

• The design of a generic parallel runtime environment encompassing both the Eden and GpH runtime environments is complete, but the implementation is stalled at present.

• SMP-GHC, an implementation of GpH for multi-core machines has been developed by Tim Harris, Simon Marlow and Simon Peyton Jones (→2.1).

• At St Andrews GpH is being used as a vehicle for investigating scheduling on the GRID.
• We are teaching parallelism to undergraduates using GpH at Heriot-Watt and Phillips Universitat Marburg.

GpH Applications

• GpH is being used to parallelise the GAP mathematical library in an EPSRC project (GR/R91298).

• As part of the SCIEnce EU FP6 I3 project (026133) that started in April 2006 we will use GpH and Java to provide access to Grid services from Computer Algebra(CA) systems, including GAP and Maple. We will both produce Grid-parallel implementations of common CA library functions, and also wrap CA systems as Grid services.

Implementations

The GUM implementation of GpH is available in two development branches.

• The stable branch (GUM-4.06, based on GHC-4.06) is available for RedHat-based Linux machines. The stable branch is available from the GHC CVS repository via tag gum-4-06.
• The unstable branch (GUM-5.02, based on GHC-5.02) is currently being tested on a Beowulf cluster. The unstable branch is available from the GHC CVS repository via tag gum-5-02-3.

Our main hardware platform are Intel-based Beowulf clusters. Work on ports to other architectures is also moving on (and available on request):

• A port to a Sun-Solaris shared-memory machine exists but currently suffers from performance problems.
• A port to a Mosix cluster has been built in the Metis project at Brooklyn College, with a first version available on request from Murray Gross (→7.3.4).

Further reading

• GpH Home Page:

  http://www.macs.hw.ac.uk/~dsg/gph/

• Stable branch binary snapshot:

  ftp://ftp.macs.hw.ac.uk/pub/gph/gum-4.06-snap-i386-unknown-linux.tar

• Stable branch installation instructions:

  ftp://ftp.macs.hw.ac.uk/pub/gph/README.GUM

Contact

<gph at macs.hw.ac.uk>, <mgross at dorsai.org>

GdH supports distributed stateful interactions on multiple locations. It is a conservative extension of both Concurrent Haskell and GpH (→3.2.2), enabling the distribution of the stateful IO threads of the former on the multiple locations of the latter. The programming model includes forking stateful threads on remote locations, explicit communication over channels, and distributed exception handling.

Status

An alpha-release of the GdH implementation is available on request <gph at macs.hw.ac.uk>. It shares substantial components of the GUM implementation of GpH (Glasgow parallel Haskell) (→3.2.2).

Applications and Evaluation

• EPSRC project High Level Techniques for Distributed Telecommunications Software (GR/R88137) has recently been completed (February 2006). The project was collaboration between Heriot-Watt University and Motorola UK Research Labs, and amongst other activities evaluated GdH and Erlang as technologies for distributed telecoms software in comparison to C++/CORBA. Previous publications appear on the project page, and some recent results are given in the papers below. The latter paper compares Erlang, GdH and C++ for engineering a medium-scale (14K lines of C++, 4K lines of Erlang, and 0.5K lines of GdH) telecoms component.

  Nystrom J.H. Trinder P.W. King D.J. Are High-level Languages suitable for Robust Telecoms Software? Proc. 24th Int. Conference on Computer Safety, Reliability and Security (SAFECOMP’05), Fredrikstad, Norway (September 2005).

  http://www.macs.hw.ac.uk/~dsg/telecoms/publications/SafeComp2005.pdf Nystrom, J.H., Trinder, P.W., King,D.J. A Comparative Evaluation of Three High-level Distributed Languages for Telecoms Software. In preparation.

• There is a forthcoming Ph.D. thesis on the design, implementation and use of GdH by Robert Pointon.

Further reading

• The GdH homepage:

  http://www.macs.hw.ac.uk/~dsg/gdh/

Description

Eden has been jointly developed by two groups at Philipps Universität Marburg, Germany and Universidad Complutense de Madrid, Spain. The project has been ongoing since 1996. Currently, the team consists of the following people:

Eden extends Haskell with a small set of syntactic constructs for explicit process specification and creation. While providing enough control to implement parallel algorithms efficiently, it frees the programmer from the tedious task of managing low-level details by introducing automatic communication (via head-strict lazy lists), synchronisation, and process handling.

Eden’s main constructs are process abstractions and process instantiations. The function process :: (a -> b) -> Process a b embeds a function of type (a -> b) into a process abstraction of type Process a b which, when instantiated, will be executed in parallel. Process instantiation is expressed by the predefined infix operator ( # ) :: Process a b -> a -> b. Higher-level coordination is achieved by defining skeletons, ranging from a simple parallel map to sophisticated replicated-worker schemes. They have been used to parallelise a set of non-trivial benchmark programs.

Eden has been implemented by modifying the parallel runtime system GUM of GpH (→3.2.2). Differences include stepping back from a global heap to a set of local heaps to reduce system message traffic and to avoid global garbage collection. The current (freely available) implementation is based on GHC 5.02.3. A source code version is available from the Eden web page. Installation support will be provided if required.

Survey and standard reference

Rita Loogen, Yolanda Ortega-Mallén and Ricardo Peña: Parallel Functional Programming in Eden, Journal of Functional Programming 15(3), 2005, pages 431-475 (Special Issue on Functional Approaches to High-Performance Parallel Programming)

Recent and Forthcoming Publications

• Jost Berthold, Rita Loogen: The Impact of Dynamic Channels on Functional Topology Skeletons, Parallel Processing Letters, to appear 2006.

• Steffen Priebe: Dynamic Task Generation and Transformation within a Nestable Workpool Skeleton, Euro-Par 2006, Dresden, to appear.

Current Activities

• Yolanda and Mercedes analyse Eden skeletons using an implementation of its operational semantics in Maude.

• Jost continues his work on a more general implementation of parallel Haskell dialects in a shared runtime system.

• Steffen continues his work on the polytypic skeleton library for Eden making use of the new meta-programming facilities in GHC.

• Jost and Rita continue working on the skeleton library.

Further reading

http://www.mathematik.uni-marburg.de/~eden

Epigram is a prototype dependently typed functional programming language, equipped with an interactive editing and typechecking environment. High-level Epigram source code elaborates into a dependent type theory based on Zhaohui Luo’s UTT. The definition of Epigram, together with its elaboration rules, may be found in ‘The view from the left’ by Conor McBride and James McKinna (JFP 14 (1)).

Motivation

Simply typed languages have the property that any subexpression of a well typed program may be replaced by another of the same type. Such type systems may guarantee that your program won’t crash your computer, but the simple fact that True and False are always interchangeable inhibits the expression of stronger guarantees. Epigram is an experiment in freedom from this compulsory ignorance.

Specifically, Epigram is designed to support programming with inductive datatype families indexed by data. Examples include matrices indexed by their dimensions, expressions indexed by their types, search trees indexed by their bounds. In many ways, these datatype families are the progenitors of Haskell’s GADTs, but indexing by data provides both a conceptual simplification – the dimensions of a matrix are numbers – and a new way to allow data to stand as evidence for the properties of other data. It is no good representing sorted lists if comparison does not produce evidence of ordering. It is no good writing a type-safe interpreter if one’s typechecking algorithm cannot produce well-typed terms.

Programming with evidence lies at the heart of Epigram’s design. Epigram generalises constructor pattern matching by allowing types resembling induction principles to express as how the inspection of data may affect both the flow of control at run time and the text and type of the program in the editor. Epigram extracts patterns from induction principles and induction principles from inductive datatype families.

Current Status

Whilst at Durham, Conor McBride developed the Epigram prototype in Haskell, interfacing with the xemacs editor. Nowadays, a team of willing workers at the University of Nottingham are developing a new version of Epigram, incorporating both significant improvements over the previous version and experimental features subject to active research.

The first steps have been made in collecting recurrent programs and examples in some sort of standard library. There’s still a great deal of cleaning up to do, but progress is being made.

The Epigram system has also been used succesfully by Thorsten Altenkirch in his undergraduate course on Computer Aided Formal Reasoning for two years http://www.cs.nott.ac.uk/~txa/g5bcfr/. Several final year students have successfully completed projects that involved both new applications of and useful contributions to Epigram.

Peter Morris is working on how to build the datatype system of Epigram from a universe of containers. This technology would enable datatype generic programming from the ground up. Central to these ideas is the concept of indexed container that has been developed recently. There are ongoing efforts to elaborate the ideas in Edwin Brady’s PhD thesis about efficiently compiling dependently typed programming languages.

Joel Wright has started writing a stand alone editor for Epigram using Gtk2Hs (→4.8.1). Thanks to a most helpful visit from Duncan Coutts and Axel Simon, two leading Gtk2Hs developers, we now have the beginnings of a structure editor for Epigram 2.

There has also been steady progress on Epigram 2 itself. The type theoretic basis underpinning Epigram has been further developed to incorporate observational type theory. The lion’s share of the core theory has already been implemented, but there is still plenty of work to do.

Whilst Epigram seeks to open new possibilities for the future of strongly typed functional programming, its implementation benefits considerably from the present state of the art. Our implementation makes considerable use of applicative functors, higher-kind polymorphism and type classes. Moreover, its denotational approach translates Epigram’s lambda-calculus directly into Haskell’s. On a more practical note, we have recently shifted to the darcs version control system and cabal framework.

Epigram source code and related research papers can be found on the web at http://www.e-pig.org and its community of experimental users communicate via the mailing list <epigram at durham.ac.uk>. The current implementation is naive in design and slow in practice, but it is adequate to exhibit small examples of Epigram’s possibilities. The new implementation, whose progress can be observed at http://www.e-pig.org/epilogue/ will be much less rudimentary.

Chameleon is a Haskell style language which integrates sophisticated reasoning capabilities into a programming language via its CHR programmable type system. Thus, we can program novel type system applications in terms of CHRs which previously required special-purpose systems.

Latest developments

Jeremy Wazny successfully defended his PhD thesis on Type inference and type error diagnosis for Hindley/Milner with Extensions. This thesis summarizes to a large extent the theoretical underpinnings behind Chameleon. A copy can be downloaded via http://www.comp.nus.edu.sg/~sulzmann/chameleon/.

The latest available Chameleon version is from July 2005. This version is known to have bugs. We are currently working on a much improved version which will be available in the third quarter of 2006. An announcement will be sent to the Haskell mailing list once the new version is ready.

Further reading

http://www.comp.nus.edu.sg/~sulzmann/chameleon/

XHaskell is an extension of Haskell with XDuce style regular expression types and regular expression pattern matching. We have much improved the implementation which can found under the XHaskell home-page.

Further reading

http://www.comp.nus.edu.sg/~luzm/xhaskell/

With the generation of understandable type error messages in mind we have devised a constraint based type inference method in the form of the Top library. This library is used in the Helium compiler (for learning Haskell) developed at Universiteit Utrecht. Our philopsophy is that no single type inferencer works best for everybody all the time. Hence, we want a type inferencer adaptable to the programmer’s needs without the need for him to delve into the compiler. Our goal is to devise a library which helps compiler builders add this kind of technology to their compiler.

The main outcome of our work is the Top library which has the following characteristics:

• It uses constraints to build a constraint tree which follows the shape of the abstract syntax tree.

• These constraints can be ordered in various ways into a list of constraints

• Various solvers (specifically a fast greedy one, a slower global one, and the chunky solver which combines the two) exist to solve the resulting list of constraints.

• The library is easily extended with new constraints, and the type graph implementation includes various heuristics to find out what is the most likely source of an inconsistency. Some of these heuristics are very general, others are more tailored towards Haskell. Some the heuristics are fixed, like a majority heuristics which takes into account that there is ‘more’ evidence that a certain constraint is the root of an inconsistency. In addition, there are also heuristics specified from the outside. By means of a siblings directive, a programmer may specify that his experiences are that certain functions are often mixed up. As a result, a compiler may give the hint that (++) should be used instead of (:), because (++) happens to fit in the context.

• It preserves type synonyms as much as possible,

• We have support for type class directives. It allows programmers to for instance specify that certain instances will never occur. The type inferencer can use this information to give better error messages. Other directives can be used to specify additional invariants on type classes. For instance, that two type classes do not share a common type (Fractional vs. Integral). A paper about this subject will find its way into PADL 2005. Although we have implemented this into Helium, the infrastructure applies as well to other systems of qualified types.

• The various phases in type inferencing have now been integrated by a slightly different, more general choice of constraints.

An older version of the underlying machinery for the type inferencer has been published in the Proceedings of the Workshop of Immediate Applications of Constraint Programming held in October 2003 in Kinsale, Ireland.

The entire library is parameterized in the sense that for a given compiler we can choose which information we want to drag around.

The library has been used extensively in the Helium compiler, so that Helium can be seen as a case study in applying Top in a real compiler. In addition to the above, Helium also

• has a logging facility for building collections of correct and incorrect Haskell programs (including time line information),

• has a run-time parameters for experimenting with various solvers and constraint orderings.

• gives precise error location information,

• supports specialized type rules, which are a means to override the order in which certain expressions are inferenced and how the type error messages are formulated (see our paper presented at ICFP ’03). These type rules are especially useful for making the type error messages for domain specific extensions to Haskell correspond more closely to the domain, instead of the underlying Haskell language structures. The specialized type rules are automatically checked for soundness and completeness with respect to the original type system.

Further reading

• Project website:

  http://www.cs.uu.nl/wiki/Top/WebHome

The purpose of the EHC project is to provide a description of a Haskell compiler which is as understandable as possible so it can be used for education as well as research.

For its description an Attribute Grammar system (AG) is used as well as other formalisms allowing compact notation like parser combinators. For the description of type rules, and the generation of an AG implementation for those type rules, we recently started using the Ruler system (→5.5.3) (included in the EHC project).

The EHC project also tackles other issues:

• In order to avoid overwhelming the innocent reader, the description of the compiler is organised as a series of increasingly complex steps. Each step corresponds to a Haskell subset which itself is an extension of the previous step. The first step starts with the essentials, namely typed lambda calculus.

• Each step corresponds to an actual, that is, an executable compiler. Each of these compilers is a compiler in its own right so experimenting can be done in isolation of additional complexity introduced in later steps.

• The description of the compiler uses code fragments which are retrieved from the source code of the compilers. In this way the description and source code are kept synchronized.

Currently EHC already incorporates more advanced features like higher-ranked polymorphism, partial type signatures, class system, explicit passing of implicit parameters (i.e. class instances), extensible records, kind polymorphism.

Part of the description of the series of EH compilers is available as a PhD thesis, which incorporates previously published material on the EHC project.

The compiler is used for small student projects as well as larger experiments such as the incorporation of an Attribute Grammar system.

We also hope to provide a Haskell frontend dealing with all Haskell syntactic sugar omitted from EHC.

Further reading

• Homepage:

  http://www.cs.uu.nl/groups/ST/Ehc/WebHome

• Attribute grammar system:

  http://www.cs.uu.nl/wiki/HUT/AttributeGrammarSystem

• Parser combinators:

  http://www.cs.uu.nl/wiki/HUT/ParserCombinators

Software development often consists of designing a (set of mutually recursive) datatype(s), to which functionality is added. Some functionality is datatype specific, other functionality is defined on almost all datatypes, and only depends on the type structure of the datatype.

Examples of generic (or polytypic) functionality defined on almost all datatypes are the functions that can be derived in Haskell using the deriving construct, storing a value in a database, editing a value, comparing two values for equality, pretty-printing a value, etc. Another kind of generic function is a function that traverses its argument, and only performs an action at a small part of its argument. A function that works on many datatypes is called a generic function.

There are at least two approaches to generic programming: use a preprocessor to generate instances of generic functions on some given datatypes, or extend a programming language with the possibility to define generic functions. The techniques behind some of these ideas are given in a separate subsection. In Comparing approaches to generic programming in Haskell (in the lecture notes of the Spring School on Datatype-Generic Programming 2006, held in Nottingham, April 2006, to appear in LNCS), Ralf Hinze, Johan Jeuring and Andres Löh compare 8 different approaches to generic programming in Haskell, both lightweight approaches and language extensions. Most of the approaches discussed in this and previous versions of the Communities report are addressed. In the same set of lecture notes, Jeremy Gibbons discusses the various interpretations of the word ‘generic’.

Preprocessors

DrIFT is a preprocessor which generates instances of generic functions. It is used in Strafunski (→4.3.2) to generate a framework for generic programming on terms. New releases appear regularly, the latest is 2.2.0 from April 2006.

Languages

Light-weight generic programming There are a number of approaches to light-weight generic programming.

Generic functions for data type traversals can (almost) be written in Haskell itself (using many of the extensions of Haskell provided by GHC), as shown by Ralf Lämmel and Simon Peyton Jones in the ‘Scrap your boilerplate’ (SYB) approach (http://www.cs.vu.nl/boilerplate/). The SYB approach to generic programming in Haskell has been further elaborated in the recently published (in FLOPS ’06) paper “Scrap Your Boilerplate” Reloaded and “Scrap Your Boilerplate” Revolutions (to appear in MPC’06). In these papers Ralf Hinze, Andres Löh, and Bruno Oliveira show, amongst others, how by viewing the SYB approach in a particular way, the choice of basic operators becomes obvious.

In Open data types and open functions (to appear at PPDP’06), Andres Löh and Ralf Hinze propose to add extensible data types to Haskell, and they show how to use these extensible data types to implement generic functions in a light-weight approach to generic programming.

In Generics as a Library, Bruno Oliveira, Ralf Hinze and Andres Löh show how to extend Ralf Hinze’s “Generic for the Masses” approach to be able to extend generic functions with ad-hoc behaviour for new data types.

Finally, in Generic programming, NOW! (in the lecture notes of the Spring School on Datatype-Generic Programming 2006, held in Nottingham, April 2006, to appear in LNCS), Ralf Hinze and Andres Löh show how GADTs can be used to implement many of the lightweight approaches to generic programming directly in Haskell.

Generic Haskell In Generic views on data types (to appear in MPC’06) Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriguez show how to add views on data types to Generic Haskell. Using these views, typical fixed-point functions such as determining the recursive children of a constructor of a recursive data type can be combined with the usual Generic Haskell programs in a single program. The Generic Haskell compiler has been extended with views (available via svn).

Other In Generic Programming with Sized Types (to appear in MPC’06), Andreas Abel defines a generic programming language in which you can only define terminating generic programs, by adding sizes to types.

In iData for the World Wide Web: programming interconnected web forms (in FLOPS’06), Rinus Plasmeijer and Peter Achten show how to use the generic programming extension of Clean for implementing web forms.

Techniques

Jeremy Gibbons’ tutorial Design Patterns as Higher-Order Datatype-Generic Programs from ECOOP and OOPSLA 2005 has been written up as a paper, http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/#hodgp. He and Bruno Oliveira have also written about The Essence of the Iterator Pattern as a higher-order datatype-generic program (http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/#iterator), in terms of McBride and Paterson’s idioms or applicative functors.

The Spring School on Datatype-Generic Programming has taken place in Nottingham, UK, April 23 - 26, see http://www.cs.nott.ac.uk/ssdgp2006/. There were lectures about comparing approaches to generic programming in Haskell, generic programming in Haskell using GADTs, the implementation of patterns as generic programs, generic programming in Omega (a Haskell-like functional programming language with a limited form of dependent types), and in Epigram (→3.3.1) (a dependently typed programming language).

Current Hot Topics

Generic Haskell: finding transformations between data types. Adding type inference to the compiler. Other: the relation between generic programming and dependently typed programming; the relation between coherence and generic programming; methods for constructing generic programs. Methods for testing generic programs.

Hopefully there will be papers about these topics in the next Workshop on Generic Programming (colocated with ICFP 2006): http://www.informatik.uni-bonn.de/~ralf/wgp2006.html.

Further reading

• http://repetae.net/john/computer/haskell/DrIFT/
• http://www.cs.chalmers.se/~patrikj/poly/
• http://www.generic-haskell.org/
• http://www.cs.vu.nl/Strafunski/
• http://www.cs.vu.nl/boilerplate/

Background

The Haskell Cabal is a Common Architecture for Building Applications and Libraries. It is an API distributed with GHC (→2.1), NHC98 (→2.3), and Hugs (→2.2) which allows a developer to easily group together a set of modules into a package.

HackageDB (Haskell Package Database) is an online database of packages which can be interactively queried by client-side software such as the prototype cabal-get. From HackageDB, an end-user can download and install packages which conform to the Cabal interface.

The Haskell Implementations come with a good set of standard libraries included, but this set is constantly growing and is maintained centrally. This model does not scale up well, and as Haskell grows in acceptance, the quality and quantity of available libraries is becoming a major issue.

It can be very difficult for an end user to manage a wide variety of dependencies between various libraries, tools, and Haskell implementations, and to build all the necessary software at the correct version numbers on their platform: previously, there was no generic build system to abstract away differences between Haskell Implementations and operating systems.

HackageDB and The Haskell Cabal seek to provide some relief to this situation by building tools to assist developers, end users, and operating system distributors.

Such tools include a common build system, a packaging system which is understood by all of the Haskell Implementations, an API for querying the packaging system, and miscellaneous utilities, both for programmers and end users, for managing Haskell software.

Further reading

• http://www.haskell.org/cabal
• http://hackage.haskell.org/ModHackage/Hackage.hs?action=home

Hacanon-light is a lightweight FFI library that uses the Data Interface Scheme (DIS) from Hacanon (http://haskell.org/hawiki/Hacanon) and Template Haskell to provide a high level interface to marshaling/un-marshaling. It differs from Hacanon taking a passive role in the binding process; it won’t use or validate itself from any foreign header files.

Hacanon-light is meant to be used together with Zeroth (→5.5.2).

Further reading

• Darcs repository:

  http://darcs.haskell.org/~lemmih/hacanon-light

HODE is a binding to the Open Dynamics Engine. ODE is an open source, high performance library for simulating rigid body dynamics.

HODE uses Hacanon-light (→4.2.1) to simplify the binding process and Zeroth (→5.5.2) to avoid linking with Template Haskell.

Further reading

• Darcs repository:

  http://darcs.haskell.org/~lemmih/hode

• ODE:

  http://ode.org

The PFP library is a collection of modules for Haskell that facilitates probabilistic functional programming, that is, programming with stochastic values. The probabilistic functional programming approach is based on a data type for representing distributions. A distribution represent the outcome of a probabilistic event as a collection of all possible values, tagged with their likelihood.

A nice aspect of this system is that simulations can be specified independently from their method of execution. That is, we can either fully simulate or randomize any simulation without altering the code which defines it.

The library was developed as part of a simulation project with biologists and genome researchers. We plan to apply the library to more examples in this area. Future versions will hopefully contain a more systematically documented list of examples.

Since the last report, the implementation has undergone only minor changes, and no new release has been made yet. The web site has been updated slightly and contains the latest papers on the subject.

Further reading

http://eecs.oregonstate.edu/~erwig/pfp/

Hmm is a small Haskell library to parse and verify Metamath databases.

Metamath (http://metamath.org) was conceived and almost completely implemented by Norman Megill. It a project for formalizing mathematics, a file format for specifying machine-checkable proofs, and a program for generating and verifying this file format. Already more than 6000 proofs have been verified from the axioms of set theory.

Version 0.1 of Hmm has been released on October 17th, 2005.

The development version can be found at http://www.solcon.nl/mklooster/repos/hmm/. This is a darcs repository (→6.6).

Hmm can’t currently do more than just read and verify a Metamath file. However, the longer-term goal is to generate calculational proofs from Metamath proofs. As an example, the Metamath proof that cross-product distributes over union (see http://us.metamath.org/mpegif/xpundi.html) could be visualized something like this:

I am working towards this goal, slowly and step by step.

Further reading

http://www.solcon.nl/mklooster/repos/hmm/

magic-haskell is a binding to the libmagic library. With magic-haskell, you can determine the type of a file by looking at its contents rather than its name. This library also can yield the MIME type of a file by looking at its contents.

This is often a more useful method than looking at a file’s name since it can yield correct results even if a file’s extension is missing or misleading.

Further reading

http://quux.org/devel/magic-haskell

MissingH is a library designed to provide the little “missing” features that people often need and end up implementing on their own. Its focus is on list, string, and IO features, but extends into other areas as well. The library is 100%pure Haskell code and has no dependencies on anything other than the standard libraries distributed with current versions of GHC and Hugs.

In addition to the smaller utility functions, recent versions of MissingH have added a complete FTP client and server system, a virtualized I/O infrastructure similar to Python’s file-like objects, a virtualized filesystem infrastructure, a MIME type guesser, a configuration file parser, GZip decompression support in pure Haskell, a DBM-style database virtualization layer, and a modular logging infrastructure, complete with support for Syslog.

Future plans for MissingH include adding more network client and server libraries, support for a generalized URL downloading scheme that will work across all these client libraries, and enhancing the logging system.

This library is licensed under the GNU GPL.

Further reading

http://quux.org/devel/missingh

MissingPy is really two libraries in one. At its lowest level, MissingPy is a library designed to make it easy to call into Python from Haskell. It provides full support for interpreting arbitrary Python code, interfacing with a good part of the Python/C API, and handling Python objects. It also provides tools for converting between Python objects and their Haskell equivalents. Memory management is handled for you, and Python exceptions get mapped to Haskell Dynamic exceptions.

At a higher level, MissingPy contains Haskell interfaces to some Python modules. These interfaces include support for the Python GZip and BZip2 modules (provided using the HVIO abstraction from MissingH), and support for Python DBM libraries (provided using AnyDBM from MissingH (→4.2.9)). These high-level interfaces look and feel just like any pure Haskell interface.

Future plans for MissingPy include an expansion of the higher-level interface to include such things as Python regexp libraries, SSL support, and LDAP support.

This library is licensed under the GNU GPL.

Further reading

http://quux.org/devel/missingpy

The Utrecht parsing Library and the associated Attribute Grammar System have been made available as cabal packages (→4.1.1), and as such may be easier to install.

The systems have been succesfully used by Niels van der Velde, one of our Master students, as part of a toolchain to assist in the parallelisation of C code. It seems that the lazy evaluation used inside is requiring quite some memory footprint.

One of our other master students, Joost Verhoog, is about to complete the alternative path to code-generation for the AG system, in which we follow te more traditional multi-pass attribute grammar evaluation schemes, as explained in the thesis of Joao Saraiva http://www.cs.uu.nl/wiki/Swierstra/SupervisedTheses. Our hope is that this will alleviate the aforementioned problem.

Strafunski is a Haskell-based bundle for generic programming with functional strategies, that is, generic functions that can traverse into terms of any type while mixing type-specific and uniform behaviour. This style is particularly useful in the implementation of program analyses and transformations.

Strafunski bundles the following components:

• the library StrategyLib for generic traversal and others;
• precompilation support for user datatypes based on DrIFT (→3.4);
• the library ATermLib for data exchange;
• the tool Sdf2Haskell (→5.2.6) for external parser and pretty-print integration.

The Strafunski-style of generic programming can be seen as a lightweight variant of generic programming (→3.4) because no language extension is involved, but generic functionality simply relies on a few overloaded combinators that are derived per datatype. By default, Strafunski relies on DrIFT to derive the appropriate class instances, but a simple switch is offered to rely on the “Scrap your boilerplate” (→3.4) model as available in the Data.Generics library.

Strafunski is used in the HaRe project (→5.3.3) and in the UMinho Haskell Libraries and Tools to provide analysis and transformation functionality for languages such as XML Schema, Java, VDM, SQL, spreadsheets, and Haskell itself.

Further reading

http://www.cs.vu.nl/Strafunski/

hs-plugins is a library for dynamic loading and runtime compilation of Haskell modules, for Haskell and foreign language applications. It can be used to implement application plugins, hot swapping of modules in running applications, runtime evaluation of Haskell, and enables the use of Haskell as an application extension language. Version 1.0rc1 has been released.

Further reading

• Source and documentation can be found at:

  http://www.cse.unsw.edu.au/~dons/hs-plugins/

• The source repository is available:

  darcs get

  http://www.cse.unsw.edu.au/~dons/code/hs-plugins/

ldap-haskell is a Haskell binding to C-based LDAP libraries such as OpenLDAP. With ldap-haskell, you can interrogate an LDAP directory, update its entries, add data to it, etc. ldap-haskell provides an interface to all the most common operations you would need to perform with an LDAP server.

Further reading

darcs get http://darcs.complete.org/ldap-haskell

The “time” package replaces the current library for handling time. The “main” modules feature representation of UTC and UT1, as well as the proleptic Gregorian calendar, time-zones, and functions for strftime-style formatting. Additional “second-level” modules handle TAI, leap-seconds, Julian, ISO 8601 week, and “year and day” calendars, calculation of Easter, and POSIX time. Modules are organised under Data.Time to distinguish from the old System.Time.

The source is in the darcs (→6.6) repository “time” in the current standard libraries, and is built by the GHC library build process. Largely complete, remaining work includes putting use examples in the documentation, and integrating existing unit tests into the testsuite repository.

Further reading

http://semantic.org/TimeLib/

Takusen is a library for accessing DBMS’s. It is a low-level library like HSQL, in the sense that it is used to issue SQL statements. Takusen’s ‘unique-selling-point’ is a design for processing query results using a left-fold enumerator. For queries the user creates an iteratee function, which is fed rows one-at-a-time from the result-set. We also support processing query results using a cursor interface, if you require finer-grained control. Currently we fully support Oracle, Sqlite, and PostgreSQL.

Since the last report we have implemented a new internal interface for prepared statements, and improved the PostgreSQL back-end. We have also (very recently!) moved from SourceForge to a darcs repo (→6.6) at haskell.org, and hope to present a new release soon from this repo.

Plans for the future include:

• support multiple result-sets (from nested cursors or stored procedures)
• cabalise (→4.1.1)
• use Ashley Yakeley’s new Time library (→4.4.3) instead of CalendarTime
• resurrect MS SQL Server backend
• ODBC backend

Further reading

http://darcs.haskell.org/takusen/devel/

HaskellDB is a library for accessing databases through Haskell in a type safe and declarative way. It completely hides the underlying implementation and can interface with several popular database engines through either HSQL or wxHaskell. HaskellDB was originally developed by Daan Leijen. This latest incarnation of HaskellDB was produced as part of a student project at Chalmers University of Technology.

The current version supports:

• Completely type safe queries on databases
• Support for MySQL, PostgreSQL, SQLite and ODBC through HSQL
• Support for ODBC through wxHaskell
• Automatic conversion between Haskell types and SQL types
• Support for bounded strings
• Dynamic loading of drivers via hs-plugins (→4.4.1)

Future possible developments include:

• Support for more backends (Oracle)
• Support for non-SQL backends
• Driver-specific code generation. This is needed for non-SQL backends, and we have discovered that no SQL databases implement the standard in quite the same way

There hasn’t been a new release for a while, but an experimental Cabalized (→4.1.1) version is available in the CVS repository. New developers are very welcome to join the project.

Further reading

http://haskelldb.sourceforge.net/

Haskell implementations come with modules to handle Maps, Sets, and other common data structures. We call these modules the Standard Collection Libraries. The goal of this project is to improve those.

Beside incremental improvement of the current code (stress testing, ironing bugs out, small improvements of API, …), a package has been created to gather collection-related code that would not fit in the base package yet. This includes changes that are either potentially de-stabilizing, controversial or otherwise experimental.

This new package features notably:

• New data structures, including AVL-tree based Maps and Sets (thanks to Adrian Hey);
• A class-based framework for collection data-types, equipped with polymorphic testsuite and benchmarks.

I plan to submit this package to intensive testing and review, in order to be able to include parts of it in the standard.

Further reading

http://hackage.haskell.org/trac/ghc/wiki/CollectionLibraries

Monads are very common in Haskell programs and yet every time one needs a monad, it has to be defined from scratch. This is boring, error prone and unnecessary. Many people have their own libraries of monads, and it would be nice to have a common one that can be shared by everyone. Some time ago, Andy Gill wrote the monad transformer library that has been distributed with most Haskell implementations, but he has moved on to other jobs, so the library was left on its own. I wrote a similar library (before I knew of the existence of Andy’s library) and so i thought i should combine the two. The “new” monadic library is not really new, it is mostly reorganization and cleaning up of the old library. It has been separated from the “base” library so that it can be updated on its own.

Since the last report, there has been a new major release of the monad library (version 2.0), and a minor update (version 2.0.1).

Users interested in using the library can download it (with documentation) from the library’s website.

Further reading

http://www.cse.ogi.edu/~diatchki/monadLib/

Data.ByteString (formerly FPS) provides packed strings (byte arrays held by a ForeignPtr), along with a list interface to these strings. It lets you do extremely fast IO in Haskell; in some cases, even faster than typical C implementations, and much faster than [Char]. It uses a flexible “foreign pointer” representation, allowing the transparent use of Haskell or C code to manipulate the strings.

Data.ByteString is written in Haskell98 plus the foreign function interface and cpp. It has been tested succesfully with GHC 6.4 and 6.5, and hugs March 2005.

Many improvements have been made over the last 6 months, including the new Data.ByteString.Lazy module, successfully used on terabyte data quantities. Data.ByteString will be part of the GHC base libraries in the GHC 6.6 release.

Further reading

• Source and documentation can be found at

  http://www.cse.unsw.edu.au/~dons/fps.html

• The source repository is available:

  darcs get

  http://www.cse.unsw.edu.au/~dons/code/fps

The hierarchy of numerical type classes is revised and oriented at algebraic structures. Axiomatics for fundamental operations are given as QuickCheck properties, superfluous super-classes like Show are removed, semantic and representation-specific operations are separated, the hierarchy of type classes is more fine grained, and identifiers are adapted to mathematical terms.

There are both certain new type classes representing algebraic structures and new types of mathematical objects.

Currently supported algebraic structures are

• group (additive),
• ring,
• principal ideal domain,
• field,
• algebraic closures,
• transcendental closures,
• module and vector space,
• normed space,
• lattice,
• differential algebra.

There is also a collection of mathematical object types, which is useful both for applications and testing the class hierarchy. The types are

• complex number,
• residue class,
• infinite precision number in an arbitrary positional system (initial support),
• polynomial, power series, Laurent series
• root set of a polynomial,
• numbers equipped with units (dynamic checks only).

Using the revised system requires hiding some of the standard functions provided by Prelude, which is fortunately supported by GHC (→2.1). The library has basic Cabal (→4.1.1) support.

Future plans

Collect more Haskell code related to mathematics, e.g. for linear algebra. Study of alternative numeric type class proposals and common computer algebra systems. Ideally each data type resides in a separate module. However this leads to mutual recursive dependencies, which cannot be resolved if type classes are mutually recursive.

A still unsolved problem arises for e.g. residue classes, matrix computations, infinite precision numbers and fixed point numbers. It should be possible to assert statically that the arguments of a function are residue classes with respect to the same divisor, or that they are vectors of the same size. Possible ways out are encoding values in types or local type class instances. The latter one is still neither proposed nor implemented in any Haskell compiler.

Further reading

http://darcs.haskell.org/numericprelude/

An efficient implementation of ordered sequences, based on (external, node oriented) 2-3 finger search trees as described in a recent paper by Ralf Hinze (see below).

With regard to asymptotic complexity, 2-3 finger search trees seem to be the best known purely functional implementations of ordered sequences, with the following amortized time bounds:

• member, insert, delete, split: O(log(min(d,n-d)))
• minimum, maximum, deleteMin, deleteMax: O(1)
• merge: O(ns*log(nl/ns))

The project started as an exercise to explore the intriguing possibilities of nested data types to statically check data-structural invariants. One of my interests was to find out how much this helps development in practice. The results are nothing less than impressive to me. I am sure I would never have been able to produce anything as complicated with such a (relatively) low effort, had not the type system constantly guided me in the right direction.

Meanwhile, I think this could evolve into a generally useful library. A lot of work remains to be done, though: currently the library provides only the basic functionality and I have just started to get into performance measurements. I suspect some optimizations are possible, but haven’t yet looked into it very deeply. The code is mostly tested (and specified, thanks to QuickCheck), but hasn’t been used in a real application.

The library is not yet released, mainly because (lacking a personal homepage) I don’t have a convenient place on the web to host it. However, I plan to release a first alpha version soon.

Further reading

• Ralf Hinze, Numerical Representations as Higher-Order Nested Datatypes, Technical Report IAI-TR-98-12, Institut für Informatik III, Universität Bonn, December 1998

  http://www.cs.bonn.edu/ralf/publications/IAI-TR-98-12.ps.gz