[Haskell-cafe] Re: Monads and constraint satisfaction problems (CSP)

[Greg Meredith]

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 at linspireinc.com>
> Subject: Re: [Haskell-cafe] Monads and constraint satisfaction
>        problems (CSP)
> To: "Greg Meredith" <lgreg.meredith at biosimilarity.com>
> Cc: haskell-cafe <haskell-cafe at haskell.org>
> Message-ID: <ejkwj0vs.wl%jeremy.shaw at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070531/c4d642a2/attachment-0001.htm