On Thursday, May 11, 2017 at 11:01:51 AM UTC+1, Rupert Smith wrote: > > 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. >> > 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. -- 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.
