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 <rendel@daimi.au.dk> wrote:
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