StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The best way to express this sort of iterative procedure in Haskell is as an <em>infinite list</em> of each successive result. Piecing together your four steps yields a notion of a function from a solution to a different (better) solution; all you need to do is apply this infinitely many times. The user of your function can then use any list function to get the answer: <code>solve s0 !! numIterations</code>, or <code>find stoppingCondition $ solve s0</code>, or whatever you want.</p> <p>In order to get here, let's write out the types for each of these functions.</p> <ol> <li><code>moves :: Solution -> [Move]</code><br> Given a possible solution, figure out the possible changes you can make.</li> <li><code>value :: Solution -> Move -> Double</code><br> Given a solution and a move, evaluate it and record that value as some real number.</li> <li><code>choose :: Solution -> [Move] -> Move</code><br> Given a solution and a list of moves, pick the best one.</li> <li><code>apply :: Solution -> Move -> Solution</code><br> Given a move, apply it to an existing solution to get a new one.</li> </ol> <p>You want to write a function with a type something like <code>solve :: Solution -> (Solution -> Bool) -> Solution</code> which takes an initial solution and a stopping condition to execute your algorithm.</p> <p>Instead, let's make this an infinite list; this means that you'll just remove the predicate and have <code>Solution -> [Solution]</code>.</p> <pre><code>import Data.Ord import Data.List -- moves, value, and apply are domain-specific choose :: Solution -> [Move] -> Move choose s ms = maximumBy (comparing $ value s) ms solve :: Solution -> [Solution] solve = iterate $ \s -> apply s . choose s $ moves s </code></pre> <p>Here, the key is <code>iterate :: (a -> a) -> a -> [a]</code>, which repeatedly applies a function to a value and gives you the results—exactly the description of your algorithm.</p> <p>However, the way I'd really write this would be the following:</p> <pre><code>import Data.Ord import Data.List solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s] solve moves value apply = iterate step where step s = apply s . choose s $ moves s choose s = maximumBy (comparing $ value s) </code></pre> <p>The advantage of this is that you can reuse this same generic structure for <em>any</em> problem domain. All you need to do is to provide the <code>moves</code>, <code>value</code>, and <code>apply</code> functions! And depending on my mood, I might rewrite that as this:</p> <pre><code>import Control.Applicative import Data.Ord import Data.List solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s] solve moves value apply = iterate step where step = (.) <$> apply <*> choose <*> moves choose = maximumBy . comparing . value </code></pre> <p>Here, we use applicative notation to say that we're effectively just doing <code>(.) apply choose moves</code> (which is just <code>apply . choose $ moves</code>) in a context where each of those functions is implicitly passed a parameter <code>s</code> (the reader applicative). If we really wanted to tersify things, we could write</p> <pre><code>import Control.Applicative import Data.Ord import Data.List solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s] solve moves value apply = iterate $ (.) <$> apply <*> maximumBy . comparing . value <*> moves </code></pre> <p>Any of these snippets will do exactly what you need. (Proviso: there are no effects/monads in any of your functions, so randomness is out. You make this monadic easily, though.)</p> <hr> <p>Just for kicks, though, let's think about the <code>State</code> monad. This represents a computation with some sort of environment, so that <code>State s a</code> is isomorphic to <code>s -> (a,s)</code>—something which can see the state and potentially update it. Here, all the <code>Solution -></code>s on the left of your function signatures would disappear, as would the <code>-> Solution</code>s on the right. That would leave you with</p> <ol> <li><code>moves :: State Solution [Move]</code></li> <li><code>value :: Move -> State Solution Double</code></li> <li><code>choose :: [Move] -> State Solution Move</code></li> <li><code>apply :: Move -> State Solution ()</code></li> </ol> <p>This means that you would have some monadic action <code>step</code>:</p> <pre><code>import Control.Applicative import Control.Monad.State import Data.Ord import Data.List choose :: [Move] -> State Solution Move choose = let val m = do v <- value m return (m,v) in fst . maximumBy (comparing snd) <$> mapM val ms step :: State Solution () step = apply =<< choose =<< moves </code></pre> <p>You could make this more point-free, or make it polymorphic just as above, but I won't do that here. The point is that once you have <code>step</code>, you can generate answers with <code>runState . last $ replicateM_ numIterations step</code>, or given a <code>whileM</code> function, <code>runState $ whileM (stoppingCondition :: State Solution Bool) step</code>. Again, the user can decide how to stop it. Your <code>moves</code> and <code>value</code> functions would probably query the state with <code>get :: State s s</code>; <code>apply</code> would probably use <code>modify :: (s -> s) -> State s ()</code> to tweak the state without needing to pull it back out. You can see the similarity with the structure from above in these types; and in fact, you can see that structure in the definition of <code>step</code>, as well. Each one says "string together <code>apply</code>, <code>choose</code>/<code>value</code>, and <code>moves</code>", which is the definition of your algorithm.</p> <hr> <p>The take-home message from both of these is that you want to avoid explicit loops/recursion, as you so rightly realized. If you think about this algorithm imperatively, then the <code>State</code> monad seems like a natural structure, as it hides exactly those imperative features you were thinking of. However, it has downsides: for instance, everything has become monadic, and—worst of all—functions other than <code>apply</code> are able to change the saved solution. If you instead imagine this algorithm as producing a <em>new</em> result each time, you get the notion of <code>step :: Solution -> Solution</code>, and from there you can use <code>iterate</code> to get a well-behaved infinite list.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload