Skip to content

Climbing the Towers of Hanoi with Haskell-style Curry from a Monadic Container (While Sparing the Sugar!)

April 13, 2009

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:

$ 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:

-- hanoiHelpedRich.hs
-- Haskell function to compute the Towers of Hanoi problem recursively, 
-- using a helper function and the '$' operator to take a function and 
-- an argument, and accordingly save typing parentheses
--
-- Copyright(C) April 13, 2009, at 19:56, 
-- by Benjamin L. Russell
-- 
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

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:

-- hanoiMover.hs
-- Originally based on hanoi_v1.1.hs, a Haskell function to compute
-- the Towers of Hanoi problem recursively, by Benjamin L. Russell,
-- dated April 16, 2008, at 14:17; 
-- revised based on a comment from augustss, dated April 18, 2009, at
-- 17:38, (see
-- http://dekudekuplex.wordpress.ecom/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/#comment-58),
-- in response to my blog post "Climbing the Towers of Hanoi with
-- Haskell-style Curry from a Monadic Container (While Sparing the 
-- Sugar!)," dated April 13, 2009, at 19:59 (see
-- http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/)
--
-- Copyright(C) April 20, 2009, at 18:38, 
-- by Benjamin L. Russell
-- 
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

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:

-- hanoiHelperRichSansParens.hs
-- Haskell function to compute the Towers of Hanoi problem recursively, 
-- using a helper function and the '$' operator to take a function and 
-- an argument, and accordingly save typing parentheses, rewritten
-- without parentheses
-- 
-- Originally based on hanoiHelperRich.hs, a Haskell function to compute
-- the Towers of Hanoi problem recursively, by Benjamin L. Russell,
-- dated April 13, 2009, at 20:13; 
-- revised based on a comment from Jedai, dated April 18, 2009, at
-- 03:21, (see http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/#comment-57),
-- in response to my blog post "Climbing the Towers of Hanoi with
-- Haskell-style Curry from a Monadic Container (While Sparing the 
-- Sugar!)," dated April 13, 2009, at 19:59 (see
-- http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/)
--
-- Copyright(C) April 20, 2009, at 19:25, 
-- by Benjamin L. Russell
-- 
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

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
About these ads
8 Comments
  1. Jedai permalink

    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 (>>)).

  2. augustss permalink

    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.:

      – hanoiMover.hs
      — Originally based on hanoi_v1.1.hs, a Haskell function to compute
      — the Towers of Hanoi problem recursively, by Benjamin L. Russell,
      — dated April 16, 2008, at 14:17;
      — revised based on a comment from augustss, dated April 18, 2009, at
      — 17:38, (see
      http://dekudekuplex.wordpress.ecom/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/#comment-58),
      — in response to my blog post “Climbing the Towers of Hanoi with
      — Haskell-style Curry from a Monadic Container (While Sparing the
      — Sugar!),” dated April 13, 2009, at 19:59 (see
      http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/)

      — Copyright(C) April 20, 2009, at 18:38,
      — by Benjamin L. Russell

      — This program is free software; you can redistribute it and/or modify
      — it under the terms of the GNU General Public License as published by
      — the Free Software Foundation; either version 2 of the License, or
      — (at your option) any later version.

      — This program is distributed in the hope that it will be useful,
      — but WITHOUT ANY WARRANTY; without even the implied warranty of
      — MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
      — GNU General Public License for more details.

      — You should have received a copy of the GNU General Public License
      — along with this program; if not, write to the Free Software
      — Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

      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)

      Thank you for your suggestion. Do you prefer this version?

    • Jedai,

      Indeed.

      Accordingly, I have written an alternate version of hanoi, hanoiHelperRichSansParens.hs; viz.:

      – hanoiHelperRichSansParens.hs
      — Haskell function to compute the Towers of Hanoi problem recursively,
      — using a helper function and the ‘$’ operator to take a function and
      — an argument, and accordingly save typing parentheses, rewritten
      — without parentheses

      — Originally based on hanoiHelperRich.hs, a Haskell function to compute
      — the Towers of Hanoi problem recursively, by Benjamin L. Russell,
      — dated April 13, 2009, at 20:13;
      — revised based on a comment from Jedai, dated April 18, 2009, at
      — 03:21, (see http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/#comment-57),
      — in response to my blog post “Climbing the Towers of Hanoi with
      — Haskell-style Curry from a Monadic Container (While Sparing the
      — Sugar!),” dated April 13, 2009, at 19:59 (see
      http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/)

      — Copyright(C) April 20, 2009, at 19:25,
      — by Benjamin L. Russell

      — This program is free software; you can redistribute it and/or modify
      — it under the terms of the GNU General Public License as published by
      — the Free Software Foundation; either version 2 of the License, or
      — (at your option) any later version.

      — This program is distributed in the hope that it will be useful,
      — but WITHOUT ANY WARRANTY; without even the implied warranty of
      — MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
      — GNU General Public License for more details.

      — You should have received a copy of the GNU General Public License
      — along with this program; if not, write to the Free Software
      — Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

      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

      Thank you for your comment. What do you think?

  3. 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 ?

  4. 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

Trackbacks & Pingbacks

  1. Haskell实现hanoi | GuanGuan's Blog

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: