Improving Data Structures with Associated Types

Original .PDF

This talk describes how to view live heap structures in Haskell, including sharing and unboxing information, and then to use insights on the representation of data to improve the performance and space, for the first time, of uniform polymorphic data types by changing their representation. We’ll use associated data types to guide regular optimizations of polymorphic structures.

The library described in this talk is available on hackage, along with the visualization tool used to build it. There’s also a screencast of the visualization tool in use.

This talk was originally presented at WG2.8 in Frauenchiemsee, Germany in June 2009.

Stream Fusion for Haskell Arrays

PDF Version

Arrays have traditionally been an awkward data structure for Haskell programmers. Despite the large number of array libraries available, they have remained relatively awkward to use in comparison to the rich suite of purely functional data structures, such as fingertrees or finite maps. Arrays have simply not been first class citizens in the language.

In this talk I’ll begin with a survey of the more than a dozen array types available, including some new matrix libraries developed in the past year. I’ll then describe a new efficient, pure, and flexible array library for Haskell with a list like interface, based on work in the Data Parallel Haskell project, that employs stream fusion to dramatically reduce the cost of pure arrays. The implementation will be presented from the ground up, along with a discussion of the entire compilation process of the library, from source to assembly.

The library described in this talk is available on hackage, and is now used by a few projects, including haskell-monte-carlo haskell-pqueue-mtl haskell-statistics-fusion haskell-uvector-algorithms and Bryan O’Sullivan’s new uber benchmark suite.


This talk was originally presented at Galois on August 28th, 2008.

The Haskell Platform: Status Report: Haskell Symposium 2009

At the future of Haskell discussion, at the Haskell Symposium 2009, Duncan Coutts and I gave a status update on the Haskell Platform project: the project to build a single, shared distribution of Haskell for every platform.

DEFUN 2009: Multicore Programming in Haskell Now!

Here are the

for today’s DEFUN tutorial: Multicore Programming in Haskell Now!

Multicore computers are here: is your programming language ready for it?

Haskell is: you can take an off-the-shelf copy of GHC and write high performance parallel programs right now. This tutorial will teach you how to exploit parallelism through Haskell on your commodity multicore machine, to make your code faster. We will introduce key parallel programming models, as implemented in Haskell, including:

  • semi-explicit parallelism via sparks
  • explicit parallelism via threads and shared memory
  • software transactional memory
  • data parallelism

and look at how to build faster programs using these abstractions. We will also look at the engineering considerations when writing  parallel programs, and the tools Haskell provides for debugging and reasoning about parallel programs.

This half-day tutorial will teach intermediate functional programmers with no previous parallel programming experience how to write, reason about and run parallel Haskell programs, using a range of parallel programming models. Each model will be introduced with motivating examples, and exercises to develop familarity with the model in question. By the end you should have an understanding of which parallelism abstraction to use in which circumstance, and be able to go to work writing multicore capable programs in Haskell.

Parallel Programming in Haskell: A Reading List

I’m busy preparing a tutorial for DEFUN on Saturday, and was putting together the “further reading” slides for the attendees, so they have material to go to for deeper reading.threadscope

Here’s my basic “How to learn about parallel programming in Haskell” reading list.

Learn Parallel Haskell

Does anyone else have favourite learning materials for parallel and concurrent programming in GHC Haskell?

Haskell Popularity Rankings: September 2009

Here’s the Haskell package popularity statististics for the month of August 2009 (a couple of days early, due to ICFP travel). These are downloads of source using the logs for the Hackage package server (kindly hosted by Galois). They measure popularity of Haskell source code packages on Hackage.

haskell_universe

Headlines

  • Total Hackage downloads : 1.22 million (+82k)
  • Total Packages on Hackage : 1520 packages
  • Total Contributors : 414 developers
  • Over 80 thousand downloads in August
  • Hackage now links to distro packages where available

