Fwd: [Haskell-beginners] combinatorial

Forgot to forward my response to the list... ---------- Forwarded message ---------- From: Patrick LeBoutillier Date: Sun, Nov 22, 2009 at 5:03 PM Subject: Re: [Haskell-beginners] combinatorial To: "Michael P. Mossey" Michael, Here's how I would go about this: type MidiPitch = Int range :: [MidiPitch] range = [10..90] -- Just a dummy eval function, allows up or down one unit eval ps | length ps <= 1 = Just 1.0 eval ps | length ps > 1  =  let a = last ps      b = last . init $ ps in  if abs (a - b) == 1     then Just 1.0     else Nothing coolFunc :: Int -> MidiPitch -> ([MidiPitch] -> Maybe Float) -> [[MidiPitch]] coolFunc n p f = generate n f [[p]] -- Generate MidiPitch lists up to a given length, making sure each step -- satisfies the eval function generate :: Int -> ([MidiPitch] -> Maybe Float) -> [[MidiPitch]] -> [[MidiPitch]] generate n f cs | n == 1 = cs generate n f cs = generate (n-1) f $ concat . map (\p -> try p cs) $ range -- Tries to add a MidiPitch to each of the MidiPitch lists, keep -- only the sequences that pass the eval. try :: MidiPitch -> [[MidiPitch]] -> [[MidiPitch]] try p = filter (not . null) . map (test p)  where test p ps =          let ps' = ps ++ [p] in          case eval ps' of            Nothing   -> []            otherwise -> ps' It's seems to work, although I'm sure many bits sould be made more elegant... Note: After that another pass would be required over the result set to find the sequences that have the highest scores. Patrick On Sun, Nov 22, 2009 at 5:25 AM, Michael P. Mossey wrote:

I'm trying to write a combinatorial search algorithm with evaluation, and kind of stuck. Not sure how to do this.

I'm constructing a musical phrase, which is a list of MidiPitch:

[MidiPitch]

I have an evaluation function that determines the fitness of any given phrase:

eval :: [MidiPitch] -> Maybe Float

This returns Nothing if the phrase is completely unacceptable.

The idea is to build up a phrase one midi pitch at a time, choosing all possible next pitches (notes) from a range:

next pitch comes from: [10..90]

Most of the pitches will result in a phrase that evaluates to Nothing, so the combinatoral "explosion" will be limited.

I'd like to write a function that constructs a phrase of length n, and in fact will have to return a list of all phrases that have equal scores of the maximum.

--         <length of output phrase> -> <first pitch> -> <eval func> -> --         <all tied phrases of best score> coolFunc :: Int -> MidiPitch -> ([MidiPitch] -> Maybe Float) ->           [[MidiPitch]]

I am stuck on how to write this.

thanks, Mike

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- ===================== Patrick LeBoutillier Rosemère, Québec, Canada -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada