# maybe this could be improved?

7 messages
Open this post in threaded view
|

## maybe this could be improved?

 I've got some code which could be made simpler, I hope. the problem is this: I am implementing a software sampling synthesizer. For a given musical instrument, like piano, there are sound samples in memory. One purchases or creates sample sets. To save time money & resources, most sample sets are not complete---they have samples for only some of the pitches. Perhaps every third pitch has a sample. For the software to produce the sound for a non-included pitch, the software finds the closest included sample and plays it back slightly slower/faster to get the target pitch. That leads to the following code. Any ideas for improvement are welcome. The problem is that there are many cases to check: an empty map? the requested pitch less than all available pitches, greater than all available, or somewhere between? I am specifically writing this to run in O( log n) time. (It would be simpler as O(n).) This particular algorithm probably doesn't need to run in O(log n) time, but I want to do it as an educational experience---I will have other applications that need to use Map in O(log n) time. import Control.Monad.Identity import Control.Monad.Error import Control.Monad import qualified Data.Map as M type Pitch = Int type Sample = String type SampleMap = M.Map Pitch Sample -- Given a SampleMap and a Pitch, find the Pitch in the SampleMap -- which is closest to the supplied Pitch and return that. Also -- handle case of null map by throwing an error. findClosestPitch :: SampleMap -> Pitch -> ErrorT String Identity Pitch findClosestPitch samples inPitch = do   when (M.null samples) \$ throwError "Was given empty sample table."   case M.splitLookup inPitch samples of     (_,Just _,_ ) -> return inPitch     (m1,_        ,m2) | (M.null m1) && not (M.null m2) -> case1                       | not (M.null m1) && (M.null m2) -> case2                       | otherwise                      -> case3       where case1 = return . fst . M.findMin \$ m2             case2 = return . fst . M.findMax \$ m1             case3 = return \$ closest (fst . M.findMax \$ m1)                                      (fst . M.findMin \$ m2)             closest a b = if abs (a - inPitch) < abs (b - inPitch)                            then a                            else b
Open this post in threaded view
|

## maybe this could be improved?

 On Sat, Nov 7, 2009 at 12:44 PM, Michael Mossey <[hidden email]> wrote: > ? ? ?where case1 = return . fst . M.findMin \$ m2 > ? ? ? ? ? ?case2 = return . fst . M.findMax \$ m1 > ? ? ? ? ? ?case3 = return \$ closest (fst . M.findMax \$ m1) > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (fst . M.findMin \$ m2) > ? ? ? ? ? ?closest a b = if abs (a - inPitch) < abs (b - inPitch) > ? ? ? ? ? ? ? ? ? ? ? ? ? then a > ? ? ? ? ? ? ? ? ? ? ? ? ? else b > I'd try writing quickcheck properties for these cases. That is a really complicated function. It strikes me that a lot of those cases need less available in their scopes than they have. You could force that by breaking the cases and closest into individual functions. Then you could write properties for them. Then you are left with only one complex function determining which case you need. Possibly you could return the case directly? Anyway, that's not as helpful as telling you that you just reinvented a 4 and a half gainer comonad or whatever but if you start cutting this thing up you might notice a structure you already know. -- Darrin
Open this post in threaded view
|