Top 20 most downloaded Haskell applications in August

  1. xmonad – A tiling window manager
  2. haddock – A documentation-generation tool for Haskell libraries
  3. cpphs – A liberalised re-implementation of the C pre-processor
  4. hscolour – Colourise Haskell code
  5. cabal-install – The command-line interface for Cabal and Hackage.
  6. yi – The Haskell-Scriptable Editor
  7. darcs – a distributed, interactive, smart revision control system
  8. happy – a parser generator for Haskell
  9. pandoc – Conversion between markup formats
  10. xmobar – A Minimalistic Text Based Status Bar
  11. leksah – Haskell IDE written in Haskell
  12. alex – a tool for generating lexical analysers in Haskell
  13. happstack – The haskell application server stack + code generation
  14. hlint – Source code suggestions for Haskell
  15. gitit – Wiki using happstack, git or darcs, and pandoc
  16. hoogle – Haskell API Search
  17. cabal2arch – Create Arch Linux packages from Cabal packages
  18. happs-tutorial – A Happstack Web 2.0-type demo
  19. uuagc – Attribute Grammar System of Universiteit Utrecht
  20. yst – Builds a static website from templates and data in YAML or CSV files

Top 20 Haskell libraries in August

  1. HTTP – Client-side HTTP
  2. zlib – Compression and decompression in the gzip and zlib formats
  3. binary – Binary serialisation for Haskell values using lazy ByteStrings
  4. utf8-string – Support for reading and writing UTF8 Strings
  5. haskell-src-exts – Manipulating Haskell source: abstract syntax, lexer, parser, pretty printing
  6. QuickCheck – Automatic testing of Haskell programs
  7. ghc-paths – Knowledge of GHC’s installation directories
  8. OpenGL – A binding for the OpenGL graphics system
  9. HaXml – Utilities for manipulating XML documents
  10. GLUT – A binding for the OpenGL Utility Toolkit
  11. pureMD5 – MD5 implementations that should become part of a ByteString Crypto package
  12. time – A time library
  13. terminfo – Haskell bindings to the terminfo library
  14. parsec – Monadic parser combinators
  15. X11 – A binding to the X11 graphics library
  16. regex-base – Regular expressions for Haskell
  17. network – Networking-related facilities
  18. uniplate – Uniform type generic traversals
  19. unix-compat – Portable POSIX-compatibility layer
  20. transformers – Concrete monad transformers

We can also compute the librarys and applications that had the biggest increase in downloads in August over the previous month. These libraries are increasing in use the fastest:

Top 10 rising libraries

  1. Tensor – Tensor data types
  2. ObjectName – Explicitly handled object names
  3. StateVar – State variables for OpenGL
  4. OpenGLRaw – A raw binding for the OpenGL graphics system
  5. GLURaw – A raw binding for the OpenGL graphics system
  6. text – An efficient packed Unicode text type
  7. HaXml – Utilities for manipulating XML documents
  8. MissingH – Large utility library
  9. HStringTemplate – StringTemplate implementation in Haskell
  10. derive – A program and library to derive instances for data types

Top 10 rising applications

  1. haddock – A documentation-generation tool for Haskell libraries
  2. pandoc – Conversion between markup formats
  3. gitit – Wiki using happstack, git or darcs, and pandoc
  4. yi – The Haskell-Scriptable Editor
  5. cabal2arch – Create Arch Linux packages from Cabal packages
  6. hake – make tool. ruby : rake = haskell : hake
  7. hpodder – Podcast Aggregator (downloader)
  8. nemesis – a Rake like task management tool
  9. flow2dot – generate sequence/flow diagrams from plain text source
  10. lhc – LHC Haskell Compiler

All these can be installed with:

 $ cabal install <package>

Crunch the Numbers

Here’s the data so you can see how your favourite packages are going:

And don’t forget — the Haskell Platform is cutting into cabal-install’s monopoly on distribution of Haskell code… downloads for that are counted separately.

QuickCheck – Automatic testing of Haskell programs

Haskell Package Popularity Rankings : August 2009

