Using Haskell to Write Music

Using Music to Learn Haskell


List Patterns: MonadState and Traverse
programmusic

List Patterns:  MonadState and Traverse

There's an even more concise and general way to solve for these patterns:


-- result and state are the same, just the running sum.
sumState :: (Num b, MonadState b m) => b -> m b
sumState y = get >>= \x -> let z = x + y in put z >> return z

-- traverse container answering new container with sum of values traversed so far.
stateSum :: (Num a, Traversable t) => t a -> t a
stateSum xs = evalState (traverse sumState xs) 0

$ stateSum [1..10]
[1,3,6,10,15,21,28,36,45,55]

-- state is pair, (sum, count), answer is (sum / count)
avgTotState :: (Fractional b, MonadState (b,b) m) => b -> m b
avgTotState y = get >>= \(s,n) -> let s' = s + y in put (s',n+1) >> return (s'/(n+1))

cumAvgState :: Fractional a => [a] -> [a]
cumAvgState [] = []
cumAvgState (x:xs) = evalState (traverse avgTotState xs) (x,1)

$ cumAvgState [1..10]
[1.5,2.0,2.5,3.0,3.5,4.0,4.5,5.0,5.5]

-- state is window of 'n' items to average over, answer is average of items in window
avgRunState :: (Fractional b, MonadState [b] m) => Int -> b -> m b
avgRunState c y = get >>= \rs -> let rs' = take c (y:rs) in put rs' >> return (sum rs' / fromIntegral c)

runAvgState :: Fractional a => Int -> [a] -> [a]
runAvgState 0 _  = []
runAvgState _ [] = []
runAvgState c xss@(_:_)
 | length xss < c = []
 | otherwise      = evalState (traverse (avgRunState c) (drop c xss)) (take c xss)

$ runAvgState 4 [1..20]
[2.75,3.5,4.75,6.5,7.5,8.5,9.5,10.5,11.5,12.5,13.5,14.5,15.5,16.5,17.5,18.5]

Rather than managing state and anser explicitly, as we did above with foldl, you can delegate that to the MonadStatetypeclass. You have to remap ordinary Haskell from the foldl function to the get and put operations in the State class and the way you combine them with Monad type class functions >>=, >>, and return. That sounds like more work than it actually turns out to be, especially if you keep simple templates like these in your back pocket.

Note finally we generalize over the Num and Fractional typeclasses. This greately widens the surface of these functions as represented by all the types with Num, Fractional, and Traversable instances, vs. just working over lists. Reading about the burning bridges upgrade to the GHC compiler got me interested in how I might follow this example to better generalize my code.

Coming up with those type signatures wasn't just a question of reading the documentation and typing in the correct answer. I find ghci a valuable assistant, and when I don't get my type signatures right the first time, I often figure out where I went wrong by temporarily commenting them out, loading the code into ghci and asking it to tell me type for the function. That an be a powerful way to explore new features, for example (head Control.Arrow.&&& length) in the example below, which I came across working on a parser for a binary file:


-- For a a sortable list, answer list of items by frequency of occurence, sorted in descending order by count
frequencyCount :: Ord a => [a] -> [(a,Int)]
frequencyCount xs = sortBy (compare `on` snd) $ map (head Control.Arrow.&&& length) $ (group . sort) xs

List Patterns: Fold and Unfold
programmusic

List Patterns Fold and Unfold

What about foldl? At first glance, it might seem like a poor fit. Doesn't fold just collapse a container (as in a catamorphism)? Actually, while that's one common pattern, foldr is much more powerful than that. There's no reason the shape of the output has to be "smaller" than the shape of the input. You can use it to get to the same place as scanl:


-- Sum contents of list answering incremental sums and final sum.
foldSuml :: [Int] -> [Int]
foldSuml [] = []
foldSuml (x:xs) = reverse $ foldl (\(s:ss) x' -> let s' = s + x' in (s':s:ss)) [x] xs

$ foldSuml [1..10]
[1,3,6,10,15,21,28,36,45,55]

Here, there's a foldl that both consumes and produces a list. It's faster to build a list back-to-front. And Haskell's pattern matching decomposes a list to its head and tail. So here we build the list of sums backward, use pattern matching to fetch out the current sum from the head of the list, and then reverse the list at the end to duplicate the scanSuml behavior.

Note the right fold mirrors the right scan:


foldSumr :: [Int] -> [Int]
foldSumr [] = []
foldSumr (x:xs) = foldr (\x' (s:ss) -> let s' = s + x' in (s':s:ss)) [x] xs

$ foldSumr [1..4]
[10,8,5,1]

Before we get futher, note you can unfoldr across a list to yield sums as well.


unfoldSum :: [Int] -> [Int]
unfoldSum xs = unfoldr (\(t,xs') -> if null xs' then Nothing else let t' = head xs' + t in Just (t', (t', tail xs'))) (0,xs)

Here, the unfoldr generator function that is the first argument takes a pair with the current sum and the remaining list of items to sum over. While there are more items to sum over, we answer Just the new pair, and unfoldr assembles the list of sums from the first element in the pair as the result:

Or even more simply, if we limit ourselves to consecutive integers:


unfoldSumrInts :: [Int]
unfoldSumrInts = unfoldr (\b -> Just ((b * (b + 1)) `div` 2, b + 1)) 1

$ take 10 $ unfoldSumrInts 
[1,3,6,10,15,21,28,36,45,55]

As an example of a way that fold is more powerful (or at least more efficient) than scan, consider a function that requires some additional state beyond the value a the head of the list. For example, a running average of each element as it's added to the list, i.e. for list [a,b,c,d] you'd get [a, (a+b)/2 , (a+b+c)/3, (a+b+c+d)/4]. With each new element, add it to the sum, compute average by dividing the new sum by length of list + 1, and append new average to list.


-- for:
--  * pair of a) accumulated total across list, b) list of accumulated totals
--  * new element,
-- compute:
--  * add new element to update accumulated total across pair,
--  * compute new average by dividing updated accumulated total by count of elements
-- answer:
--  * pair with updated a) accumulated total, b) list of accumulated totals