## maybe this could be improved?

 In reply to this post by Michael Mossey Michael, Your code is interesting and I'd like to run it, but I'm not to familiar with Maps and Monad transformers. Could you provide a function to create a SampleMap and a way to test it from ghci? Thanks, Patrick On Sat, Nov 7, 2009 at 12:44 PM, Michael Mossey <[hidden email]> wrote: > I've got some code which could be made simpler, I hope. the problem is > this: I am > implementing a software sampling synthesizer. For a given musical > instrument, like piano, there are sound samples in memory. One purchases > or creates sample sets. To > save time money & resources, most sample sets are not complete---they have > samples for only some of the pitches. Perhaps every third pitch has a > sample. For the software to produce the sound for a non-included pitch, > the software finds the closest included sample and plays it back slightly > slower/faster to get the target pitch. > > That leads to the following code. Any ideas for improvement are welcome. > The problem is that there are many cases to check: an empty map? the > requested pitch less than all available pitches, greater than all > available, or somewhere between? I am specifically writing this to run in > O( log n) time. (It would be simpler as O(n).) This particular algorithm > probably doesn't need to run in O(log n) time, but I want to do it as an > educational experience---I will have other applications that need to use > Map in O(log n) time. > > import Control.Monad.Identity > import Control.Monad.Error > import Control.Monad > import qualified Data.Map as M > > type Pitch = Int > type Sample = String > type SampleMap = M.Map Pitch Sample > > > -- Given a SampleMap and a Pitch, find the Pitch in the SampleMap > -- which is closest to the supplied Pitch and return that. Also > -- handle case of null map by throwing an error. > findClosestPitch :: SampleMap -> Pitch -> ErrorT String Identity Pitch > findClosestPitch samples inPitch = do > ?when (M.null samples) \$ throwError "Was given empty sample table." > ?case M.splitLookup inPitch samples of > ? ?(_,Just _,_ ) -> return inPitch > ? ?(m1,_ ? ? ? ?,m2) | (M.null m1) && not (M.null m2) -> case1 > ? ? ? ? ? ? ? ? ? ? ?| not (M.null m1) && (M.null m2) -> case2 > ? ? ? ? ? ? ? ? ? ? ?| otherwise ? ? ? ? ? ? ? ? ? ? ?-> case3 > ? ? ?where case1 = return . fst . M.findMin \$ m2 > ? ? ? ? ? ?case2 = return . fst . M.findMax \$ m1 > ? ? ? ? ? ?case3 = return \$ closest (fst . M.findMax \$ m1) > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (fst . M.findMin \$ m2) > ? ? ? ? ? ?closest a b = if abs (a - inPitch) < abs (b - inPitch) > ? ? ? ? ? ? ? ? ? ? ? ? ? then a > ? ? ? ? ? ? ? ? ? ? ? ? ? else b > > > > _______________________________________________ > Beginners mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/beginners> -- ===================== Patrick LeBoutillier Rosem?re, Qu?bec, Canada
Open this post in threaded view
|

## maybe this could be improved?

 Patrick LeBoutillier wrote: > Michael, > > Your code is interesting and I'd like to run it, but I'm not to > familiar with Maps and Monad transformers. > Could you provide a function to create a SampleMap and a way to test > it from ghci? > Sure, import Control.Monad.Identity import Control.Monad.Error import Control.Monad import qualified Data.Map as M type Pitch = Int type Sample = String type SampleMap = M.Map Pitch Sample -- Given a SampleMap and a Pitch, find the Pitch in the SampleMap -- which is closest to the supplied Pitch and return that. Also -- handle case of null map by throwing an error. findClosestPitch :: SampleMap -> Pitch -> ErrorT String Identity Pitch findClosestPitch samples inPitch = do   when (M.null samples) \$ throwError "Was given empty sample table."   case M.splitLookup inPitch samples of     (_,Just _,_ ) -> return inPitch     (m1,_        ,m2) | (M.null m1) && not (M.null m2) -> case1                       | not (M.null m1) && (M.null m2) -> case2                       | otherwise                      -> case3       where case1 = return . fst . M.findMin \$ m2             case2 = return . fst . M.findMax \$ m1             case3 = return \$ closest (fst . M.findMax \$ m1)                                      (fst . M.findMin \$ m2)             closest a b = if abs (a - inPitch) < abs (b - inPitch)                            then a                            else b testMap1 = M.fromList [ (1,"sample1")                        , (5,"sample2")                        , (9,"sample3") ] -- testMap2 ==> Right 1 testMap2 = runIdentity \$ runErrorT \$ findClosestPitch testMap1 2 -- testMap3 ==> Right 5 testMap3 = runIdentity \$ runErrorT \$ findClosestPitch testMap1 5 -- testMap4 ==> Left "Was given empty sample table." testMap4 = runIdentity \$ runErrorT \$ findClosestPitch M.empty 5
