On Saturday, May 13, 2017 at 11:40:59 PM UTC+1, Rupert Smith wrote: > > 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. -- 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.
