+%format da' = "d_a^\prime"

%format expand = "\delta"

%format nexpanded = "n_{\delta}s"

+%format ndelta = "n_\delta"

\renewcommand{\abstractname}{Summary}

+ , search, iterativeDFS) where

Next, we import a few base Haskell modules that contain some useful

import Control.Applicative ((<$>))

+import Data.Function (on)

import Data.List (sortBy)

import Data.List.Ordered (mergeBy)

mkNode (Path as qs) at qt = Path (at:as) (qt:qs)

-\section{Search Methods}\todo[inline]{Custom strategies.}

-The difference between the search methods implemented is in how they order the

-frontier\footnote{The frontier is the list of nodes yet to be examined.}, and

-thus the order of node examination. In this implementation, search methods are

-defined as a frontier modification function. All methods are guaranteed to be

-stable \cite{stable}, ie. the relative order of the nodes provided by the

-|expand| function will be preserved in the frontier.

-To shorten type signatures, a |FrontierApp| alias is declared. This alias

-is polymorphic over the action |a| and state |q| types, like |Path|, and

-represents a function that combines the current frontier (hereupon |frontier|)

-and a list of new nodes (hereupon |nexpanded|\footnote{From \emph{n}ode,

-$\delta$ (see section \ref{search}) and the common Haskell suffix \emph{s} for

-lists.}) to create a new frontier.

-type FrontierApp a q = [Path a q] -> [Path a q] -> [Path a q]

-\subsection{Uninformed Methods}

-The two uninformed methods are trivial to define: a breadth first search will

-add new nodes to the end of the list, while a depth-first search will add them

-to the start of the list.

-breadthFirst, depthFirst :: FrontierApp a q

-\subsection{Informed Methods}

-The two informed methods are slightly more complex, since they take additional

-Firstly, greedy breadth first search (GBFS). GBFS takes only one additional

-factor into account, namely an estimated distance to the a goal node, typically

-designated $h(n)$ where $n$ represents the current node. |greedyBF| takes a

-heuristic function of type |q -> Integer|, and returns a |FrontierApp| that

-sorts the frontier using that function.

-greedyBF :: (Ord m, Num m) => (q -> m) -> FrontierApp a q

-greedyBF h frontier nexpanded = mergeUSOn h' nexpanded frontier where

-A* search takes both $h(n)$ and a known path cost $g(n)$ into account. |g|

-accepts the action type |a| instead of the state |q| to allow for simple state

-sharing, if the caller desires\footnote{Obviously, the function could be

-broadened to |q -> a -> Integer| if required in a later version.}.

--- TODO: presorted version

-aStar :: (Ord m, Num m) => (a -> m) -> (q -> m) -> FrontierApp a q

-aStar g h frontier nexpanded = mergeUSOn f nexpanded frontier where

- f (Path (at:_) (qt:_)) = h qt + g at

\section{Running a Search}\label{search}

-Using the ~~above~~ definitions, the |search| function is fairly trivial, simply

+Using the below definitions, the |search| function is fairly trivial, simply

expanding the head of the frontier until a goal state is reached or the frontier

-|search| takes a |FrontierApp| value |app|, expansion function