Open this post in threaded view
|

## maybe this could be improved?

 Michael, Here's my stab at it, not sure if it's really better though: findClosestPitch :: SampleMap -> Pitch -> ErrorT String Identity Pitch findClosestPitch samples inPitch = do   when (M.null samples) \$ throwError "Was given empty sample table."   case M.splitLookup inPitch samples of     (_, Just _, _) -> return inPitch     (ml, _, mh)    -> return \$ approxPitch ml mh     where       approxPitch ml mh | M.null ml = fst . M.findMin \$ mh       approxPitch ml mh | M.null mh = fst . M.findMax \$ ml       approxPitch ml mh             = closest (fst . M.findMax \$ ml) (fst . M.findMin \$ mh)         where closest a b = min (inPitch - a) (b - inPitch) I tried to separate the approximation part from the rest of the code, and used a bit of deduction to eliminate (hopefully correctly...) some of the testing conditions. Anyways, I had fun doing working on this, and I learned a bit about computerized music as well! Thanks, Patrick On Wed, Nov 11, 2009 at 9:15 PM, Michael P Mossey <[hidden email]> wrote: > Patrick LeBoutillier wrote: >> >> Michael, >> >> Your code is interesting and I'd like to run it, but I'm not to >> familiar with Maps and Monad transformers. >> Could you provide a function to create a SampleMap and a way to test >> it from ghci? >> > > Sure, > > > import Control.Monad.Identity > import Control.Monad.Error > import Control.Monad > import qualified Data.Map as M > > type Pitch = Int > type Sample = String > type SampleMap = M.Map Pitch Sample > > > -- Given a SampleMap and a Pitch, find the Pitch in the SampleMap > -- which is closest to the supplied Pitch and return that. Also > -- handle case of null map by throwing an error. > findClosestPitch :: SampleMap -> Pitch -> ErrorT String Identity Pitch > findClosestPitch samples inPitch = do > ?when (M.null samples) \$ throwError "Was given empty sample table." > ?case M.splitLookup inPitch samples of > ? (_,Just _,_ ) -> return inPitch > ? (m1,_ ? ? ? ?,m2) | (M.null m1) && not (M.null m2) -> case1 > ? ? ? ? ? ? ? ? ? ? | not (M.null m1) && (M.null m2) -> case2 > ? ? ? ? ? ? ? ? ? ? | otherwise ? ? ? ? ? ? ? ? ? ? ?-> case3 > ? ? where case1 = return . fst . M.findMin \$ m2 > ? ? ? ? ? case2 = return . fst . M.findMax \$ m1 > ? ? ? ? ? case3 = return \$ closest (fst . M.findMax \$ m1) > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(fst . M.findMin \$ m2) > ? ? ? ? ? closest a b = if abs (a - inPitch) < abs (b - inPitch) > ? ? ? ? ? ? ? ? ? ? ? ? ?then a > ? ? ? ? ? ? ? ? ? ? ? ? ?else b > > > testMap1 = M.fromList [ (1,"sample1") > ? ? ? ? ? ? ? ? ? ? ?, (5,"sample2") > ? ? ? ? ? ? ? ? ? ? ?, (9,"sample3") ] > > -- testMap2 ==> Right 1 > testMap2 = runIdentity \$ runErrorT \$ findClosestPitch testMap1 2 > > > -- testMap3 ==> Right 5 > testMap3 = runIdentity \$ runErrorT \$ findClosestPitch testMap1 5 > > -- testMap4 ==> Left "Was given empty sample table." > testMap4 = runIdentity \$ runErrorT \$ findClosestPitch M.empty 5 > > > > > -- ===================== Patrick LeBoutillier Rosem?re, Qu?bec, Canada