[Haskell-beginners] combinatorial

Michael Mossey mpm at alumni.caltech.edu
Sun Nov 22 17:30:57 EST 2009

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.


More information about the Beginners mailing list