[Haskell-beginners] complex typeclass/constraint question

[Brent Yorgey]

On Wed, Aug 29, 2012 at 12:28:37AM -0700, Dennis Raddle wrote:
> {- I'm writing code to do some combinatorial construction via test-and-evaluate
> algorithms. And I want to write a very generic algorithm. The idea is
> that the item being constructed has a current state, which is
> represented by a data type of typeclass EvalState. And the algorithm
> will consider a set of new elements to add to the object being
> constructed, represented by a data type of typeclass ElemSet. Here are
> the class definitions:
> 
> -}
> class ElemSet a where
>   elemSetNumElements :: a -> Int
> 
> class EvalState s where
>   isCompleteState :: s -> Bool
>   newElemSet :: ElemSet a => s -> a
>   integrateElem :: ElemSet a => a -> Int -> s -> s
>   -- given an elem set, and an index of the elem to choose , compute a score
>   scoreElem :: ElemSet a => a -> Int -> s -> EvalScore

As it stands, the EvalState class is quite useless, and almost
certainly not what you want.  Consider the type of
newElemSet:

  newElemSet :: ElemSet a => s -> a

This means that, given some type s which is an instance of EvalState,
a user calling newElemSet can ask for *any type they want* as the
output as long as it is an instance of ElemSet, and newElemSet has to
construct it for them.  Which seems rather difficult when all
newElemSet has to go on is that instances of ElemSet can be queried
for their size --- not much help at all in *constructing* one.

integrateElem and scoreElem have similar problems -- they have to be
able to deal with arbitrary instances of ElemSet, but the only thing
they have to go on is the number of elements

I suspect what you really want is for each instance of EvalState to
have some *particular* type associated with it to represent ElemSets.
There are two ways to do this.  One is using a multi-parameter type
class with a functional dependency:

  class ElemSet a => EvalState s a | s -> a where
    ...
    newElemSet :: s -> a
    ...

The other way is using an associated type family:

  class ElemSet (ESType s) => EvalState s where
    type ESType s :: *
    ...
    newElemSet :: s -> ESType s
    ...

Personally I would use the latter in this case.

It's also possible I've completely misunderstood what you're trying to
do; but whatever it is, your current EvalState class is not going to
work.

-Brent