[Haskell-beginners] combinatorial

[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