|
Alright! now we're finally anealling us picnic! here's our main "loop": |
let anneal_tick :: MotionFunction a -> TransitionProbabilityFunction -> EnergyFunction a -> Float -> (StdGen,a) -> (StdGen,a)
anneal_tick mf tpf ef t (r,p) = let (r2,p2) = mf r p
(n ,r3) = random r2
in (r3,
if n < tpf (ef p) (ef p2) t
then p2
else p)
let anneal :: EnergyFunction a -> MotionFunction a -> TransitionProbabilityFunction -> TemperatureFunction -> Int -> StdGen -> a -> a
anneal ef mf tpf tf m r s = snd $ foldl' (flip (anneal_tick mf tpf ef)) (r,s) (map (tf m) [0..m])
random_generator <- getStdGen
putStr "starting annealing... "
putStr "number of annealing steps: "
print annealing_time
let ideal_placement = anneal
(picnicEnergy sitting)
(picnicMotion walking)
picnicTransitionalProbability
picnicTemperature
annealing_time
random_generator
starting_placement
writeFile "tut9.svg" $ writePolygons $ map (similarityLine ideal_placement) sitting
putStr "Done!\nfinal energy: "
print $ picnicEnergy sitting ideal_placement
putStr "final temperature: "
print $ picnicTemperature 0 annealing_time
Now, if we run our the completed program, we'll calculate ourselves low energy, crystallized picnic exactly as we wanted: (be patient it'll might take 5 minutes for a result...) |
> runHaskell tutorial.hs Hello World! Let's have a picnic! Number of people coming: 200 starting energy: 16010 starting temperature: 0.33689734 starting annealing... number of annealing steps: 500 Done! final energy: 15010 final temperature: 0.0
|
Now let's look at our crowning achievement, tut9.svg- Check out the bluer color, compared to the previous picture, of an annealed picnic: |
|
Here's what it looks like with a much longer annealing time: |
|
WooHoo! Now let's figure out what this final piece of code is all about... First, we have the anneal_tick function, which handles a single moment in time for our annealing... It needs to be handed three of the four annealing functions... Instead of the fourth one, TemperatureFunction, it is handed just the temperature at that moment (the Float), since at any given time the temperature is just a single number. The last thing passed into this function is the current placement of our "atoms", as well as a random number source, StdGen... In Haskell, you can't just pull random numbers out of "thin air" as you can in almost any other programming language known to mankind... Remember, doing unpredictable stuff that isn't specified explicitly in a function's type signature is a Haskell no-no... The main "loop" of our program is in the function anneal... I put "loop" in quotes because Haskellers don't use loops, they use folds... A fold is kind of like a map function: Whereas map returns a list created by thrashing through a starting list and applying a function to each member, folds return a single item, created by folding together all the items in a list into a single result value- There are two main folding functions, foldl and foldr, which fold from the left and right end of the starting list, respectively. To learn more about the different types of folds, check the HaskellWiki. Finally, we code generates the ideal_placement by glueing together all our building block functions to generate our final result- And that's the end of our tutorial program! Of course, the total number of annealing steps we're doing (500) is not enough for a very good annealing- You'd need to run a few million steps and use GHC to compile the program to machine language to get an optimal result- Here's how you'd compile it: |
ghc -O2 -fglasgow-exts -optc-march=pentium4 -optc-O2 -optc-mfpmath=sse -optc-msse2 --make picnic.hs
|
Once again, this shows how haskell's typing system let's us modularize like a charm: Note that the word "picnic" or anything else picnic-related does not appear in either the anneal_tick or the anneal function... This code, which is the very heart of this program, is completely unpolluted by our problem domain: If you were a biochemist simulating artery clot annealing, you could use this exact same code to run your simulations. If you're a nuclear chemist simulating isotope doodads in a hydrogen bomb, you could use this function. (Note to nuclear chemists- If you're reading this tutorial, and copy/pasting my code, then we're in big trouble...) As this example shows, Haskell's powerful typing system allows us to prevent leakage from different sections of code in ways almost no other language can match- Whether you're worried about leaking randomness, IO operations, picnic references, etc. etc. Haskell's type system offers the ultimate in "code leakage" protection! In conclusion of my tutorial, I want to wander off a bit into the realm of armchair programming philosophy...  I, like many others involved in Haskell, believe very strongly that the central ideas in the Haskell language represent the future of programming- It's seems pretty inevitable that Haskell-like will have a huge impact on the future... But, alas, Haskell still has one unavoidable weakness that might be the fly in the ointment of the inevitable Haskell utopia of the future- We can see it clearly in the code above where this weakness comes in to play... Several times in this tutorial I have talked about how easy it is to take algorithms or math concepts and effortlessly translate them into elegant types and functions using the elegance of the Haskell syntax and typing system. One set of functions, however, were not so easy to translate: the anneal_tick and anneal functions. The source of these functions was the pseudo-code in the wikipedia article we've been using... They're just a wee-bit more obfuscated than one would really want, in my opinion. It's only a little bit obfuscated, but still makes me unhappy... The reason for this is that this pseudo code is simulating a physical world that changes slightly over time: This is a fundamental property of our universe: Things only change a little bit from one moment to the next. A great description of this noteworthy property of our world can be found in this Whitepaper which discusses a pretty cool take on A.I. that is being explored by Jeff Hawkins and Dileep George at a company named Numenta- Their software is all about how our minds exploit this property in achieving intelligence... Because the physical world changes only slightly from moment to moment, it means that languages that can comfortably mutate large data structures in targeted ways will always have a role to play in real-world software- The "real world" usually just doesn't work the way Haskell, and other functional languages would prefer it did: Haskell preferred that at every moment in time, a "new universe" would look at the "old universe" and would rebuild itself, from scratch, from what it saw in the past, with radical changes happening all the time. Despite its many advantages, I humbly suggest, therefore, that in the future there will continue to be a rift between the "imperative" and "functional" camps of programming, until someone comes up with a truly robust way of uniting these two camps- And I think that some profound programming discoveries still need to be made in the future before this problem is really resolved- I get the feeling it's just not good enough to wave at the problem and say "Monads". |