hanoi.hs

import Control.Monad.State

-- first version
toh n = fst $ tohmoves n (n, 0, 0)

tohmoves :: Int -> (Int, Int, Int) -> (Int, (Int, Int, Int))
tohmoves 1 (a, b, c) = (1, (a - 1, b, c + 1))
tohmoves n (a, b, c) =
  let (n', (a', c', b')) = tohmoves (n - 1) (a, c, b)
      (n'', (a'', b'', c'')) = tohmoves 1 (a', b', c')
      (n''', (b''', a''', c''')) = tohmoves (n - 1) (b'', a'', c'')
  in (n' + n'' + n''', (a''', b''', c'''))
 
-- second version
toh2 n = fst $ runState (tohmoves2 n) (n, 0, 0)
  
tohmoves2 :: Int -> State (Int, Int, Int) Int
tohmoves2 1 = modify (\(a, b, c) -> (a - 1, b, c + 1)) *> pure 1
tohmoves2 n = do
  modify (\(a, b, c) -> (a, c, b))
  n' <- tohmoves2 (n - 1)
  modify (\(a, c, b) -> (a, b, c))
  n'' <- tohmoves2 1
  modify (\(a, b, c) -> (b, a, c))
  n''' <- tohmoves2 (n - 1)
  modify (\(b, a, c) -> (a, b, c))
  pure $ n' + n'' + n'''