Hackerrank, Utopian Tree in Haskell

Question

Problem statement

The Utopian tree goes through 2 cycles of growth every year. The first growth cycle occurs during the monsoon, when it doubles in height. The second growth cycle occurs during the summer, when its height increases by 1 meter. Now, a new Utopian tree sapling is planted at the onset of the monsoon. Its height is 1 meter. Can you find the height of the tree after \$N\$ growth cycles?

Input Format

The first line contains an integer, \$T\$, the number of test cases. \$T\$ lines follow. Each line contains an integer, \$N\$, that denotes the number of cycles for that test case.

Constraints

1 <= T <= 10 
0 <= N <= 60

Sample Input: #01:

2
3
4

Sample Output: #01:

6
7

Explanation: #01:

There are 2 testcases.

N = 3:
* the height of the tree at the end of the 1st cycle = 2 * the height of the tree at the end of the 2nd cycle = 3 * the height of the tree at the end of the 3rd cycle = 6

N = 4:

• the height of the tree at the end of the 4th cycle = 7

This is my accepted solution:

module Main where

import Control.Monad(mapM_)

main = do
    let base_height = 1
    n_test_cases <- readLn
    test_cases <- getList n_test_cases
    mapM_ (\i -> putStrLn $ show $ utopianTreeHeight base_height 
        (test_cases !! i)) [0..n_test_cases - 1]

getList :: Int -> IO [Int]
getList n = 
    if n == 0
        then return []
    else
        do
            x <- readLn
            xs <- getList (n - 1)
            return (x:xs)

utopianTreeHeight :: Int -> Int -> Int
utopianTreeHeight present_height 0 = present_height
utopianTreeHeight present_height cycles = 
    if odd cycles
        then 2 * (utopianTreeHeight present_height (cycles - 1))
    else
        1 + (utopianTreeHeight present_height (cycles - 1))

So, does this solution show good Haskell style? What could be improved? I have doubts especially regarding the way I deal with the IO (which was not provided by Hackerrank), as it was the first time I read about and applied the Haskell way of doing it.

Answer 1

For the main function

1 : you can replace getList with replicateM

2 : replace putStrLn $ show with print

3 : you can pass test_cases directly to mapM_

4 : you also don't need to import mapM_

5 : you should use camelCase for names instead of snake_case

import Control.Monad (replicateM)

main = do
  numberOfTests <- readLn
  testCases <- replicateM numberOfTests readLn
  mapM_ (print . utopian) testCases 

Answer 2

Your solution lacks the use of higher-order functions that are an essential part of Haskell style. Instead of writing explicitly recursive functions that plumb state around (like an impoverished for-loop) seek out, create, and use constructs that have semantic meaning to your problem.

Starting from the small, the problem defines a growth cycle as a either doubling a tree's height, or increasing it by one. We can encode all of that information in Haskell.

type Height = Integer
type Cycle = Height -> Height

monsoon :: Cycle
monsoon = (* 2)

summer :: Cycle
summer = (+ 1)

Next, we know that the cycles begin with a monsoon and thereafter proceed regularly indefinitely into the future.

timeline :: [Cycle]
timeline = cycle [monsoon, summer]

cycle is a function from the Haskell Prelude module which turns a finite list into an infinite list by infinitely repeating it. Now we can take a finite sequence from the front of the list to determine all of the cycles the tree will experience over a given span of time.

-- code fragment
take n timeline :: [Cycle] -- n cycles from planting

Now given the original height of the tree and the cycles it will experience over a given span of time, we can find the resulting height of the tree.

utopian :: Int -> Height
utopian n = foldl (flip ($)) 1 $ take n timeline

We fold over the finite timeline from the left, applying each growth function to the accumulator (starting with the height of the tree at year 0).

Answer 3

Let's look at the first few values for even \$N\$:

*Main> [ utopianTreeHeight 1 n | n <- [0, 2 .. 20] ]
[1,3,7,15,31,63,127,255,511,1023,2047]

They're all one less than a power of two:

*Main> [ 1 + utopianTreeHeight 1 n | n <- [0, 2 .. 20] ]
[2,4,8,16,32,64,128,256,512,1024,2048]

What about for odd values of \$N\$?

*Main> [ utopianTreeHeight 1 n | n <- [1, 3 .. 20] ]
[2,6,14,30,62,126,254,510,1022,2046]

They're all two less than a power of two:

*Main> [ 2 + utopianTreeHeight 1 n | n <- [1, 3 .. 20] ]
[4,8,16,32,64,128,256,512,1024,2048]

This is a hint that we can find a closed-form formula for the \$N\$th term:

height :: Int -> Int
height n | even n    = (2 ^ x) - 1
         | otherwise = (2 ^ x) - 2
         where x = (n + 1) `div` 2 + 1