Commits

Rhys ! committed 34256bf Draft

documentation updates

Comments (0)

Files changed (3)

 * Depth-first search
 * Greedy best-first
 * A* search
+* Iterative deepening depth-first search
 
 Missing features
 ----------------
-No custom search strategies as of yet.
+No custom informed search strategy as of yet.
+
+Acknowledgements
+----------------
+* Brent Yorgey & Louis Wasserman for the [split][] package.
+* Leon P Smith for the [data-ordlist][] package.
+* Authors of the Haskell Platform packages.
+* Authors of documents referenced in literate code.
 
 [platform]: http://www.haskell.org/platform/
 [lhs2Tex]: http://www.andres-loeh.de/lhs2tex/
+[split]: https://hackage.haskell.org/package/split-0.2.2
+[data-ordlist]: https://hackage.haskell.org/package/data-ordlist-0.4.6
                , search, iterativeDFS) where
 \end{code}
 
-Next, we import a few base Haskell modules that contain some useful
-functions.\todo[inline]{Acknowledgments: Data.List.Ordered and
-Data.List.Split.}
+Next, we import a few Haskell modules that contain some useful
+functions. The only non-base module is |Data.List.Ordered| from the
+\emph{data-ordlist} \cite{ordlist} package, which is here providing an ordered
+merge for lists.
 
 \begin{code}
 import Control.Applicative ((<$>))
 less element than the states list.
 
 \begin{code}
-data Path a q =  Path  { actions :: [a]
-                       , states :: [q] }
+data Path a q =  Path  {  actions  :: [a]
+                       ,  states   :: [q] }
 \end{code}
 
 Next, a couple of constructor-like functions for |Path| are defined; one to
 \end{code}
 
 The root of the search tree is defined as |q0| and the recursive function |go|
-is called with the root-populated frontier.\todo[inline]{Note counter.}
+is called with the root-populated frontier. |go| also counts the number of nodes
+processed so far; this is summed with the length of the frontier so the total
+number of nodes in the search tree can be returned with the (lack of) result.
 
 \begin{code}
 search app expand goalp q0 = go 0 [mkRoot q0] where
 returned.
 
 \begin{code}
-      go procCount [] = (procCount, Nothing)
+      go procCount []     = (procCount, Nothing)
 \end{code}
 
 \section{Search Methods}\label{methods}\todo[inline]{Custom strategies.}
 %endif
     \item Sorting and merging ordered lists on a transform. The underlying
           |sortBy| and |mergeBy| functions are stable, and thus are all the
-          functions below.\todo[inline]{Check sort performance.}
+          functions below.
 \begin{code}
 sortOn :: (Ord b) => (a -> b) -> [a] -> [a]
 sortOn f = sortBy (compare `on` f)
   `The Haskell Programming Language'
   \url{http://www.haskell.org/haskellwiki/Haskell}
 
+\bibitem{ordlist}
+  Smith L.P.,
+  `data-ordlist: Set and bag operations on ordered lists'
+  \url{https://hackage.haskell.org/package/data-ordlist-0.4.6}
+
 \bibitem{adt}
   HaskellWiki,
   `Algebraic data type'
+-- CLI for NxM search.
+
 import Control.Applicative ((<$>))
 import Data.List (intercalate)
 import Data.List.Split (splitOn)
               , aStar, breadthFirst, depthFirst, greedyBF )
 import NMPuzzle (NMPuzzle, expand, hTaxicab, mkPuzzle)
 
+-- Parse a spec string into a (q0, qgoal) pair.
 readSpec :: String -> (NMPuzzle, NMPuzzle)
 readSpec s = (q0, goal) where
   ncols = read (sLines !! 1)
   sLines = lines s
 
 formatOutput :: String -> String -> SearchResult (String, Int) NMPuzzle -> String
-formatOutput fileName methodName (nc, res) = unwords
-  [fileName, methodName, show nc, actionStr res]
+formatOutput fileName methodName (nc, res) =
+  unwords [fileName, methodName, show nc, actionStr res]
   where
     actionStr Nothing     = "No solution found."
     actionStr (Just res)  = intercalate "; " (fst <$> actions res)
 
+-- A search method, taking a goal state for any heuristic included.
 type Method a q =
+  -- Goal state for any heuristic(s).
   q ->
+  -- 𝛿 expansion function.
   (Path a q -> [Path a q]) ->
+  -- Goal predicate.
   (q -> Bool) ->
+  -- q0 (initial state).
   q ->
   SearchResult a q