-|expand|\footnote{\label{delta}In reference to the transition functions of

-NFA.}, a goal predicate |goalp|\footnote{From set-builder notation

+|search| takes a frontier application value |app| (see section \ref{methods}),

+expansion function |expand|\footnote{\label{delta}In reference to the transition

+functions of NFA.}, a goal predicate |goalp|\footnote{From set-builder notation

$\Phi$\cite{set-notation} and the NFA goal set $F$\cite{nfa}.} and an initial

state |q0|\footnote{ibid.}. The function returns a |Maybe| value because the

goal state may not be achievable.

type SearchResult a q = (Int, Maybe (Path a q))

- (Path a q -> [Path a q]) ->

+ (Path a q -> [Path a q]) ->

The root of the search tree is defined as |q0| and the recursive function |go|

go procCount [] = (procCount, Nothing)

+\section{Search Methods}\label{methods}\todo[inline]{Custom strategies.}

+The difference between the search methods implemented is in how they order the

+frontier\footnote{The frontier is the list of nodes yet to be examined.}, and

+thus the order of node examination. In this implementation, search methods are

+defined as a frontier modification function. All methods are guaranteed to be

+stable \cite{stable}, ie. the relative order of the nodes provided by the

+|expand| function will be preserved in the frontier.

+To shorten type signatures, a |FrontierApp| alias is declared. This alias

+is polymorphic over the action |a| and state |q| types, like |Path|, and

+represents a function that combines the current frontier (hereupon |frontier|)

+and a list of new nodes (hereupon |nexpanded|\footnote{From \emph{n}ode,

+$\delta$ (see section \ref{search}) and the common Haskell suffix \emph{s} for

+lists.}) to create a new frontier.

+type FrontierApp a q = [Path a q] -> [Path a q] -> [Path a q]

+\subsection{Uninformed Methods}

+The two uninformed methods are trivial to define: a breadth first search will

+add new nodes to the end of the list, while a depth-first search (DFS) will add

+them to the start of the list.

+breadthFirst, depthFirst :: FrontierApp a q

+\subsection{Informed Methods}

+The two informed methods are slightly more complex, since they take additional

+Firstly, greedy breadth first search (GBFS). GBFS takes only one additional

+factor into account, namely an estimated distance to the a goal node, typically

+designated $h(n)$ where $n$ represents the current node. |greedyBF| takes a

+heuristic function of type |q -> Integer|, and returns a |FrontierApp| that

+sorts the frontier using that function.

+greedyBF :: (Ord m, Num m) => (q -> m) -> FrontierApp a q

+greedyBF h frontier nexpanded = mergeUSOn h' nexpanded frontier where

+A* search takes both $h(n)$ and a known path cost $g(n)$ into account. |g|

+accepts the action type |a| instead of the state |q| to allow for simple state

+sharing, if the caller desires\footnote{Obviously, the function could be

+broadened to |q -> a -> Integer| if required in a later version.}.

+aStar :: (Ord m, Num m) => (a -> m) -> (q -> m) -> FrontierApp a q

+aStar g h frontier nexpanded = mergeUSOn f nexpanded frontier where

+ f (Path (at:_) (qt:_)) = h qt + g at

+\subsection{Iterative Deepening DFS}

+Iterative deepening DFS is a depth-first search where the maximum depth of the

+DFS is increased each run until the shallowest goal state is found \cite{iddfs}.

+It is equivalent to breadth-first search in that it will find the optimal

+solution, but it trades a smaller memory footprint for a longer run time.

+To start, a function for limiting the depth of an arbitrary |FrontierApp| is

+defined. The function takes a parameter |da| that extracts the depth from the

+action value; that is, the caller is expected to keep track of search depth.

+This saves some bookkeeping here and is simple enough for the caller to

+implement, especially for a search with a monotonic $g(n)$ cost.

+limitApp :: (Ord m, Num m) =>

+limitApp app da limd frontier [] = frontier

+limitApp app da limd frontier nexpanded@(ndelta:_)

+ | da' ndelta > limd = frontier

+ | otherwise = app frontier nexpanded

+ da' = da . head . actions

+Once the depth of a search can be limited via the |FrontierApp| value, the next

+step is repeating the search with higher limits until a solution is found. To

+avoid nontermination in the event there is no solution, the function checks

+if more nodes were created compared to the last run; if not, the search tree

+has been fully explored and the |Nothing| result can be returned.

+iterativeSearch :: (Eq q, Ord m, Num m) =>

+ (m -> FrontierApp a q) ->

+ (Path a q -> [Path a q]) ->

+iterativeSearch limitedApp expand goalp q0 = go 0 1 where

+ go procMax lim = case hM of

+ Nothing | procCount > procMax -> go procCount (lim + 1)

+ res@(procCount, hM) = search (limitedApp lim) expand goalp q0

+Now the |iterativeDFS| function can be defined. This is not purely a

+|FrontierApp| value like the other search methods, but the majority of the

+signature is similar to the |search| function and so re-use is not impacted in

+iterativeDFS :: (Eq q, Ord m, Num m) =>

+ (Path a q -> [Path a q]) ->

+iterativeDFS da = iterativeSearch (limitApp depthFirst da)

\section{Utility Definitions}

\url{https://en.wikipedia.org/wiki/Sorting_algorithm#Stability}

+ `Iterative deepening depth-first search',

+ \url{https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search}