Tower of Hanoi Haskell

Question

I have found the following code for solving the Towers of Hanoi. The code is working fine! But I cannot understand what's going on exactly.

import Data.Bits    
hanoi :: Int -> [(Int, Int)]
hanoi n = map (\x -> ((x .&. (x-1)) `mod` 3, ((x .|. (x-1)) + 1) `mod` 3)) [1..shift 1 n]
main = print $ hanoi 5

Can anybody explain this code? Thanks

Answer 1

I will assume if you understand the general algorithm of solving Towers of Hanoi problem.

What goes on in your code, line by line:

1. import Data.Bits we are importing bit-manipulation functions, the ones we will use in our case are .&., .|. and shift.

2. hanoi :: Int -> [(Int, Int)] the function takes one argument (number of discs) and returns a list of pairs representing moves (format: (from, to)).

3. hanoi n = map ... . We are mapping this a function over this list [1..shift 1 n], which stores subsequent left bit shifts (1 << n) from 1 to n. 3a. The mapping function ((\x -> ((x .&. (x-1))mod3, ((x .|. (x-1)) + 1)mod3))) returns, for a given argument, a pair of (x .&. (x-1))mod3 and ((x .|. (x-1)) + 1)mod3), (in (from, to) format). Here is an explanation of why the function works that way.
4. main = print $ hanoi 5 print the result in a main function.