Fwd: [Haskell-beginners] combinatorial
Patrick LeBoutillier
patrick.leboutillier at gmail.com
Sun Nov 22 17:04:11 EST 2009
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
More information about the Beginners
mailing list