Fwd: [Haskell-beginners] combinatorial

[Patrick LeBoutillier]

Forgot to forward my response to the list...

---------- Forwarded message ----------
From: Patrick LeBoutillier <patrick.leboutillier at gmail.com>
Date: Sun, Nov 22, 2009 at 5:03 PM
Subject: Re: [Haskell-beginners] combinatorial
To: "Michael P. Mossey" <mpm at 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


On Sun, Nov 22, 2009 at 5:25 AM, Michael P. Mossey
<mpm at alumni.caltech.edu> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



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



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