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
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]]
We can relax this requirement by returning a list of all phrases that are of length n (and were not unacceptable) and then doing some kind of fold. If you can relax the maximum requirement, you can make it not necessary to know the entire solutions space before you can start returning results. In that case, the worker function looks something like: type Evaluator = [MidiPitch] -> Maybe Float] workFunc :: Int -> [MidiPitch] -> Evaluator -> [[MidiPitch]] Letting Int decrease in successive iterations. And you probably want some sort of generating function: generateFunc :: [MidiPitch] -> [[MidiPitch]] And then you can let the list (or logic) monad work its magic. workFunc 0 song eval = return song workFunc n song eval = do song' <- generateFunc case eval song' of Nothing -> [] _ -> return song' Note that since your evaluation function is not incremental (i.e. I can't pass it a partial evaluation) I don't maintain scores in workFunc. Cheers, Edward
Excerpts from Edward Z. Yang's message of Sun Nov 22 13:29:42 -0500 2009:
Letting Int decrease in successive iterations.
[snip]
workFunc 0 song eval = return song workFunc n song eval = do song' <- generateFunc case eval song' of Nothing -> [] _ -> return song'
Um, I fudged the recursive case. workFunc n song eval = do song' <- generateFunc case eval song' of Nothing -> [] _ -> workFunc (n-1) song' eval Cheers, Edward
Edward Z. Yang wrote:
We can relax this requirement by returning a list of all phrases that are of length n (and were not unacceptable) and then doing some kind of fold.
Thanks for the advice and code.
Note that since your evaluation function is not incremental (i.e. I can't pass it a partial evaluation) I don't maintain scores in workFunc.
I'm not totally exactly sure what you mean here, but my evaluation function can in fact evaluate phrases of any length. In fact, I realized after seeing your reply that I failed to describe my problem well at all. Here's what I had in mind for a search algorithm. The idea is to combine features of greedy and broad search. I have no idea is this is a good idea. It's just a thought. Let's say we start by evaluating all lists of length 2 and picking those tied for the maximum score. Then the algorithm is, for each input list of length 2 tied for maximum, make all lists of length 3 that are acceptable (that don't return Nothing when evaluated) concat all those evaluate all of them and pick all tied for the maximum feed into next step (continue with lengths 4..N.) The idea is that's a greedy algorithm that still allows for some breadth of search by looking at ties. In my scoring system there will often be ties. Thanks, Mike
Excerpts from Michael Mossey's message of Sun Nov 22 17:30:57 -0500 2009:
I'm not totally exactly sure what you mean here, but my evaluation function can in fact evaluate phrases of any length.
Say I have [A, B] which evaluates to 3. If I want to know the score of [A, B, C], I can't say, "Oh, but remember that [A, B] is 3." It's not a fold, essentially.
Here's what I had in mind for a search algorithm. The idea is to combine features of greedy and broad search. I have no idea is this is a good idea. It's just a thought.
If by greedy you mean depth-first and by broad you mean breadth-first, this is a certainly a good idea. If you'd like to look it up further, check "beam search".
Let's say we start by evaluating all lists of length 2 and picking those tied for the maximum score. Then the algorithm is,
for each input list of length 2 tied for maximum, make all lists of length 3 that are acceptable (that don't return Nothing when evaluated) concat all those evaluate all of them and pick all tied for the maximum feed into next step (continue with lengths 4..N.)
The idea is that's a greedy algorithm that still allows for some breadth of search by looking at ties. In my scoring system there will often be ties.
It sounds like you've basically got the algorithm written down, you have to translate it to Haskell. Do you have a specific problem? Cheers, Edward
Edward Z. Yang wrote:
If by greedy you mean depth-first and by broad you mean breadth-first, this is a certainly a good idea. If you'd like to look it up further, check "beam search".
I think I mean that. Thanks for the tip.
It sounds like you've basically got the algorithm written down, you have to translate it to Haskell. Do you have a specific problem?
No, I think I've got it now, but it is always interesting to me to see what new things I learn when the more experienced members on the list give me their thoughts. I'm just checking if anyone wants to suggest that I'm off course and a better way exists. Thanks, Mike
participants (3)
-
Edward Z. Yang -
Michael Mossey -
Michael P. Mossey