[Haskell-beginners] Translating imperative algorithms to Haskell

[Stephen Tetley]

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

Stephen

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
  where
    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.)
>