Ok; I rewrote my recursive version of hanoi,
preserving my semantics (i.e., working for lists of
length 1 or more, rather than 0 or more, to start
with) in a more Haskell-idiomatic manner; viz:
hanoi_general_recursive.hs:
hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
| 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 [(a, b)] = unlines ["Move " ++ show a ++
" to "++ show b ++ "."]
hanoi_shower ((a, b):moves) = unlines ["Move " ++ show
a ++ " to "++ show b ++ "."] ++ hanoi_shower moves
(I wanted to start out with lists of length 1 as a
base case before extending the base case to lists of
length 0 because Luke Palmer had already solved it for
0, and I didn't want just to copy his solution--I
can't learn anything if I just do that.)
In WinHugs:
Main> :load hanoi_general_recursive.hs
Main> putStr (hanoi_shower (hanoi 'a' 'b' 'c' 2))
Move 'a' to 'b'.
Move 'a' to 'c'.
Move 'b' to 'c'.
Main> putStr (hanoi_shower (hanoi 'a' 'b' 'c' 1))
Move 'a' to 'c'.
Main> putStr (hanoi_shower (hanoi 1 2 3 2))
Move 1 to 2.
Move 1 to 3.
Move 2 to 3.
Main> putStr (hanoi_shower (hanoi 1 2 3 1))
Move 1 to 3.
Ok; it works now.
Now that I have successfully created a recursive
version that preserves my original semantics, it is
time to extend the base case to handle lists of length
0.
(Notice that I added a base case of n == 0 to hanoi
itself as well, in addition to hanoi_shower; leaving
this out in hanoi results in an error of "ERROR - C
stack overflow" on an argument of n == 0 discs:)
hanoi_general_recursive_base_0.hs:
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
Now, let's sit back and watch the fun in WinHugs:
Main> :load hanoi_general_recursive_base_0.hs
Main> putStr (hanoi_shower (hanoi 'a' 'b' 'c' 2))
Move 'a' to 'b'.
Move 'a' to 'c'.
Move 'b' to 'c'.
Main> putStr (hanoi_shower (hanoi 'a' 'b' 'c' 0))
Main> putStr (hanoi_shower (hanoi 1 2 3 2))
Move 1 to 2.
Move 1 to 3.
Move 2 to 3.
Main> putStr (hanoi_shower (hanoi 1 2 3 0))
Great!
Just for reference, here's the code for the other
versions for comparison:
hanoi_general_list_comprehension_unwords.hs [Note:
This version adds an extra space before the final '.'
on each line.]:
hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
| 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 moves = unlines [unwords ["Move", show a,
"to", show b, "."] | (a, b) <- moves]
--
hanoi_general_list_comprehension_unlines.hs:
hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
| 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 moves = unlines ["Move " ++ show a ++ "
to "++ show b ++ "." | (a, b) <- moves]
--
hanoi_general_map_unlines.hs:
hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
| 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 moves = unlines (map move moves)
where move (a, b) = "Move " ++
show a ++ " to "++ show b ++ "."
--
hanoi_general_recursive.hs [Note: This version only
works for lists of length 1 or more.]:
hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
| 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 [(a, b)] = unlines ["Move " ++ show a ++
" to "++ show b ++ "."]
hanoi_shower ((a, b):moves) = unlines ["Move " ++ show
a ++ " to "++ show b ++ "."] ++ hanoi_shower moves
--
hanoi_general_recursive_base_0.hs [Note: This program
is just the program contained in the file
hanoi_general_recursive.hs, but extended to process
lists of length 0 or more.]:
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
--
Thanks for all your help! Thanks especially to
Tillmann Rendel, Neil Mitchell, and Luke Palmer for
their sample code, to Brandon S. Allbery KF8NH for his
acute questions, to Brent Yorgey for pointing out that
hanoi_helper was superfluous, and to Abhay Parvate for
his discussion of the meaning of Neil Mitchell's
"mapM_ putStrLn == putStr . unlines" (I hope I didn't
miss anybody).
Next step: to figure out how to write hanoi in CPS.
More on this later....
Benjamin L. Russell
--- Tillmann Rendel
Benjamin L. Russel wrote:
hanoi_shower ((a, b) : moves) | null moves = ... | otherwise == ...
Luke Palmer wrote:
More idiomatic pedantry: the way you will see most Haskellers write this style of function is by pattern matching rather than guards:
hanoi_shower [] = ... hanoi_shower ((a,b):moves) = ...
These two versions are semantically different! Benjamin's versions works for lists of length 1 or more, Luke's version works for lists of length 0 or more.
Luke's version looks like a typical Haskell solution, which would be expressed in lispy syntax like this:
(define hanoi_shower (lambda (xs) (cond ((null xs) (...)) (true, (let ((a, (first (first xs))) (b, (rest (first xs))) (moves, (rest xs))) (...)))))
The pattern matching in Haskell takes care of both the cond and the let, there's no need for guards or to actually call null or any selector functions. A nice exercise may be to implement the map function using primitive recursion.
Tillmann _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe