What are some good intermediate problems and projects for learning Haskell?

Question

I just recently started diving into Real World Haskell and the book provides some good practice exercises.

However, I'd like some suggestions for specific problems people have solved or projects they've completed that have really helped them to better understand the language and its capabilities. What sort of things can I throw myself at that are really going to challenge me?

I have a moderate understanding of the language and no previous experience with other functional languages; Haskell is my first jump into this arena.

Answer 1

I have found Project Euler helpful in learning the rudimentary language constructs to help me get feel for Haskell. Granted, this isn't creating a real application with Haskell, but for me it's a great way to get comfortable with the language's features. After that, I may try to re-write some my small python apps in Haskell (some of them GUI oriented). So, that might be your next step, take something you've written in another language, and try to do it in Haskell.

Answer 2

Here's a problem inspired by Why Functional Programming Matters by John Hughes: find the most efficient way to archive digitized record albums onto DVD:

The problem is as follows:

• I want to archive my music collection on DVD. An album takes up 300–600MB, but a DVD holds 4,700,000B. I want to pack as many albums as possible into a DVD.

  If two different packings use the same number of DVDs, I prefer the one that leaves the most amount of free space on the least full DVD, so that all the other DVDs are as full as possible.

• The problem is NP-hard, but basic step is to use the standard greedy hueristic:
  1. Sort the albums into a list, largest one first.
  2. Start with an infinite list of empty DVDs.

  3.   repeat
         take the first album from the list
         put the album in the first DVD that has room for it
       until there are no more albums on the list
     

     Burn all the nonempty DVDs.

Please solve these programming problems:

8. Implement the standard greedy algorithm by writing a function

     pack :: [(Album, Integer)] -> [DVD]
   

   where

     type Album = String
     type DVD = [Album]
   

   Decompose your solution into separate functions as described by Hughes.
9. The result of a packing is a pure function of the order in which albums appear on the list. You can improve a packing by using bubble search: take the sorted list producing a new list using this algorithm:

     repeat
       probabilistically choose an item from the old list
       remove that item from the old list and place it at the end of the
       new list
     until the old list is empty
   

   Then you do the greedy packing algorithm on the perturbed list. If the packing improves, the new ordering then becomes the basis for further perturbations.

   The probabilistic choice is parameterized by a probability p:

   • Choose the first item with probability p
   • Choose the second item with probability p×(1-p)
   • Choose the ith item with probability p×(1-p)^i-1
   • Choose the last item (in a list of length n) with probability (1-p)^n-1

   The problem is to implement packing by Bubble Search

   Your function can take as an argument need an infinite list of random numbers.

With p=0.45 and 10,000 iterations bubble search can consistently produce packings of DVDs that are over 99.5% full.

Hints:

• Reuse as many of Hughes's combinators as possible.
• You'll need to plumb through an infinite list of random numbers. Write new higher-order functions to help you do so.