Brandon, Jeremy, et al,

Thanks for the pointers. The paper by OlegK, et al, articulates exactly the structure i was noticing, except that i was coming at it from the other end. i was noticing that a wide range of these CSP-style problems could be decomposed into a trivial monad ( e.g., list, multiset, set) and some additional search machinery (over which a good solution should be parametric). They show how to add a reasonable upper limit on the search machinery to any monad.

Best wishes,

--greg

Date: Thu, 31 May 2007 11:36:55 -0700
From: "Jeremy Shaw" < jeremy.shaw@linspireinc.com>
Subject: Re: [Haskell-cafe] Monads and constraint satisfaction
problems (CSP)
To: "Greg Meredith" <lgreg.meredith@biosimilarity.com>
Cc: haskell-cafe < haskell-cafe@haskell.org>
Message-ID: <ejkwj0vs.wl%jeremy.shaw@linspireinc.com>
Content-Type: text/plain; charset=US-ASCII

At Thu, 31 May 2007 10:42:57 -0700,
Greg Meredith wrote:

> BTW, i think this could have a lot of bang-for-buck because the literature i
> read exhibited two basic features:
>
> - the "standard" treatments (even by CS-types) are decidedly not
> compositional
> - the people in the field who face industrial strength csp problems
> report that they have to take compositional approaches because the problems
> are just too large otherwise (both from a human engineering problem as well
> as a computational complexity problem)

This paper describes a non-monadic, compositional method for solving CSPs:

http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf

There is also the LogicT monad transformer:

http://okmij.org/ftp/Computation/monads.html

j.

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com