Have you ever felt like eating some Haskellian curry on your way to the top of the Towers of Hanoi, but could do without the sugar in the container? Well, here’s how….
Previously, I had posted the following solution to the Towers of Hano problem:
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
However, this function seemed somewhat difficult to understand at a glance, and had the problem that it needed to be called as follows:
putStr (hanoi_shower (hanoi 'a' 'b' 'c' 3))
Thereupon, the function would reward the user with the following results:
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'.
While technically a solution, this function had never seemed an entirely satisfactory counterpart to my earlier Scheme solution (part of the text in the output statement thereof below has been slightly reworded from “… from disc” to “… disc from” here for readability) to the same problem:
(define (hanoi n)
(hanoi-helper 'A 'B 'C n))
(define (hanoi-helper source using destination n)
(cond ((= n 1)
(printf "Moving disc from ~a to ~a.\n" source destination))
(else
(hanoi-helper source destination using (- n 1))
(hanoi-helper source using destination 1)
(hanoi-helper using source destination (- n 1)))))
In particular, the Scheme version could be invoked quite simply as follows:
(hanoi 3)
Thereupon, it would reward the user with the following results:
Moving disc from A to C.
Moving disc from A to B.
Moving disc from C to B.
Moving disc from A to C.
Moving disc from B to A.
Moving disc from B to C.
Moving disc from A to C.
Why not the Haskell version?
At first, not understanding how to use monads correctly, I tried to write the following (incorrect) version, thinking that I could just concatenate the results of the recursive calls into one long string:
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"
hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
| n == 1 = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
| otherwise = hanoiHelper (n-1) source using dest
++ hanoiHelper 1 source dest using
++ hanoiHelper (n-1) using dest source
However, attempting to load this function into WinGhci resulted in the following error message:
Couldn't match expected type `[a]' against inferred type `IO ()'
In the first argument of `(++)', namely
`hanoiHelper (n - 1) source using dest'
In the expression:
hanoiHelper (n - 1) source using dest
++ hanoiHelper 1 source dest using
++
hanoiHelper (n - 1) using dest source
In the definition of `hanoiHelper':
hanoiHelper n source dest using
| n == 1
= putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
| otherwise
= hanoiHelper (n - 1) source using dest
++ hanoiHelper 1 source dest using
++
hanoiHelper (n - 1) using dest source
Since the error message reported that the expected type of hanoiHelper was `[a]’, I then tried modifying the type signature for hanoiHelper accordingly, as follows:
hanoiHelper :: Integer -> String -> String -> String -> [a]
Unfortunately, this only reported in the converse error, thus:
[1 of 1] Compiling Main ( hanoiIncorrect.hs, interpreted )
hanoiIncorrect.hs:9:10:
Couldn't match expected type `IO ()' against inferred type `[a]'
In the expression: hanoiHelper n "A" "B" "C"
In the definition of `hanoi': hanoi n = hanoiHelper n "A" "B" "C"
hanoiIncorrect.hs:13:27:
Couldn't match expected type `[a]' against inferred type `IO ()'
In the expression:
putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
In the definition of `hanoiHelper':
hanoiHelper n source dest using
| n == 1
= putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
| otherwise
= hanoiHelper (n - 1) source using dest
++ hanoiHelper 1 source dest using
++
hanoiHelper (n - 1) using dest source
Failed, modules loaded: none.
Stumped, I came across the following example of code for solving this problem:
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
However, I wasn’t satisfied with this solution, because the syntactic sugar of the do-notation obscured the semantics of what was happening. I liked to have my Haskell curry without sugar.
Then I came across the following explanation of an unsugared monad:
Let’s examine how to desugar a ‘do’ with multiple statements in the following example:
main = do putStr "What is your name?"
putStr "How old are you?"
putStr "Nice day!"
The ‘do’ statement here just joins several IO actions that should be performed sequentially. It’s translated to sequential applications of one of the so-called “binding operators”, namely ‘>>’:
main = (putStr "What is your name?")
>> ( (putStr "How old are you?")
>> (putStr "Nice day!")
)
After comparing the two examples and looking at the nesting of parentheses for a while, I suddenly realized that monads must be some kind of container. Apparently, the monads served to contain something inside that was undesirable in a purely functional environment outside, and the bind (“>>”) notation could be nested to enforce sequencing on the execution order.
After some thought, I came up with the corresponding Haskell solution; viz.:
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C" where
hanoiHelper 1 source dest using = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
hanoiHelper n source dest using = (hanoiHelper (n-1) source using dest)
>> ( (hanoiHelper 1 source dest using)
>> (hanoiHelper (n-1) using dest source)
)
This function type-checked correctly, and could be summoned as follows:
hanoi 3
Thereupon, similarly to its Scheme counterpart, it would now reward the user as follows:
Move disc from A to B.
Move disc from A to C.
Move disc from B to C.
Move disc from A to B.
Move disc from C to A.
Move disc from C to B.
Move disc from A to B.
For those who prefer do-notation, here is the same function sweetened with syntactic sugar:
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C" where
hanoiHelper 1 source dest using = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
hanoiHelper n source dest using = do
hanoiHelper (n-1) source using dest
hanoiHelper 1 source dest using
hanoiHelper (n-1) using dest source
Although almost a direct counterpart to the corresponding Scheme version, it was still not structured similarly as a main function and a helper function; I wanted to divide it correspondingly.
Eventually, I came up with the following corresponding solution, which also used a helper function:
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"
hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
| n == 1 = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
| otherwise = (hanoiHelper (n-1) source using dest)
>> ( (hanoiHelper 1 source dest using)
>> (hanoiHelper (n-1) using dest source)
)
As a bonus, during my research, I chanced upon the following explanation of the ‘$’ operator:
This is hopefully something worth sharing about Haskell. The $ operator.
simpleHTTP $ buildRequest req_text
simpleHTTP ( buildRequest req_text )
It is an application operator, it takes a function and an argument, and … applies the function to the argument. It’s purpose is to save typing parentheses. It is all about operator precedence.
head . words $ config_file_contents
( head . words ) config_file_contents
Application, f a (f applies to a), binds stronger than any operator. If it was an operator, think about multiplication operator which people often omit, it would have precedence set to 10. $ has precedence set to 0, which is the lowest value of precedence possible.
The . is my another favourite. (f . g) a == f (g a) it set to 9, and therefore binds almost as strong as application.
listActions :: String -> [Action]
listActions = filter notDone . map actionFromMap . parseJSON
Feeling richer with the ‘$’, I rewrote my function, listed below complete with comments and a copyleft disclaimer, to suit my mood accordingly:
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"
hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
| n == 1 = putStrLn $ "Move disc from " ++ source ++ " to " ++ dest ++ "."
| otherwise = (hanoiHelper (n-1) source using dest)
>> ( (hanoiHelper 1 source dest using)
>> (hanoiHelper (n-1) using dest source)
)
Now I am on a diet with fewer parentheses, but with more ‘$’ in my pocket.
P.S.
One commentator, augustss, has been kind enough to point out that my version of hanoi can be rewritten to be less IO-based, and more functional. Per augustss’s suggestion, I have rewritten hanoi.hs as follows:
hanoi :: Integer -> IO ()
hanoi = putStr . hanoiShower . hanoiMover 'a' 'b' 'c'
hanoiMover :: a -> a -> a -> Integer -> [(a, a)]
hanoiMover source using dest n
| n == 0 = []
| n == 1 = [(source, dest)]
| otherwise = hanoiMover source dest using (n-1)
++ hanoiMover source using dest 1
++ hanoiMover using source dest (n-1)
This version is essentially a higher-order functional composition of my original hanoi.hs mentioned at the beginning of this blog post.
Thanks to augustss for pointing out this observation; I’ll try to write my functions in a more functional style hereinafter.
P.P.S.
Another commentator, Jedai, has been generous enough to indicate that my version of hanoi can be rewritten entirely without parentheses. Per Jedai’s suggestion, I have rewritten hanoi.hs as follows:
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"
hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
| n == 1 = putStrLn $ "Move disc from " ++ source ++ " to " ++ dest ++ "."
| otherwise = hanoiHelper (n-1) source using dest
>> hanoiHelper 1 source dest using
>> hanoiHelper (n-1) using dest source
Monadically Speaking: Adventures in Programming Language Theory 
Note that if you search to avoid orgy of parentheses, you can rewrite your latest expression :
hanoiHelper (n-1) source using dest
>> hanoiHelper 1 source dest using
>> hanoiHelper (n-1) using dest source
since as you said application binds tighter than any operator (and the monad laws specify that “(a >> b) >> c” is the same as “a >> (b >> c)” so you don’t even need to remember the associativity of (>>)).
This is backwards. You have gone from a nice non-IO version of the function, to one where the IO is spread all over. That’s not the way to do it. You want to separate computation from IO when you program in a functional way, so the first one was the right way.
Just rename hanoi to hanoiMover, and then define
hanoi = putStr . hanoi_shower . hanoiMover ‘a’ ‘b’ ‘c’
And you have you simple top level function.
augustss:
You’re right; I probably should have noticed that, since it was a simple example of higher-order functional composition.
Accordingly, as you suggested, I have renamed hanoi to hanoiMover and added your version of hanoi. In addition, I have renamed hanoi_shower to hanoiShower (to comply with Haskellian functional naming conventions), and added a type signature for your version of hanoi, viz.:
Thank you for your suggestion. Do you prefer this version?
Jedai,
Indeed.
Accordingly, I have written an alternate version of hanoi, hanoiHelperRichSansParens.hs; viz.:
Thank you for your comment. What do you think?
I think the final product is fabulous. I just wish I could follow what’s happening. I get lost after the first line after “otherwise.” I just started learning Haskell and I’m not a programmer. Can you walk us through what Haskell is doing?
Do you mean the “hanoiHelper … >> hanoiHelper … >> hanoiHelper …” or the “hanoiMover … ++ hanoiMover … ++ hanoiMover …” version ?
I mean the very last version.
hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n “A” “B” “C”
hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
| n == 1 = putStrLn $ “Move disc from ” ++ source ++ ” to ” ++ dest ++ “.”
| otherwise = hanoiHelper (n-1) source using dest
>> hanoiHelper 1 source dest using
>> hanoiHelper (n-1) using dest source
Hey there terrific blog! Does running a blog such as this require a lot of work? I’ve absolutely no expertise in computer programming however I was hoping to start my own blog in the near future. Anyways, if you have any recommendations or tips for new blog owners please share. I know this is off subject nevertheless I just needed to ask. Thank you!|