[Haskell-beginners] combinatorial

[Edward Z. Yang]

> 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