<p dir="ltr">Please run with a profiler<br>
Programmers are notoriously bad at guessing where the bottlenecks are<br>
Unless looking for beer 😃</p>
<p dir="ltr">For strictness there is the bang notation ! 😃</p>
<p dir="ltr">--<br>
--</p>
<p dir="ltr">Sent from an expensive device which will be obsolete in a few months! :D</p>
<p dir="ltr">Casey<br>
    </p>
<div class="gmail_extra"><br><div class="gmail_quote">On Sep 11, 2016 3:49 PM, "Dennis Raddle" <<a href="mailto:dennis.raddle@gmail.com">dennis.raddle@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I'm a Haskell semi-beginner, and I've implemented a crude Monte Carlo search optimization algorithm, and I want to know how to use strict evaluation to prevent it from consuming too much memory. <div><br></div><div>I am willing to learn new things to do this---if you want to point me in the right direction and maybe give some references, I'll take it from there. However, if there is something simple that can take care of the whole problem, please let me know.</div><div><br></div><div>I have not run this with the profiler so I don't actually know precisely what it is doing now. I have not run out of memory using it in small cases, but I hope to use it on much larger cases.</div><div><br></div><div>Here is the code so far:</div><div><br></div><div><br></div><div><font size="1"><br></font></div><div><font face="monospace, monospace"><div><font size="1">import qualified Data.List as L</font></div><div><font size="1">import Control.Monad</font></div><div><span style="font-size:x-small">import Data.Function</span><br></div><div><br></div><div><font size="1"><br></font></div><div><font size="1">-- Suppose that we do backtracking search for an optimal arrangement of</font></div><div><font size="1">-- elements in some kind of "structure". The "structure" is built one step at</font></div><div><font size="1">-- a time.</font></div><div><font size="1">--</font></div><div><font size="1">-- An example would be searching for an optimal arrangement of furniture. The</font></div><div><font size="1">-- structure is a represenation of the room and all items that have been</font></div><div><font size="1">-- placed in it so far. We could list the options (or "steps") available to us</font></div><div><font size="1">-- at any point in building the structure, that is a list of furniture items</font></div><div><font size="1">-- and locations.</font></div><div><font size="1">--</font></div><div><font size="1">-- We have the notion that the structure, at some point in adding steps,</font></div><div><font size="1">-- becomes complete. We have an evaluation function providing a "goodness</font></div><div><font size="1">-- score" on either a partially built or complete structure.</font></div><div><font size="1">--</font></div><div><font size="1">-- The search will optimize the goodness score over all possible complete</font></div><div><font size="1">-- structures. (Or perhaps with Monte Carlo search, an approximate optimal</font></div><div><font size="1">-- value.)</font></div><div><font size="1">--</font></div><div><font size="1">-- Class Opt (for "optimization") defines a structure type "struct" and a step</font></div><div><font size="1">-- type "step".</font></div><div><font size="1"><br></font></div><div><font size="1">class Opt struct step | struct -> step where</font></div><div><font size="1">  -- number of steps chosen so far in current state of 'struct':</font></div><div><font size="1">  oSize  :: struct -> Int</font></div><div><font size="1">  -- list all the available steps to choose next. If this list is null, then</font></div><div><font size="1">  -- the structure is complete.</font></div><div><font size="1">  oList  :: struct -> [step]</font></div><div><font size="1">  -- apply a step to the structure to create a new structure:</font></div><div><font size="1">  oApply :: struct -> step -> struct</font></div><div><font size="1">  -- evaluate the "goodness" of the current state of a structure. Higher is</font></div><div><font size="1">  -- better.</font></div><div><font size="1">  oEval  :: struct -> Double</font></div><div><font size="1"><br></font></div><div><font size="1"><br></font></div><div><br></div><div><font size="1">-- Implement a kind of Monte Carlo search. (I have a vague idea of the</font></div><div><font size="1">-- literature on Monte Carlo; this algorithm is my guess at something that</font></div><div><font size="1">-- does the job). We work in a state monad of class</font></div><div><font size="1">-- "RandMonad" which holds the StdGen data and provides several methods for</font></div><div><font size="1">-- accessing it. The only method we need from RandMonad is</font></div><div><font size="1">--</font></div><div><font size="1">--    rChooseItem :: RandMonad m => [a] -> m a</font></div><div><font size="1">--</font></div><div><font size="1">-- which chooses a random item from a non-null list.</font></div><div><font size="1">--</font></div><div><font size="1">-- The basic algorithm is this: at each point in building the structure, we</font></div><div><font size="1">-- have a structure S and a list of next steps step_list. We apply each step</font></div><div><font size="1">-- in step_list to S, in turn. After applying a step x to S, call the result</font></div><div><font size="1">-- S_x. We evaluate the "monte carlo fitness" of S_x by making random</font></div><div><font size="1">-- completions of it---that is, choosing a bunch of additional steps</font></div><div><font size="1">-- randomly---doing 'nExper' completions (nExper might be 1000 to 10000). The</font></div><div><font size="1">-- fitness as measured by oEval of the very best random completion becomes</font></div><div><font size="1">-- the "monte carlo fitness" of S_x. We then choose the step from step_list,</font></div><div><font size="1">-- x, that maximizes the "monte carlo fitness" of S_x.</font></div><div><font size="1">--</font></div><div><font size="1">-- We then repeat this process until S is complete.</font></div><div><font size="1"><br></font></div><div><font size="1"><br></font></div><div><font size="1">-- Function monteCarlo will take a partially complete structure, and optimize</font></div><div><font size="1">-- it over an investigation of 'nExper' possible "completions".</font></div><div><span style="font-size:x-small"><br></span></div><div><span style="font-size:x-small">monteCarlo :: (RandMonad r, Opt a b) => Int -> a -> r a</span><br></div><div><font size="1"><div>monteCarlo nExper struct = case oList struct of</div><div>  -- If structure is complete, then it is its own optimization.</div><div>  []    -> return struct</div><div>  -- Otherwise find optimal step according to "monte carlo fitness" and</div><div>  -- recursively call 'monteCarlo'</div><div>  steps -> do</div><div>    let doStep step = do</div><div>          let newStruct = oApply struct step</div><div>          score <- monteCarloEval nExper newStruct</div><div>          return (score,newStruct)</div><div>    (_,winner) <- L.maximumBy (compare `on` fst) `liftM` mapM doStep steps</div><div>    monteCarlo nExper winner</div><div><br></div><div><br></div></font></div><div><font size="1"><br></font></div><div><font size="1">-- monteCarloEval</font></div><div><font size="1">--</font></div><div><font size="1">-- Evaluate the "monte carlo fitness" of a structure 'struct' by completing it</font></div><div><font size="1">-- in nExper random ways (that is, make all remaining choices in purely random</font></div><div><font size="1">-- way) and finding the maximum value of the evaluated final state among all</font></div><div><font size="1">-- nExper ways.</font></div><div><font size="1">--</font></div><div><font size="1">monteCarloEval :: (RandMonad r, Opt a b) => Int -> a -> r Double</font></div><div><font size="1">monteCarloEval nExper struct = case oList struct of</font></div><div><font size="1">  [] -> return $ oEval struct</font></div><div><font size="1">  _  -> do</font></div><div><font size="1">    scores <- replicateM nExper (randomComplete struct)</font></div><div><font size="1">    return . maximum . map oEval $ scores</font></div><div><font size="1"><br></font></div><div><font size="1"><br></font></div><div><font size="1">-- Make random choices of steps until a structure 's' is complete.</font></div><div><font size="1">randomComplete :: (RandMonad r, Opt a b) => a -> r a</font></div><div><font size="1">randomComplete s = case oList s of</font></div><div><font size="1">  []    -> return s</font></div><div><font size="1">  steps -> rChooseItem steps >>= (randomComplete . oApply s)</font></div><div><br></div></font></div></div>
<br>______________________________<wbr>_________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div></div>