Colin Paul Adams wrote:
I want to implement the negascout algorithm for the game I'm writing.
Wikipedia gives the algorithm in imperative terms:
http://en.wikipedia.org/wiki/Negascout
I've tried to translate this into Haskell. I'm not sure if I'm going about it the right way, and if I am, if I've done it correctly.
Variable names like alpha'' can be seen as an indication that a function is too big and/or monolithic. It's worth keeping in mind the lesson of the lambda calculus: that a local variable is just a function in disguise. To exploit that, you can replace definitions and uses of variables like alpha' and alpha'' with calls to functions. Wherever you have something like: let alpha' = <new value for alpha> in <body> ...try changing it to something like: foo <new value for alpha> ... where foo alpha = <body> Instead of a monolithic deeply-nested conditional expression, this will naturally lead to a set of small functions which call other small functions. As Toby Hutton said, you should also factor out any repetition into functions. One advantage of defining small functions like this is that you can also take advantage of guard syntax, which used appropriately in Haskell can be cleaner and more readable than either 'case' or 'if'. For example, to deal with the following pseudocode: a := -negascout (child, depth-1, -b, -alpha) if a > alpha alpha := a You could write a function such as: newAlpha a | a > alpha = a | otherwise = alpha Note this function depends on 'alpha'. To avoid having to pass extra parameters around all over the place, simply define this function using a 'where' clause, at the appropriate scope level so that the 'alpha' it needs is in scope. In your example, it would probably be defined in your negascout' function, something like this: negascout' node depth beta' alpha beta rest = ... where newAlpha a | a > alpha = a | otherwise = alpha Note that newAlpha needs to be called with the result of a call to negascout. While we're about it, notice that both of the recursive calls to negascout use the same first two arguments, so just for readability, we can define this: search a b = -negascout child (depth-1) (-b) (-a) The pseudocode above can now be (mostly) replaced with a call 'newAlpha', as follows: newAlpha (search alpha b) However, this doesn't deal with what happens to the result of the call to newAlpha. In the imperative pseudocode, alpha is mutated. For a functional version, you can just repeat the above strategy: define a function which takes an argument alpha, and call that function with the new value for alpha, i.e. the result of the call to newAlpha, so something like: foo (newAlpha $ search alpha b) The foo function will implement the remainder of the body of the foreach loop from the pseudocode. (Coming up with a better name than 'foo' is left as an exercise...) I tried this and the result was 13-16 lines, depending how you count, of code that is of similarly high level to the original pseudocode. Anton