On Wednesday, May 10, 2017 at 5:07:29 PM UTC+1, Rupert Smith wrote: > > By search, I mean a backtracking search over a 'graph' of possibilities. > > There is a well-known pretty printing library by Joh Hughes. It is for > Haskell but can be made to work on ML style languages by introducing some > laziness explicitly. Haskell is lazy by default, which is why it is not > needed there. > > http://belle.sourceforge.net/doc/hughes95design.pdf > > It defines lambdas that evaluate to the various possible choices then only > evaluates the 'best' choice according to a heuristic for evaluating pretty > printing possibilities. I think when a bad choice deeper down is uncovered, > it can backtrack? To be honest, I never really analysed the code and fully > understood it, just made use of it or blindly ported it to ML. > > Is there some library for Elm that helps with coding this kind of search? > Or a simpler example illustrating the technique? > > I am trying to do a 2d layout algorithm, and thinking of some heuristic > that will choose amongst various layouts, trying simpler and more symmetric > options first. >
I found this pretty printer which is desinged by Philip Wadler and builds on the Hughes pretty printer: http://package.elm-lang.org/packages/vilterp/elm-pretty-print/latest But this code looks optimised and I don't see how to pull out a re-usable back tracking search from it. So I think perhaps the Hughes design will be better to take as a starting point. In the paper he describes "Monads for Backtracking" which sounds like what I am after. I think I will try and implement a search that solves a 9-puzzle (you know with 8 tiles and a hole and you slide the tiles about to make a picture), using the 'Manhattan heuristic'. Easy problem to understand as an example of a heuristic search in order to figure out how to implement a back-tracking search and discover what code might be re-usable across different search problems. Quiet round here, ever since Noah told you all to behave yourselves. :-P -- You received this message because you are subscribed to the Google Groups "Elm Discuss" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
