New Adventures in Software

Cedric Beust has posted a programming challenge on his blog.  Seeing as I have nothing better to do, I thought I’d give it a go in Haskell.  Here is a naive brute-force solution that I came up with.  I’m sure there are many optimisations that can be made.

import List(nub)
 
-- Predicate that returns True if a number contains no duplicate digits.
noDuplicateDigits :: Int -> Bool
noDuplicateDigits n = length (nub (digits)) == length digits
                      where digits = show n
 
values :: Int -> [Int]
values n = [x | x <- [1..n], noDuplicateDigits x]
 
-- Given a positive integer n, return the number of values between 1 and n that
-- contain no duplicate digits, and the largest gap between two consecutive
-- values in that sequence.
answer :: Int -> (Int, Int)
answer n = (length sequence, gap)
           where sequence = values n
                 gap = maximum (zipWith subtract sequence (tail sequence))

Tutorials

• Yet Another Haskell Tutorial (PDF) - by Hal Daume III
• A Gentle Introduction to Haskell - by Paul Hudak, John Peterson and Joseph Fasel
• Learn Haskell in 10 Minutes
• Haskell Tutorial - Walla Walla College Computer Science Department
• A Taste of Haskell (PDF) - Slides from Simon Peyton-Jones’ OSCON tutorial sessions (video: part 1 and part 2).
• Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell (PDF) - by Simon Peyton-Jones

Specifications

• Haskell 98

Compilers and Interpreters

• The Glasgow Haskell Compiler (GHC)
• Hugs 98
• nhc98
• jhc

Monads

• You Could Have Invented Monads!

Software Transactional Memory

• Beautiful Concurrency (PDF) by Simon Peyton-Jones (from the book Beautiful Code).
• Transactional Memory for Concurrent Programming (16 minute video) - An OSCON presentation by Simon Peyton-Jones (PDF slides)

Having been exposed to pure functional programming in Miranda at university, Haskell is a programming language that I like a lot. I’ve dabbled with it on and off using GHC but I’ve never written a really substantial program in it. Certainly nothing to rival the Java behemoths that I develop day-to-day. Programs written (well) in Haskell are concise, expressive and have an elegance that is hard to match in more general-purpose languages such as C and Java.

Despite the appeals of strongly-typed, side-effect-free programming, Haskell (and non-strict, pure functional languages in general), have long been regarded as primarily the domain of academics. Haskell’s design owes much to the proprietary Miranda system but, unencumbered by commercial constraints, it has rapidly supplanted its predecessor. Even the University of Kent, previously the principal champion of Miranda, has long since switched to Haskell for teaching purposes. Haskell is now a part of undergraduate computer science courses around the world but, despite this, has little visibility in the world of commercial software development.

However, all that may be about to change. This week saw the announcement of the book “Real World Haskell”, to be published by O’Reilly. If the authors deliver on the proposed outline, it promises to provide a real boost for Haskell as a viable language for mainstream software development. The book will cover topics that are often ignored by existing Haskell guides but that are essential for solving real world problems. I/O, databases, GUI development, concurrency and unit testing are just some of the items to be addressed.

At present there is nothing much to see, but I’ll be monitoring their progress closely over the coming months in eager anticipation. Hopefully, by the time the book is out, GHC will have broken free from its LGPL shackles to remove another barrier to widespread Haskell adoption.