[Haskell-beginners] Translating imperative algorithms to Haskell

Stephen Tetley stephen.tetley at gmail.com
Sun Feb 21 15:07:29 EST 2010

Hi Stephen

I'd be tempted to make the 'fold' problem specific (especially as I'm
not sure I'd call a fold a 'fold' if it breaks early).

Here's what I came up with though it seems to have a bug somewhere.
The Step and Window types might benefit strictness annos in real life.
The imperative version on Wikipedia is far clearer than either mine or
yours though.

Best wishes


data Tree a = Node a [Tree a]
            | Leaf a
  deriving (Eq,Show)

data Step a = NewWindow  a a
            | BetaCutoff a

data Window a = Win a a

runCutoff :: [(Window a -> Step a)] -> Window a -> a
runCutoff []     (Win alp _) = alp
runCutoff (f:fs) ab          = case f ab of
    NewWindow  a b -> runCutoff fs (Win a b)
    BetaCutoff a   -> a

cutoff :: a -> (a -> Bool) -> (a -> Step a) -> Step a
cutoff a test elsek | test a    = BetaCutoff a
                    | otherwise = elsek a

negascout :: Tree Int -> Int -> (Window Int) -> Int
negascout (Leaf h)    _ _             = h
negascout (Node h _ ) d _             | d <= 0 = h
negascout (Node _ ns) d w@(Win _ b0)  = runCutoff (map scout ns) w
    scout _    (Win a _)   | a >= b0 = BetaCutoff a
    scout node (Win a b)   = let a' = max a (nega node (-b) (-a))
                             in cutoff a' (>= b0) (\x -> full node (Win x b))

    full node (Win a b) = let a' = nega node (-b0) (-a)
                          in cutoff a' (>= b) (\x -> NewWindow x (x+1))

    nega node x y  = negate $ negascout node (d-1) (Win x y)

On 21 February 2010 19:29, Stephen Blackheath [to Haskell-Beginners]
<mutilating.cauliflowers.stephen at blacksapphire.com> wrote:
> All,
> And... A slight variation that shadows alpha (which some people don't
> like, but I think it's a great technique) and thereby avoids the mistake
> I made in my previous three versions where I forgot a ' in -negascout ch
> (depth-1) (-beta) (-alpha').  (You have to watch that in Haskell.)

More information about the Beginners mailing list