[Haskell-cafe] help with musical data structures

wren ng thornton wren at freegeek.org
Mon Nov 16 03:13:55 EST 2009

Stephen Tetley wrote:
> Hello Mike
> A pitch class set represents Z12 numbers so I'd define a Z12 number
> type then store it in a list (if you have need a multiset -
> duplicates) or Data.Set (if you need uniqueness).

If you want an efficient implementation for *sets* of Z12 numbers I'd 
recommend using bit arithmetic. Pick some Word type with at least 12 
bits and use bit0 to represent including 0 in the set, bit1 to represent 
including 1, bit2 for 2, etc. This can be generalized for any Zn 
provided n is a suitably small number. Z16 may be a good place to start 
if you want wider applicability, though you'd want to wrap that with 
error checking code in order to exclude 12..15.

     import Data.Word
     import Data.Bits

     newtype Z16 = Z16 Word16

     z16_0 = 1 `shiftL` 0
     z16_1 = 1 `shiftL` 1
     z16_2 = 1 `shiftL` 2

     union        = (.|.)
     intersection = (.&.)

But I don't know whether you need to deal more with sets or with the 
elements therein, so that might reduce the efficiency of this approach.

Live well,

More information about the Haskell-Cafe mailing list