Towers of Hanoi: Difference between revisions

==[[Haskell]]==

[[Category:Haskell]]

Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c:

hanoi :: Integer -> a -> a -> a -> [(a, a)]

hanoi = hanoi' [] where

hanoi' k 0 _ _ _ = k

hanoi' k n a b c = hanoi' ((a,b):(hanoi' k (n-1) c b a)) (n-1) a c b

Here hanoi' uses an accumulator argument for the "following" moves.

One can use this function to produce output, just like the other programs:

hanoiIO n a b c = foldl (>>) (return ()) $ map f $ hanoi n a b c where

f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y

Or, instead one can of course also program imperatively, using the IO monad directly:

hanoiM :: Integer -> IO ()

hanoiM n = hanoiM' n 1 2 3 where

hanoiM' 0 a b c = return ()

hanoiM' n a b c = do

hanoiM' (n-1) a c b

putStrLn $ "Move " ++ show a ++ " to " ++ show b

hanoiM' (n-1) c b a