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

You want us to explain Haskell syntax of this function, Towers of Hanoi solution or both? — syntagma, May 30 '17 at 08:36

score 2 · Accepted Answer · answered May 30 '17 at 08:47

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

What goes on in your code, line by line:

import Data.Bits we are importing bit-manipulation functions, the ones we will use in our case are .&., .|. and shift.
hanoi :: Int -> [(Int, Int)] the function takes one argument (number of discs) and returns a list of pairs representing moves (format: (from, to)).
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.
main = print $ hanoi 5 print the result in a main function.

Thanks a lot for your comments ! Yes I am understanding the algorithm, but I need to understand Haskell. — Henning, May 30 '17 at 08:56
Can you try to give me a more easier answer ?, I don´t understand the binary calculation. — Henning, Jun 02 '17 at 08:02

Tower of Hanoi Haskell

1 Answers1