DEV Community

Discussion on: Daily Challenge #13 - Twice Linear

View post
Collapse
 
auroratide profile image
Timothy Foster •

Haskell, featuring tail recursion!

import Data.Set (Set)
import qualified Data.Set as Set

u :: Int -> Set Int
u layers = u' layers (Set.singleton 1)
  where
    u' 0 s = s
    u' layer s = u' (layer - 1) (Set.unions [s, Set.map (\x -> 2*x+1) s, Set.map (\x -> 3*x+1) s])

dbl_linear :: Int -> Int
dbl_linear n = Set.elemAt n (u layers)
  where layers = ceiling $ logBase 2 $ fromIntegral (n + 1)