[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
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.)
>
More information about the Beginners
mailing list