Back in March, I crunched the web logs for the Hackage package server (kindly hosted by Galois) to measure for the first time how popular Haskell packages were Hackage.

haskell_universe

4 months later, I’ve rerun the numbers, and have some new data.

Headlines

  • Total Hackage downloads : 1.13 million
  • Total Packages on Hackage : 1470
  • Total Contributors : 400 developers

Top 20 Haskell applications

  1. xmonad – A tiling window manager
  2. cabal-install – The command-line interface for Cabal and Hackage.
  3. haddock – A documentation-generation tool for Haskell libraries
  4. xmobar – A Minimalistic Text Based Status Bar
  5. yi – The Haskell-Scriptable Editor
  6. hscolour – Colourise Haskell code
  7. happy (+1) – a parser generator for Haskell
  8. alex (-1) – a tool for generating lexical analysers in Haskell
  9. leksah (+1) – Haskell IDE written in Haskell
  10. cpphs (+3) – A liberalised re-implementation of the C pre-processor
  11. darcs – a distributed, interactive, smart revision control system
  12. frag – A 3-D First Person Shooter Game
  13. pandoc – Conversion between markup formats
  14. uuagc – Attribute Grammar System of Universiteit Utrecht
  15. hmp3 – An ncurses mp3 player
  16. c2hs – C->Haskell FFI tool with cross-language type safety
  17. hoogle – Haskell API Search
  18. cabal-rpm – RPM package builder for Haskell Cabal source packages
  19. happs-tutorial – A Happstack Web 2.0-type demo
  20. hlint – Source code suggestions for Haskell

Top 20 Haskell libraries

  1. HTTP – Client-side HTTP
  2. zlib – Compression and decompression in the gzip and zlib formats
  3. Cabal – A framework for packaging Haskell software
  4. X11 – A binding to the X11 graphics library
  5. binary – Binary serialisation for Haskell values using lazy ByteStrings
  6. utf8-string – Support for reading and writing UTF8 Strings
  7. mtl – Monad transformer library
  8. regex-posix – POSIX regular expressions
  9. xmonad-contrib (+11) – Third party extensions for xmonad
  10. parsec (+1) – Monadic parser combinators
  11. X11-extras – (obsolete) Missing bindings to the X11 graphics library
  12. network – Networking-related facilities
  13. regex-base – Regular expressions for Haskell
  14. QuickCheck – Automatic testing of Haskell programs
  15. bytestring – Fast, packed, strict and lazy byte arrays
  16. HaXml – Utilities for manipulating XML documents
  17. hslogger – Versatile logging framework
  18. terminfo – Haskell bindings to the terminfo library
  19. time – A time library
  20. regex-compat – API compatible regular expressions

Essentially unchanged since March in overall rankings.

What if we look at the fastest rising packages though? These are the 25 packages that climbed the most in overall rankings in the 4 months to August 2009, and by how many rankings they improved.

Top 5 fastest rising applications

  1. MazesOfMonad 1266 – Console-based Role Playing Game
  2. bloxorz 1254 – OpenGL logic game
  3. HPong 1166 – A simple OpenGL Pong game based on GLFW
  4. darcs-beta 1131 – beta branch of darcs
  5. Bookshelf 1012 – A simple document organizer with some wiki functionality

Top 5 fastest rising libraries

  1. hashed-storage 1208 – Hashed file storage support code
  2. atom 1200 – A DSL for embedded hard realtime applications
  3. buster 1197 – Almost but not quite entirely unlike FRP GUI library
  4. hack 1190 – a Haskell Webserver Interface
  5. elerea 1174 – A minimalistic FRP library

All these can be installed with:

 $ cabal install <package>

Crunch the Numbers

Here’s the data so you can see how your favourite packages are going:

You can also get the month by month totals:

And don’t forget — the Haskell Platform is cutting into cabal-install’s monopoly on distribution of Haskell code… downloads for that are counted separately.

QuickCheck – Automatic testing of Haskell programs
Follow

Get every new post delivered to your Inbox.

Join 67 other followers