Haskell do notation and pattern matching?

Question

So here is my code..

move :: [Char] -> [Char] -> IO ()
move f t = do { putStrLn ("Moving from \"" ++ f ++ "\" to \"" ++ t ++ "\"!") }

hanoi :: Integer -> [Char] -> [Char] -> [Char] -> IO ()
hanoi 0 f _ _ = do { putStrLn ("Lane \""++ f ++ "\" empty!") }
hanoi n f h t = do { hanoi (n - 1) f t h
                   ; move f t
                   ; hanoi (n - 1) h f t }

When I execute hanoi 4 "A" "B" "C" I expect something like this:

Moving from "A" to "B"!
Moving from "A" to "C"!
Moving from "B" to "C"!
Moving from "A" to "B"!
Moving from "C" to "A"!
Moving from "C" to "B"!
Moving from "A" to "B"!
Tower "A" empty!
...

But I am getting :

Tower "A" empty!
Moving from "A" to "B"!
Tower "C" empty!
Moving from "A" to "C"!
Tower "B" empty!
Moving from "B" to "C"!
Tower "A" empty!
Moving from "A" to "B"!
Tower "C" empty!
Moving from "C" to "A"!
Tower "B" empty!
Moving from "C" to "B"!
...

Seems to me that there is some issue with pattern matching and do notation, and I cant figure out what. Can someone explain to me what am I doing wrong or not getting here, I suppose there is someting connected with async execution of IO monad.

I am new to Haskell, and still have not entirely figured out monads...

There is no issue with "async execution of IO monad" (I assume you're referring interleaving of output on lazy streams - this is not occuring) or any other issues with monads. Indeed, your program is correct. Every call `hanoi n ...` for every positive `n` will first call `hanoi (n-1) ..` before doing *anything else* - this is by definition of `hanoi n`, clearly, since its first statement is `hanoi (n-1)`. By induction, every call to `hanoi n` will call `hanoi 0` before doing anything else. Hence, "Tower .. empty" precedes every line! — user2407038, Oct 02 '19 at 22:37
you should check out [this answer in - Tower of Hanoi: Recursive Algorithm](https://stackoverflow.com/a/58259294/7541700) — costargc, Oct 06 '19 at 17:52

score 3 · Accepted Answer · answered Oct 03 '19 at 04:44

I don't know where your misunderstanding is, but you are probably blaming the Monad boogeyman too soon. Tracing through this program in Haskell seems identical to tracing through it's rather straight-forward C counterpart which yields the same as you showed:

// move :: [Char] -> [Char] -> IO ()
void move(char *f, char *t)
{
    // move f t = do { putStrLn ("Moving from \"" ++ f ++ "\" to \"" ++ t ++ "\"!") }
    printf("Moving from \"%s\" to \"%s\"!\n", f, t);
}

// hanoi :: Integer -> [Char] -> [Char] -> [Char] -> IO ()
void hanoi(int64_t n, char *f, char *h, char *t)
{
    if (0 == n) {
        // hanoi 0 f _ _ = do { putStrLn ("Lane \""++ f ++ "\" empty!") }
        printf("Lane \"%s\" empty!\n", f);
    } else {
        // hanoi n f h t =
        hanoi(n-1,f,t,h); // hanoi (n - 1) f t h
        move(f,t);        // move f t
        hanoi(n-1,h,f,t); // hanoi (n - 1) h f t
    }
}

int main()
{
    hanoi(4,"A","B","C");
    return 0;
}

Consider what's going on. You said hanoi 4 ... and the next line of code of any significance is hanoi (4 - 1) ... which, as @user2407038 has already commented, is going to be followed by hanoi 2, hanoi 1 and hanoi 0.

I think you should consider your algorithm more carefully.

[some problem with] pattern matching and do notation

While not entirely unrelated, these concepts are pretty distinct. The only pattern you have is 0 and you don't have any patterns due to binds in your do blocks (i.e. [some pattern] <- move).

Never mind for previous comments.. I understood. Thank you also. — djoloho, Oct 03 '19 at 08:59

Haskell do notation and pattern matching?

1 Answers1