[Haskell-beginners] combinatorial

[Michael P. Mossey]

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
Begi...@haskell.org
http://www.haskell.org/mailman/listinfo/beginners

[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

[Edward Z. Yang]

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

[Patrick LeBoutillier]

Forgot to forward my response to the list...

---------- Forwarded message ----------
From: Patrick LeBoutillier <patrick.le...@gmail.com>
Date: Sun, Nov 22, 2009 at 5:03 PM
Subject: Re: [Haskell-beginners] combinatorial
To: "Michael P. Mossey" <m...@alumni.caltech.edu>

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

--
=====================
Patrick LeBoutillier
Rosem�re, Qu�bec, Canada

--
=====================
Patrick LeBoutillier
Rosem�re, Qu�bec, Canada

[Michael Mossey]

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

[Edward Z. Yang]

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

[Michael Mossey]

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