avgTot :: Fractional a => (a,[a]) -> a -> (a,[a])
avgTot (s, ss) y =
  let s'  = s + y
      cnt = fromIntegral (length ss) + 1
      avg = s' / cnt
  in
   (s', avg:ss) -- backwards for ease of list construction

-- cumulative average
cumAvg :: Fractional a => [a] -> [a]
cumAvg [] = []
cumAvg (x:xs) = reverse . snd $ foldl avgTot (x,[x]) xs

$ cumAvg [1..10]
[1.0,1.5,2.0,2.5,3.0,3.5,4.0,4.5,5.0,5.5]

Well, that's a boring sort result for the list of consecutive integers, although it does reveal yet another way to represent the formula for the sum of n consecutive integers:


$ map round $ zipWith (*) [1..10] [1,1.5..]

Another example would be a running average over 'n' values, keeping a list you average over in your state.


-- for:
--  * pair of a) running window of list 'n' elements long, e.g. [l,m,n],
--    b) list of running sum 'n' elements long average, e.g. [l+m+n/3,m+n+0/3..]
--  * new element,
-- compute:
--  * new running window e.g. [l,m,n] => [m,n,o]
--  * new average, e.g. m+n+o/3
-- answer:
--  * pair with a) new window, b) new average added to existing list
avgRun :: Fractional a => Int -> ([a],[a]) -> a -> ([a],[a])
avgRun c (rs, ss) y =
  let rs' = take c (y:rs)
      s   = sum rs' / fromIntegral c
  in
   (rs', s:ss)  -- backwards for ease of list construction

-- Running average.
runAvg :: Fractional a => Int -> [a] -> [a]
runAvg 0 _  = []
runAvg _ [] = []
runAvg c xxs@(_:_)
  | length xxs < c = []
  | otherwise      = let start = take c xxs in reverse . snd $ foldl (avgRun c) (start, [sum start / fromIntegral c]) $ drop c xxs

$ runAvg 4 [1..20]
[2.5,2.75,3.5,4.75,6.5,7.5,8.5,9.5,10.5,11.5,12.5,13.5,14.5,15.5,16.5,17.5,18.5]

That's getting better! For one thing, these are hard to trivially reduce to a scan:


cumAvgTriv :: Fractional a => [a] -> [a]
cumAvgTriv [] = []
cumAvgTriv (x:xs) = reverse . snd . last $ scanl avgTot (x,[x]) xs

runAvgTriv :: Fractional a => Int -> [a] -> [a]
runAvgTriv 0 _  = []
runAvgTriv _ [] = []
runAvgTriv c xxs@(_:_)
  | length xxs < c = []
  | otherwise = reverse . snd . last $ let start = take c xxs in scanl (avgRun c) (start, [sum start / fromIntegral c]) $ drop c xxs

The unadorned type of scanl with function used above in foldl would be:


cumAvgTriv :: Fractional a => [a] -> [(a, [a])]

But what we're really interested in is just the [a] from the last of [(a, [a])], which we have to pluck off with


reverse . snd . last

Not only does the pattern not stay trivial, but we've held onto a lot of intermediate values just to throw almost all of them away at the end. For that reason, the foldl implementation is more efficient.


List Patterns: Scan
programmusic

List Patterns:  Scan

One simple transform is to convert a list of Int to the list of Int that is the running sum:


Input:  [1,2,3,4,5]
Outut:  [1,3,6,10,15]

or


Input:   [1,3,5,7,9,11]
Output;  [1,4,9,16,25,36]

For each new element of the list x you need the current sum s, which you add to the new element for the new sum s', which you add to the output list and carry forward for the next iteration.

That's trivial with scanl, which leaves a bread-trail of recursive results:


scanSuml :: [Int] -> [Int]
scanSuml []  = []
scanSuml (x:xs) = scanl (+) x xs

$ scanSuml [1..10]
[1,3,6,10,15,21,28,36,45,55]

Note that scanr gets you to the same place but via a different route:


scanSumr :: [Int] -> [Int]
scanSumr []  = []
scanSumr (x:xs) = scanr (+) x xs

$ scanSumr [1..10]
[55,53,50,46,41,35,28,20,11,1]

If you're curious as to why, then go have a look at the implementation. I love doing this in Haskell. Pull up the Preludedocumentation, scroll down to the function you're interested in, and click on the "Source" link. Here's what scanr looks like (plus, there are usually some interesting bits in the comments):


scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 []           =  [q0]
scanr f q0 (x:xs)       =  f x q : qs
                           where qs@(q:_) = scanr f q0 xs

Algorithms that recur to the right always take me a bit longer ot figure out. Usually I have to work though a couple iterations for it to make sense. Here, to find that first q you have to get to qs, for which you don't get the tail until the end of the input list. Let's try it out for a four item list:


scanr (+) 1 [2,3,4]
(+) 2 q : (+) 3 q' : (+) 4 q'' : [1]
(+) 2 q : (+) 3 q' : (+) 4 1 : [1]
(+) 2 q : (+) 3 q' : 5 : [1]
(+) 2 q : (+) 3 q' : [5,1]
(+) 2 q : (+) 3 5 : [5,1]
(+) 2 q : 8 : [5,1]
(+) 2 q : [8,5,1]
(+) 2 8 : [8,5,1]
10 : [8,5,1]
[10,8,5,1]

scanl and scanr are excellent ways to memo-ize recursive results. I've found complicated solutions using foldl that can be rewritten in simpler form using scanl, e.g. when the input to the recursive function shrinks to a single value.


List Patterns: scan, fold, unfold, traverse
programmusic

List Patterns: scan, fold, unfold, traverse

With Haskell I wind up manipulating lists a lot. With lists, I often need some sort of context to convert elements in list "a" to produce list "b". Haskell gives you several ways to do this. In this post, I describe a couple functions and ways to drag them over lists: fold, scan, unfoldr, traverse. You'll find fold and scan in the Prelude (in their left and right variants, e.g.foldl, scanr, etc.). unfoldr comes from Data.List, "right-handed" only. traverse does similar things, only leveragingMonadState and Traversable type classes to work with any container that's an instance of Traversable. You'll find them inControl.Monad.State and Data.Traversable.


Crafting Haskell: Cabal Details
programmusic

Folders and Files

Cabal doesn't require a particular folder layout. I use one I copied from an example on the web. Now, when I start a new project, I begin by cloning and modifying my template. I'm not going ot talk about the git bits here, just the cabal stuff. Note that the project I describe here is for a Haskell library. I'll work on a parallel project for an executable next.

The folder hierarchy that works for me is to have two top-level folders, one for source src, one for tests tests. Under the srcfolder, I put an interface file. In the example project, I use the Haskell source from my recursion post for the nOutOfMs function, which I call Combinations.hs:


-- Example API

module Combinations (
  nOutOfMs
  ) where

import Combinations.Utils

Not much there, just enough to give you the idea. The top-level Haskell file just contains the list of exports. The implementation file is under a subdirectory, in this case, Combinations.Utils.hs:


module Combinations.Utils where

import Data.Word (Word32)

-- http://stackoverflow.com/questions/7371730/how-to-tell-if-a-list-is-infinite
isNonEmpty :: [t]  -> Bool
isNonEmpty [] = False
isNonEmpty (_:_) = True

longerThan :: Int -> [a] -> Bool
longerThan n xs = isNonEmpty $ drop n xs

maxLenList :: Int
maxLenList = 1000

-- | Pick n combinations from a list of items
--   where 'n' must be a positive value and
--   'ms' must contain fewer than maxLenList items.
nOutOfMs :: Word32 -> [t] -> [[t]]
nOutOfMs 1 ms     = map (:[]) ms
nOutOfMs 0 _      = [[]]
nOutOfMs _ []     = []
nOutOfMs n mms@(m:ms)
  | longerThan maxLenList mms    = error $ "nOutOfMs list is longer than max length " ++ show maxLenList
  | length mms > fromIntegral n  = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms
  | otherwise                    = map (m:) (nOutOfMs (n-1) ms)

Note that the Combinations.Utils module name follows the folder hierarchy. Also that everything is exported. That way, your test module can import the implementation file directly and you can put helper functions under unit test.

Under tests there's a top-level file, MainTestSuite.hs and another Combinations folder with one file, UtilsTest.hs. TheMainTestSuite.hs provides examples of two types of unit tests, one that tests individual cases, one that tests properties:


module Main (
    main
  ) where

import Combinations.UtilsTest
import Test.Tasty
import Test.Tasty.HUnit
import Test.Tasty.QuickCheck

main :: IO ()
main = defaultMain tests

tests :: TestTree
tests =
  testGroup "Example"
  [
      testCase       "max N of M combinations"           testCountCombinationsMaxN
    , testCase       "zero combinations in empty list"   testCountCombinationsEmptyList
    , testProperty   "count combinations"                propCountCombinations
  ]

Everything down to the testGroup line is boilerplate. It lines things up so cabal can run your tests. In this case, the first two lines test an individual test case and the last tests a property. The Combinations.UtilsTest.hs file implements the three tests:


module Combinations.UtilsTest where

import Combinations.Utils
import Data.Word (Word32)
import Test.HUnit
import Test.QuickCheck

-- | Simple factorial
fact :: Word32 -> Integer
fact n = product [1..(toInteger n)]

-- | Calculate number of combinations of n items out of a collection of m items.
numCombinations :: Word32 -> Word32 -> Integer
numCombinations n m = fact m `div` (fact n * fact (m - n))

-- | Count number of combinations for 'n' out of m items by generating list of 'm' items
--   (pick '[]' for item to minimize size), then generating combinations of 'n' of list
--   'm' items long (all of which will be identical but we do not care because we only
--   want to count them) and answer how many are returned.  
countCombinations :: Word32 -> Word32 -> Integer
countCombinations n m =  (toInteger . length) (nOutOfMs n (replicate (fromIntegral m) []))  

-- | Example test cases.  Useful for boundary conditions.

testCountCombinationsEmptyList :: Assertion
testCountCombinationsEmptyList =
  0 @=? countCombinations 5 0

largeN :: Word32
largeN = 100

testCountCombinationsMaxN :: Assertion
testCountCombinationsMaxN =
  numCombinations largeN largeN @=? countCombinations largeN largeN

-- | Example property.  Constrain 'n' and 'm' to small numbers so
--   the default nubmer of 100 test cases finishes in a reasonable
--   amount of time (< 60 seconds).

maxCountMs :: Word32
maxCountMs = 30

data NMPair = NMPair { nCount :: Word32, mCount :: Word32 } deriving (Show)
instance Arbitrary NMPair where
  arbitrary = elements [1..maxCountMs] >>= \m -> return $ NMPair (m `div` 3) m

propCountCombinations :: Property
propCountCombinations =
  forAll arbitrary $ \(NMPair n m) -> numCombinations n m == countCombinations n m

That's enough to give a taste for two test patterns. There's plenty of online details for HUnit and QuickCheck.

Cabal Bits

The cabal bits are in CabalExample.cabal at the top-level folder. To start things off, I created the folders and files above, then ran cabal init, which asks you several questions. Then I simplified things somewhat, discussed below.


-- Initial CabalExample.cabal generated by cabal init.  For further 
-- documentation, see http://haskell.org/cabal/users-guide/

 name:                CabalExample
 version:             0.1.0.0
 synopsis:            Template to create a new Cabal package
-- description:         
 homepage:            https://github.com/tomtitchener/CabalExample/blob/master/README.md
 license:             PublicDomain
 license-file:        LICENSE
 author:              Tom Titchener
 maintainer:          tomtitchener@verizon.net
-- copyright:           
 category:            Development
 build-type:          Simple
 extra-source-files:  README.md
 cabal-version:       >=1.10

 source-repository head
   type:     git
   location: git://github.com/tomtitchener/CabalExample.git

 library
  hs-source-dirs:      src
  exposed-modules:     Combinations
  other-modules:       Combinations.Utils
  build-depends:       base
  default-language:    Haskell2010
  ghc-options:        -Wall -Werror -fwarn-incomplete-patterns -fwarn-incomplete-uni-patterns

 test-suite tests
  type:                exitcode-stdio-1.0
  hs-source-dirs:      tests, src
  main-is:             MainTestSuite.hs
  build-depends:       base, tasty, tasty-hunit, tasty-quickcheck, HUnit, QuickCheck
  default-language:    Haskell2010
  ghc-options:        -Wall -Werror -fwarn-incomplete-patterns -fwarn-incomplete-uni-patterns 

Note, I added everything from test-suite tests and below. Maybe there's a way to do this with cabal init. For now, I just do this by hand.

First, I simplified the build-depends line, which originally looked like this:


build-depends:       base >=4.8 && <4.9, tasty >=0.10 && <0.11, tasty-hunit >=0.9 && <0.10, tasty-quickcheck >=0.8 && <0.9, HUnit >=1.2 && <1.3, QuickCheck >=2.8 && <2.9

These are all pretty standard libraries. To keep things simple, I'm going to assume forward compatility. One word of warning: install a new package and add a new import for it to a Haskell file, and you'll need to update build-depends in your cabal file.

Next, I added the ghc-options line:


  ghc-options:        -Wall -Werror -fwarn-incomplete-patterns -fwarn-incomplete-uni-patterns 

This is all plain vanilla Haskell. I should be able to get sparkly clean builds.

Finally, I added the test-suite tests clause.

Cabal Usage

Now you've got all the parts lined, up, here are some things you can do. First, you can build:


bash-3.2$ cabal build
Package has never been configured. Configuring with default flags. If this
fails, please run configure manually.
Resolving dependencies...
Configuring CabalExample-0.1.0.0...
Building CabalExample-0.1.0.0...
Preprocessing library CabalExample-0.1.0.0...
[1 of 2] Compiling Combinations.Utils ( src/Combinations/Utils.hs, dist/build/Combinations/Utils.o )
[2 of 2] Compiling Combinations     ( src/Combinations.hs, dist/build/Combinations.o )
[1 of 2] Compiling Combinations.Utils ( src/Combinations/Utils.hs, dist/build/Combinations/Utils.p_o )
[2 of 2] Compiling Combinations     ( src/Combinations.hs, dist/build/Combinations.p_o )
In-place registering CabalExample-0.1.0.0...

Nice! You can also test:


bash-3.2$ cabal test
Re-configuring with test suites enabled. If this fails, please run configure
manually.
Resolving dependencies...
Configuring CabalExample-0.1.0.0...
Preprocessing test suite 'tests' for CabalExample-0.1.0.0...
[1 of 3] Compiling Combinations.Utils ( src/Combinations/Utils.hs, dist/build/tests/tests-tmp/Combinations/Utils.o )
[2 of 3] Compiling Combinations.UtilsTest ( tests/Combinations/UtilsTest.hs, dist/build/tests/tests-tmp/Combinations/UtilsTest.o )
[3 of 3] Compiling Main             ( tests/MainTestSuite.hs, dist/build/tests/tests-tmp/Main.o )
Linking dist/build/tests/tests ...
Running 1 test suites...
Test suite tests: RUNNING...
Test suite tests: PASS
Test suite logged to: dist/test/CabalExample-0.1.0.0-tests.log
1 of 1 test suites (1 of 1 test cases) passed.

Nicer yet! And you can interact:


bash-3.2$ cabal repl
Preprocessing library CabalExample-0.1.0.0...
GHCi, version 7.10.1: http://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Combinations.Utils ( src/Combinations/Utils.hs, interpreted )
[2 of 2] Compiling Combinations     ( src/Combinations.hs, interpreted )
Ok, modules loaded: Combinations, Combinations.Utils.
*Combinations> :t nOutOfMs
nOutOfMs :: GHC.Word.Word32 -> [t] -> [[t]]
*Combinations> nOutOfMs (2::GHC.Word.Word32) [(1::GHC.Word.Word32),2,3]
[[1,2],[1,3],[2,3]]

Ugh. One problem with those -Wall -Werror and etc. flags is that ghci wants integer types all properly lined up. If I'm doing a lot of typing into ghci, I temporarily comment-out those lines from the cabal file.

And you can build documentation:


bash-3.2$ cabal haddock
Running Haddock for CabalExample-0.1.0.0...
Preprocessing library CabalExample-0.1.0.0...
Haddock coverage:
  20% (  1 /  5) in 'Combinations.Utils'
  Missing documentation for:
    Module header
    isNonEmpty (src/Combinations/Utils.hs:6)
    longerThan (src/Combinations/Utils.hs:10)
    maxLenList (src/Combinations/Utils.hs:13)
  50% (  1 /  2) in 'Combinations'
  Missing documentation for:
    Module header
Documentation created: dist/doc/html/CabalExample/index.html
Preprocessing test suite 'tests' for CabalExample-0.1.0.0...

Hmm. Not such good documentation coverage! A useful reminder!

You can even use cabal to run the Haskell code coverage tool:


bash-3.2$ cabal clean
cleaning...
bash-3.2$ cabal configure --enable-tests --enable-coverage 
Resolving dependencies...
Configuring CabalExample-0.1.0.0...
bash-3.2$ find . -name *.html
bash-3.2$ cabal test
Preprocessing test suite 'tests' for CabalExample-0.1.0.0...
[1 of 3] Compiling Combinations.Utils ( src/Combinations/Utils.hs, dist/build/tests/tests-tmp/Combinations/Utils.o )
[2 of 3] Compiling Combinations.UtilsTest ( tests/Combinations/UtilsTest.hs, dist/build/tests/tests-tmp/Combinations/UtilsTest.o )
[3 of 3] Compiling Main             ( tests/MainTestSuite.hs, dist/build/tests/tests-tmp/Main.o )
Linking dist/build/tests/tests ...
Running 1 test suites...
Test suite tests: RUNNING...
Test suite tests: PASS
Test suite logged to: dist/test/CabalExample-0.1.0.0-tests.log
Writing: Combinations.Utils.hs.html
Writing: Combinations.UtilsTest.hs.html
Writing: hpc_index.html
Writing: hpc_index_fun.html
Writing: hpc_index_alt.html
Writing: hpc_index_exp.html
Test coverage report written to dist/hpc/vanilla/html/tests/hpc_index.html
1 of 1 test suites (1 of 1 test cases) passed.
Writing: Combinations.Utils.hs.html
Writing: Combinations.UtilsTest.hs.html
Writing: hpc_index.html
Writing: hpc_index_fun.html
Writing: hpc_index_alt.html
Writing: hpc_index_exp.html
Package coverage report written to
dist/hpc/vanilla/html/CabalExample-0.1.0.0/hpc_index.html

There's a lot more to cabal. Now you've got a start, it's worthwhile poking around some to see what more you can do.

HLint

Along with -Wall -Werror, I use hlint to tell about style issues, like eta reduction superflous parentheses, repeated code, and many other gotchas.

Type hlint . at the top of your folder hierarchy to get suggestions about all the *.hs files in your project.


Crafting Haskell: Cabal
programmusic

Crafting a small haskell project with Cabal

As your Haskell project grows, do you find yourself scrambling to build, test, and do other housekeeping tasks?

One solution is to make a cabal project. Is that really a good choice? If you've poked about reading blogs a bit, you're sure to come across the term "cabal hell". That sure doesn't sound like a pleasant place to wind up.

What I can say is cabal gives a great framework to manage small projects. Best of all, you can easily automate unit test with cabal, which gieves you the support you need for refactoring your main line code. And cabal gives you a custom REPL to explore your code interactively, which can result in a very productive pattern where you verify behavior interactively then record those tests in your unit test framework.

Plus, "cabal hell" is a well-known problem that some very smart people are working to resolve. So, I say it's very worthwhile.

In this post I discuss an example repo CabalExample. Download it from from GitHub and follow along. I use the nOutOfMs code from the previous post. First, I present the folder hierarchy and discuss the example source files. Then I describe the cabal bits and how you can use cabal from a command line prompt. Note, I'm not a cabal expert! There are probably 1,000 ways to improve on these instructions. The good news is, even without becoming an expert, you can use this tool to automate the kinds of things you used to automate with make.


Crafting Haskell: Recursion Part Two
programmusic

Crafting recursion - Part Two

But what do we do with the rest of the list (ms)? Seeing as we've got a portion of the problem space, why not recur?


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs n (m:ms) = map (m:) $ nOutOfMs (n - 1) ms

But when I load this into ghci and try to run it, I get an error:


*Worksheet> :l worksheet.hs
[1 of 1] Compiling Worksheet        ( worksheet.hs, interpreted )
Ok, modules loaded: Worksheet.
*Worksheet> nOutOfMs 2 [1,2,3]
*** Exception: worksheet.hs:5:1-48: Non-exhaustive patterns in function nOutOfMs

Whops, ghci says I've left some bits out! I forgot to tell it when to stop! That would seem to be easy enough:


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs 0 _      = []
nOutOfMs _ []     = []
nOutOfMs n (m:ms) = map (m:) (nOutOfMs (n-1) ms)

Let's give it a whirl!


*Worksheet> :l worksheet.hs
[1 of 1] Compiling Worksheet        ( worksheet.hs, interpreted )
Ok, modules loaded: Worksheet.
*Worksheet> nOutOfMs 2 [1,2,3]
[]

Well, it's progress. At least ghci found an expression it could evaluate! But the answer isn't what we want. Let's see if we can deduce what happened by following step-by-step as the implentation recurs:


*Worksheet> nOutOfMs 2 [1,2,3]
... typing these bits in by  hand ... 
-- expand by function definition 
nOutOfMs 2 (1:[2,3])
-- recur and expand by function definition
map (1:) $ nOutOfMs 1 (2:[3])
-- recur again and expand by function defintion
map (1:) $ map (2:) $ nOutOfMs 0 (3:[])
-- reduce by base case definition, n is 0 
map (1:) $ map (2:) []
-- reduce by applying map when list is empty 
map (1:) $ []
-- reduce by applying map when list is empty 
[]

Answering the empty list when the first argument is zero doesn't look like such a good idea. Can we answer something better than the empty list when n is 0? We have to have something to map over! What about a single item list that just contains the empty list: [[]]?


module Worksheet where 
-- | Pick n combinations from a list of items. 
nOutOfMs :: Int -> [t] -> [[t]] 
nOutOfMs 0 _ = [[]] <-- new and impoved!
nOutOfMs _ [] = [] 
nOutOfMs n (m:ms) = map (m:) (nOutOfMs (n-1) ms)

*Worksheet> :l worksheet.hs
[1 of 1] Compiling Worksheet        ( worksheet.hs, interpreted )
Ok, modules loaded: Worksheet.
*Worksheet> nOutOfMs 2 [1,2,3]
[[1,2]]

Better! But we're still ending too early. We were shooting for [[1,2], [1,3]] but all we got was [1,2]]. What would a "proper" reduction look like to give us the answer we want?


*Worksheet> nOutOfMs 2 [1,2,3]
... typing these bits in by  hand ... 
-- expand by function definition 
nOutOfMs 2 (1:[2,3])
map (1:) $ nOutOfMs 1 (2:[3])
... something happens here and I wind up with ...
map (1:) [[2],[3]]
-- reduce by applying map 
[[1,2],[1,3]]

What we need is a way to get from nOutOfMs 1 [2,3] to [[2],[3]]. Well, to pick one out of a list is just to answer the list with each element as a list itself! To an element into a list, you can apply the function (:[]).


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs 1 ms     = map (:[]) ms  <-- new and improved!
nOutOfMs 0 _      = [[]]
nOutOfMs _ []     = []
nOutOfMs n (m:ms) = map (m:) (nOutOfMs (n-1) ms)

Give it a shot:


*Worksheet> :l worksheet.hs
[1 of 1] Compiling Worksheet        ( worksheet.hs, interpreted )
Ok, modules loaded: Worksheet.
*Worksheet> nOutOfMs 2 [1,2,3]
[[1,2],[1,3]]

Progress! What's next? Look back to our original grouping:


[[[1,2,],[1,3]],[[2,3]]]

We've done the first part. Now we just need to do the second part. But now we start from the second element of the list. Looks like a chance to recur to me! First, let's try it out:


*Worksheet> nOutOfMs 2 [2,3]
[[2,3]]

Aha. Just what we need! That last bit is just a recursive call on the tail of the list:


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs 1 ms     = map (:[]) ms
nOutOfMs 0 _      = [[]]
nOutOfMs _ []     = []
nOutOfMs n (m:ms) = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms

Give it a shot:


*Worksheet> nOutOfMs 2 [1,2,3]
[[1,2],[1,3],[2,3]]

Woo Hoo! Time to go crazy!


*Worksheet> nOutOfMs 4 [1..5]
[[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]]
*Worksheet> nOutOfMs 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
*Worksheet> nOutOfMs 2 [1..4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
*Worksheet> nOutOfMs 9 [1..10]
[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,10],[1,2,3,4,5,6,7,9,10],[1,2,3,4,5,6,8,9,10],[1,2,3,4,5,7,8,9,10],[1,2,3,4,6,7,8,9,10],[1,2,3,5,6,7,8,9,10],[1,2,4,5,6,7,8,9,10],[1,3,4,5,6,7,8,9,10],[2,3,4,5,6,7,8,9,10]]

Are we done? How do we know it's right? Can we at least make a good guess that it's right? Sure! A quick look at Combinations on Wikipedia shows the formula for the number of combinations of n items out of a set of m items is:


m! / n! ( m - n)!

Turns out, product [1..x] is a trivial way to compute factorial for number x in Haskell. So, take something that makes a lot of combinations see how many our function answers:


*Worksheet> length $ nOutOfMs 5 [1..20]
15504

Then see if that matches the formula:


*Worksheet> (product [1..20]) `div` ((product [1..5]) * (product [1..15]))
15504

Nice! But we can do even better. First, let's put these functions into worksheet.hs. I use Integer for fact andnumCombinations because those numbers get very big very fast:


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs 1 ms    = map (:[]) ms
nOutOfMs 0 _      = [[]]
nOutOfMs _ []     = []
nOutOfMs n (m:ms) = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms

-- | Simple factorial
fact :: Int -> Integer
fact n = product [1..(toInteger n)]

-- | Number of combinations of n items out of a collection of m items
numCombinations :: Int -> Int -> Integer
numCombinations n m = fact m `div` (fact n * fact (m - n))

-- | Verify the nOutOfMs function answers the correct number of combinations
testCountCombinations :: Int -> Int -> Bool
testCountCombinations n m = numCombinations n m == (toInteger . length) (nOutOfMs n (replicate m []))

The toInteger function converts Int answered by length to Integer answered by numCombinations. Keeping your number types straight in Haskell can be a bit of a pain, and for some reason I have a have a hard time keeping fromIntegral,toInteger, and fromInteger straight, so I always reach for the Converting Numbers page when this comes up.

I also like to compose functions with the . operator (toInteger . length) to reduce nesting of parentheses. I find it slightly easier to read this ...


(toInteger . length) (nOutOfMs 5 [1..20])

... rather than this:


toInteger (length (nOutOfMs 5 [1..20]))

Rinse, lather, repeat!


*Worksheet> testCountCombinations 5 20
True

Now, here's an interesting experiment I stumbled across:


*Worksheet> testCountCombinations 100 100
... nothing happening here, but ghc process sure is sucking down a of CPU ...

What's holding this up? Is it the computation to count the number of combinations (not very likely) or the one that generates the combinations (likely).


*Worksheet> numCombinations 100 100
1

The combination counter worked fine. Must be nOutOfMs:


*Worksheet> nOutOfMs 100 [1..100]
[[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]  ^C ^CInterrupted.

Sure enough. There may only be one combination. But we sure waste a lot time to figure that out! Is there something we can prune from the algorithm to speed things up? Here's a solution:


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs 1 ms     = map (:[]) ms
nOutOfMs 0 _      = [[]]
nOutOfMs _ []     = []
nOutOfMs n mms@(m:ms)
  | length mms > n  = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms
  | otherwise       = map (m:) (nOutOfMs (n-1) ms)

There's no point to recur on ms when there are fewer elements in ms than there are combinations!

There are other ways to send this function into oblivion:


*Worksheet> nOutOfMs (-1) [1..10]

*Worksheet> nOutOfMs 5 [1..]

It's tempting to say if somebody's stupid enough to supply a negative value for n then we should respond with a behavior that's equally stupid:


nOutOfMs n mms@(m:ms)
  | n < 0           = error $ "nOutOfMs negative count of combinations " ++ show n 
  | length mms > n  = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms
  | otherwise       = map (m:) (nOutOfMs (n-1) ms)

Or we can pretend there's a sensible answer:


nOutOfMs n mms@(m:ms)
  | n < 0           = [[]]
  | length mms > n  = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms
  | otherwise       = map (m:) (nOutOfMs (n-1) ms)

Neither feels right. And who knows, maybe you get lucky and somebody uses your function in larger computation where n is the result of another computation and it just happens that computation can result in a negative value?

Or, you can "Use the type system, Luke!":


module Worksheet where

import Data.Word

-- | Pick n combinations from a list of items.
nOutOfMs :: Word32 -> [t] -> [[t]]
nOutOfMs 1 ms     = map (:[]) ms
nOutOfMs 0 _      = [[]]
nOutOfMs _ []     = []
nOutOfMs n mms@(m:ms)
  | length mms > fromIntegral n  = map (m:) (nOutOfMs (n-1) ms) ++ nOutOfMs n ms
  | otherwise                    = map (m:) (nOutOfMs (n-1) ms)

-- | Simple factorial
fact :: Word32 -> Integer
fact n = product [1..(toInteger n)]

-- | Number of combinations of n items out of a collection of m items
numCombinations :: Word32 -> Word32 -> Integer
numCombinations n m = fact m `div` (fact n * fact (m - n))

-- | Verify the nOutOfMs function answers the correct number of combinations
testCountCombinations :: Word32 -> Word32 -> Bool
testCountCombinations n m =  numCombinations n m == (toInteger . length) (nOutOfMs n (replicate (fromIntegral m) []))

Here, we've replaced a type that includes negative numbers, Int, with one that doesn't, Data.Word.Word32. There's no need to test for negative values because the compiler guarantees nobody calls your function with a type that includes a negative number.

It's a bit of a pain. There are fromIntegral and toInteger calls scattered about where the compiler complained at me. And it makes nOutOfMs a bit more of a pain to call, too. But it's more sound, from a typing standpoint, and that fact, in principal, should yield fewer ... surprises.

By the way, don't be mislead if you try this out by loading it into a ghci session and typing something like nOutOfMs (-1) [1..10]. That's because ghci figures out for you how to coerce (-1) into Word32 value:


*Workhseet> toInteger (fromIntegral ((-1)::Word32))
4294967295

*Worksheet> nOutOfMs (-1) [1..20]
[]

You have to override this to get the type mismatch error you'd expect:


*Worksheet> nOutOfMs ((-1)::Int) [1..20]

<interactive>:56:11:
    Couldn't match expected type 'Word32' with actual type 'Int'
    In the first argument of 'nOutOfMs', namely '((- 1) :: Int)'
    In the expression: nOutOfMs ((- 1) :: Int) [1 .. 20]
    In an equation for 'it': it = nOutOfMs ((- 1) :: Int) [1 .. 20]



Solving that second problem, nOutoFMs 5 [1..] by restricting the type of the second argument to finite lists amounts to solving the halting problem, or so it says in stackoverflow. You could write a function that answers if a list is greater than a certain length that you can evaluate for an infinite list. In this case, it might be reasonable to return undefined by calling error with a message that the length of the list exceeds some maximum size.

Finally, here's the solution I originally found. Clean, elegant, a little recondite. Undefined for negative inputs. Inefficient for some cases. But I think I understand it a lot better for having reasoned my way to it myself.


-- copied:  http://stackoverflow.com/questions/14267196/fast-obtention-of-all-the-subsets-of-size-n-in-haskell
choose :: [b] -> Int -> [[b]]
_      `choose` 0 = [[]]
[]     `choose` _ =  []
(x:xs) `choose` k =  (x:) `map` (xs `choose` (k-1)) ++ xs `choose` k

Next: getting cozy with cabal. This project gives a nice template for creating a cabal package. With a cabal package, you can integrate a test harness and leverage the powers of quickcheck.


Crafting Haskell: Recursion Part One
programmusic

Crafting recursion - Part One


Recursion in FP is ubiquitous. But I find that deriving recursive algorithms can be hard. Of course, for many algorithms you can just use existing functions: map, filter, foldl, foldr, etc. Indeed, one of the common experiences learning Haskell is to spend an afternoon reasoning through an algorithm only to find it or something close to it is already implemented, either in the Prelude, in Data.List, or somewhere on StackOverflow. Where there's an established solution it's better to use that one instead of rolling your own. Your code will likely be more correct. And it'll be easier to read, maybe for you when you come back to it three months from now, maybe for others if you're lucky enough to find something worth publishing!

But recursion is so fundamental to FP, sometimes it's still worthwhile to take the time reasoning through an existing implementation. I get a better mental model and I think it adds to my vocabulary in a longer-lasting way. In this post, I'm going to demonstrate that approach for a function that answers combinations of n items from a list m items long. Spoiler alert: it's easy enough to find a solution on the web! And that's just what I did at first. But the solution is so concise and perfect I just had to go about deriving it for myself to understand, appreciate it, and even improve on it.

Where to start? A good first step to deriving the algorithm is to look for patterns in the answer. To do that, just write out a simple case by hand.  I like to start a new file that I name worksheet.hs, where I experiment by loading it into ghci. Here's what worksheet.hs looks like to start:


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs = undefined

And here's what a console session looks like to load the file into ghci:


bash-3.2$ ghci
GHCi, version 7.10.1: http://www.haskell.org/ghc/  :? for help
Prelude> :l worksheet.hs
[1 of 1] Compiling Worksheet        ( worksheet.hs, interpreted )
Ok, modules loaded: Worksheet.
*Worksheet> :t nOutOfMs
nOutOfMs :: Int -> [t] -> [[t]]
*Worksheet>

Say we want to add just two items out of a list of just three. Here's what an ghci session might look like:


*Worksheet> nOutOfMs 2 [1,2,3]
... imagine a solution to this is done ...
... in actuality, I just typed this out by hand ...
[[1,2],[1,3],[2,3]]

That's easy enough. And it's easy enough to imagine extending that strategy:


*Worksheet> nOutOfMs 3 [1,2,3,4]
... ditto ...
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

Next, go back to the simplest version and look for groupings. That's pretty easy, too. The first two belong together because they both start the same way, leaving the third as its own group:


[[[1,2],[1,3]],[[2,3]]]

What's a more abstract way of capturing that first pattern? It's the list of lists where each list starts with the first item:


[[[1,?],[1,?]],[]]

How would I write out just the first bit in ghci? I want to create a list with two elements where each element starts with the same value.  Shoving a new value to the head of a list is what (:) (operator formerly known as cons) does.


*Worksheet> :t (:)
(:) :: a -> [a] -> [a]

I have the number I want, 1, so thanks to the Haskell magic, I can change (:) from a function that takes two arguments to one that takes just one argument:


*Worksheet> :t (1:)
(1:) :: Num a => [a] -> [a]

What ghci tells me above is that I need something that fits this type Num a => [a]. That's easy enough:


*Worksheet> :t (1:) [2]
(1:) [2] :: Num a => [a]
*Worksheet> (1:) [2]
[1,2]


But I don't want just [1,2] for my answer, I want a list with two lists inside it, each of which starts with 1: [[1,2],[1,3]]. Well, what about map? Yeah. That should do the trick!


*Worksheet> map (1:) [2,3]

:11:2:
    Non type-variable argument in the constraint: Num [a]
    (Use FlexibleContexts to permit this)
    When checking that 'it' has the inferred type
      it :: forall a. (Num a, Num [a]) => [[a]]


Ugh! Not even quite. Something's gone wrong. Do I really need FlexibleContexts? What's FlexibleContexts anyway? It may be ghci is trying to be helpful, but it seems to assume I'm trying to do something a lot more complicated than what I meant to do!

How do I figure this out? Usually, when it's difficult to get a clue from the error message, I back up and see if I can't use ghci to tell me where I've gone wrong. One thing ghci is very helpful about is telling you about types. What does it think of that expression?


*Worksheet> :t map (1:) [1,2]
map (1:) [1,2] :: (Num a, Num [a]) => [[a]]

Hmm. Not much help there! It seems to type. But it sure doesn't wanna run. What if I simplify things:


*Worksheet> :t map (1:)
map (1:) :: Num a => [[a]] -> [[a]]

Aha! Now we're getting somewhere. The expression map (1:) wants Num a => [[a]] for it's second argument. But what did we give it above?


*Worksheet> :t [1,2]
[1,2] :: Num t => [t]

Whops! The type Num t => [t] is not the same as Num t => [[t]]!


*Worksheet> :t [[1],[2]]
[[1],[2]] :: Num t => [[t]]

That should work better!


*Worksheet> :t map (1:) [[1],[2]]
map (1:) [[1],[2]] :: Num a => [[a]]
*Worksheet> map (1:) [[1],[2]]
[[1,1],[1,2]]

Finally! (If you've been antsy for the past several stages, calm down. I know these are baby steps. But they're a great model for discovering how to use ghci to guide you through a maze of types.)  So, where were we? We want our implementation of nOutOfMs to start off with something that looks like map (m:), and we know we can match on the pattern (x:xs) to pull the first item from the head of a list.  Plucking the first item off the list is easy enough:


module Worksheet where

-- | Pick n combinations from a list of items.
nOutOfMs :: Int -> [t] -> [[t]]
nOutOfMs n (m:ms) = map (m:) undefined

But what do we do with the rest of the list (ms)? Seeing as we've got a portion of the problem space, why not recur?


Crafting Haskell: Intro
programmusic

Crafting Haskell

How do you learn a new programming language? How do you go about learning a new FP language?

If you're like me, you find good books, good blogs, and good tools and you read and you play around with some programming exercises.

And if you're like me, you experience many WTF moments. Sometimes the momentum builds and you get somewhere. Other times you beat your brain into a pulp and need to take a break.

The thing is, even though you might be able to ask around for advice, it's so much more satisfying to work through a problem on your own.

After several years, several starts and stops banging away, I've developed a couple habits (that's the "craft" bit) that have helped me get over these humps.

Telling those stories what I want to do with these blog posts. Maybe it'll help you figure out how to figure things out on your own, too. I know it'll give me structure to put my ideas in order!

I assume you're familiar with Haskell syntax, you have a Haskell compiler and you know how to launch and use a Haskell REPL. In the entries below, I use ghc and ghci. If you need help doing that, go to haskell.org stat!


Happy Day Dance and Coursing as Accompaniments
programmusic
What to do with these pieces? All the repetition, the dirt-simple harmonic progressions of most of these pieces--to the extent it adds up, it sums to a sort of minimalist minimalism--tight and bland. The pieces can be a nice mask for conversation or other distractions, although at a cost in mental energy that's still greater than actual silence.

That background role also suggests accompaniment. This post highlights two uses of the pieces as starting point. The first is by a good friend and expert audio engineer. He began with "Happy Day Dance" and used it as the starter track for a sonic collage, inspired by "As Falls Wichita, So Falls Wichita Falls" by Pat Metheny and Lyle Mays.

http://dl.dropbox.com/u/8704898/Happy%20Day%20Dance/FlightOverdue.m4a

His summary:

"The little girl yelling in that "concrete jungle" patch gave me the idea that maybe she's in the city on the way to the airport to take a trip. So she travels to the rain forest, jungle, beach, but then flying back some bad things happen to the airplane, they ditch at sea, and she needs to be rescued. (Oh and let's not forget the alien like spaceship noises - maybe the little grey guys are lending a hand helping the rescue helicopter and ship find her!) .. Or maybe I watch too many (sci fi) movies!"

In a similar vein, I tried my hand at a bare-bones music video, using "Coursing" as a starting point:

http://www.vimeo.com/18351203

The pulse of the music and the echoes back and forth when you listen with headphones seemed to fit the dense, regular patterns on the bark of trees. To match the slow motion in the music, I tried different simple movements across the bark, then stitched together clips at roughly the same time intervals as the shifts in the music harmony.

Accompaniment seems like a good fit for these pattern pieces. Generating parts from the Haskell has been fun, but the regularity of the voices and the unending continuity of the texture makes them not so well-suited to live performance. Going forward, my plan is to tailor the process so the parts will be easier to perform.

?

Log in