Skip to content

Towers of Hanoi

November 18, 2008

Next, allow me to present a Haskell version of Towers of Hanoi:

-- hanoi_v1.1.hs
-- Haskell function to compute the Towers of Hanoi problem recursively
-- 
-- Usage: putStr (hanoi_shower (hanoi 1 2 3 n)), or 
--        putStr (hanoi_shower (hanoi 'a' 'b' 'c' n)), 
--        where the first three arguments of hanoi may be polymorphic types
--        (i.e., Chars, Ints, or any other suitable type), and n is the number
--        of discs to move from the source peg to the destination peg
-- 
-- Copyright(c) April 16, 2008, at 14:17, 
-- by Benjamin L. Russell
-- 
-- Update History:
-- 
-- Version 1.0.1
-- Changed program name in comments:
-- "Hanoi.hs" -> "hanoi.hs"
-- 
-- Version 1.0.2
-- Corrected copyright date: April 17 -> April 16
-- 
-- Update History:
-- 
-- Version 1.1
-- Added usage information.
-- October 17, 2008, at 14:45

hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
    | n == 0 = []
    | n == 1 = [(source, dest)]
    | otherwise = hanoi source dest using (n-1)
                  ++ hanoi source using dest 1
                         ++ hanoi using source dest (n-1)

hanoi_shower :: Show a => [(a, a)] -> String
hanoi_shower [] = ""
hanoi_shower ((a, b):moves) = unlines ["Move " ++ show a ++ " to "++ show b ++ "."] ++ hanoi_shower moves

To run the Haskell source code above, simply type:

putStr (hanoi_shower (hanoi 'a' 'b' 'c' 3))

You shall be rewarded with:

Move 'a' to 'c'.
Move 'a' to 'b'.
Move 'c' to 'b'.
Move 'a' to 'c'.
Move 'b' to 'a'.
Move 'b' to 'c'.
Move 'a' to 'c'.

Beautiful, isn’t it?

So much for now.  Until next time….

What is the taste of curried Haskell?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: