[Haskell-cafe] need help understanding how to specify constraints on monads

Dennis Raddle dennis.raddle at gmail.com
Thu Jun 28 22:23:18 UTC 2018


​Thanks, Paolino. I will study this.

I'll explain my larger goal. Probably should have started with that.

I'm writing algorithms to optimize data structures by backtracking search.

More specifically, I'm optimizing musical compositions.

But I have several possible representations of a composition and I'd like
to swap them in and out.

I also have several ideas for a search algorithm. The search will function
kind of like a chess program, adding notes to the composition one at a time
and looking ahead N notes, then using some kind of fitness evaluation
function to find the best "next move."

There are variations on this algorithm possible. The fitness function will
be computed by summing the fitness from "evaluation units" which,
individually, look at only one aspect of good music. Together they have a
more comprehensive view. I can easily try variations on the search by
adding or removing "evaluation units".

For another source of variation, I may use a fully deterministic algorithm,
or I may use some pseudorandomness in choosing what paths to search, in
various combinations.

So how do I write a search algorithm when I don't know the type of the data
structure or the evaluation units?

My idea was to create a typeclass, Comp, parameterized on the the
composition data structure ('comp'), the data type of a single "move" or
step to be added, ('step'), and the type of an evaluation units ('eu').

class Comp comp eu step | comp -> eu, comp -> step where
  listPossibleSteps :: comp -> [step]
  addStep :: comp -> step -> comp
  evalComp :: eu -> comp -> comp

This should offer all the necessary computations to implement backtracking
search of many flavors.

There's a lot more to how I want to implement this algorithm, mainly that I
want to log "analytics" to be able to examine its behavior, so that's where
the ReportLog data type and State (or possibly Writer) monad came into it,
but never mind that for now. I'm probably not even on the right track with
this much.

D
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180628/ad8b5625/attachment.html>


More information about the Haskell-Cafe mailing list