[elm-discuss] How would you code a search in Elm?

['Rupert Smith' via Elm Discuss]

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.

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
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

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
By search, I mean a backtracking search over a 'graph' of possibilities.

So I am starting to get my head around this. I had not come across the
concept of 'context passing representations' before, and for that alone,
Hughes' paper on pretty printing is worth a read. That is more of an
optimization though, but it also seems to have the effect of making
programs written in that style lazy enough to run on a strict FP like Elm
without needing to hack in more laziness.

I also read read Wadlers paper on Monads
(http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf) to
try and get my head around that, and am starting to get a feel for how
different search strategies can be written as effects that are added to an
unguided walk over the search space. Of all the things I have read on
monads, I think Wadlers paper is actually the easiest to follow.

To keep things simple, I encoded the farmer-wolf-goat-cabbage problem as a
state space, forming a graph of 'states' with 'moves' from states to states:

import EveryDict as Dict exposing (EveryDict)




type Character
= Farmer
| Wolf
| Goat
| Cabbage




type Position
= West
| East




type alias FWGCState =
EveryDict Character Position




characters : List Character
characters =
[ Farmer, Wolf, Goat, Cabbage ]




start : FWGCState
start =
Dict.empty
|> Dict.insert Farmer West
|> Dict.insert Wolf West
|> Dict.insert Goat West
|> Dict.insert Cabbage West




move : Character -> FWGCState -> FWGCState
move character state =
let
switch position =
case position of
East ->
West


West ->
East
in
if character == Farmer then
Dict.update Farmer (Maybe.map switch) state
else
Dict.update Farmer (Maybe.map switch) <|
Dict.update character (Maybe.map switch) state




type alias Step state =
state -> List state




step : Step FWGCState
step state =
List.foldl (\character -> \states -> move character state :: states) []
characters



Now I can write a recursion over the state space. Notice that this function
knows nothing about the nature of the states being explored, as state is a
polymorphic type parameter:

search : Step state -> state -> List state
search step state =
List.foldl (\state -> \states -> search step state ++ states) [] <|
step state



Of course, this infinite loops:

main =
text <| toString (search step start)

Uncaught RangeError: Maximum call stack size exceeded

But I can see that I can build different searches over this state space by
replacing the explicit infinite listing of it. Instead defining a monad
that will give me operations to 'succeed' on a goal state and to list a
state 'orelse' other states as further possibilities to explore, and
rewriting the search in terms of those operations. I will also need an
operation to 'filter' or 'fail' states that are illegal, otherwise the wolf
will eat the goat.

'orelse' could have implementations giving depth-first or breadth-first
ordering.

I could also have 'cost' and 'heuristic' functions, and have 'orelse' order
possibilities by the output of these functions to produce lowest cost first
or heuristically guided searches.

I wrote a GOFAI search library for Java that breaks this kind of search
down into orthogonal, composable aspects and allows them to be combined to
produce a large variety of different search strategies:

https://github.com/rupertlssmith/lojix/tree/master/lojix/search/src/main/com/thesett/aima/search

What I have in mind is something similar for Elm.

===

Also wondering if I am going to run into any problems with mutual recursion
and insufficient tail-call
optimization: http://package.elm-lang.org/packages/elm-lang/trampoline/1.0.1/Trampoline.
This could get pretty complex. I'll give it a go anyway.

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
But I can see that I can build different searches over this state space by
replacing the explicit infinite listing of it. Instead defining a monad
that will give me operations to 'succeed' on a goal state and to list a
state 'orelse' other states as further possibilities to explore, and
rewriting the search in terms of those operations. I will also need an
operation to 'filter' or 'fail' states that are illegal, otherwise the wolf
will eat the goat.

So I tried writing it in a monadic style, but it was confusing as hell; I
somehow could not come up with unit and bind operators that obeyed the
monad laws - these were supposed to take my strict (non-lazy) infinite walk
over the search space and turn it into a stepwise one. Part of the trouble
with monads is that if you google about them you very quickly get into the
deep end, lots of Haskell code that assumes that you know a lot already.

I preferred the Hughes paper approach with the 'context passing
representation'. He shows how to apply that to monads, but also applies it
in other situations too.

I found some old posts about Elm and monads and type classes, and remarks
from Evan that he did not want to bring over some of the negative baggage
that monads carry in Haskell:
https://groups.google.com/forum/#!topic/elm-discuss/hEvS6DgNbwM
Smart move I would say. If Elm were more like Haskell, it might be more
powerful but I think it would have attracted the more academic types and
less of the practical folk that just want to make nice stuff for the web.

Anyway, I just hacked at it until I got a simple search working and its
fairly obvious which parts of that can be broken out into combinators,
allowing the various aspects of search to be mixed and matched to produce a
variety of different searches.

So it looks like the structure of it will be like this:

A basic search algorithm that combines search operators to produce a search
- depth first, breadth first, iterative deepening, ordered by cost or
heuristic, memoization or not, and so on.
A type definition of the parts of a search that the user must supply - a
step function to walk over the state space, indication of when a state is a
goal state, cost and heuristic functions.
A search API providing all the different types of searches that can be
built from the search combinators, ready to use - A star, greedy, bounded,
iterative etc.

===

Searches of this kind can potentially run for a long time, which is a
problem in an interactive UI program. Also as javascript on the browser is
single threaded, it will be especially noticeable if a search runs for a
while and the UI feels frozen during this.

I therefore am making the search function only examine one search node each
time it is called. The examined node will be returned with a continuation
to run the rest of the search. So the output from a search will look like
this:

type SearchResult state
= Complete
| Goal state (() -> SearchResult state) -- There may be more goal
states further on after a goal state.
| Ongoing state (() -> SearchResult state)

There is a function 'next' to iterate once, and a function 'nextGoal' to
iterate until the next goal state is found.

The idea is that in an interactive environment, you will use the 'next'
function to run some loops of the search, and then return control to the
Elm kernel whether the search is still running or a goal state was found.
This will allow the interactive environment to handle user inputs and make
updates to the display and so on, and then a Cmd can be chained onto the
end of that to continue the search for another burst.

Another nice thing to do might be to do this adaptively. So take a
timestamp, run say 10 loops of the search, then take another timestamp,
calculate 'timePerLoop'. Decide what the biggest delay the user can live
with is, maybe 10 to 100 milliseconds. On the next time around try to run
as many loops of the search as timePerLoop permits. Also time each burst
and adjust timePerLoop if necessary.

Its explicit time-slicing, which is not so nice but I can't see another way
of handling long running computations gracefully.