class IntArray a where
  -- Получение элемента по индексу
  getElem :: a -> Int -> Int

  -- Установка элемента по индексу
  setElem :: a -> Int -> Int -> a

  -- Создание массива из нулей
  createZeroesIntArray :: Int -> a

  -- Увеличение значения элкмента по индексу на единицу
  incrementElem :: a -> Int -> a
  incrementElem intArray index = setElem intArray index ((getElem intArray index) + 1)

-- Реализация для [Int]
getListElem :: [Int] -> Int -> Int
getListElem list index = list !! index

setListElem :: [Int] -> Int -> Int -> [Int]
setListElem list index newValue = (take index list) ++ [newValue] ++ (drop (index + 1) list)

createZeroesList :: Int -> [Int]
createZeroesList count = replicate count 0

incrementListAt :: [Int] -> Int -> [Int]
incrementListAt list index = setListElem list index ((getListElem list index) + 1)

instance IntArray [Int] where
  getElem = getListElem
  setElem = setListElem
  createZeroesIntArray = createZeroesList

--Реализация для [Map]

getMapElem :: (Map.IntMap Int) -> Int -> Int
getMapElem map index = map Map.! index

setMapElem :: (Map.IntMap Int) -> Int -> Int -> (Map.IntMap Int)
setMapElem map index value = Map.insert index value map

createZeroesMap :: Int -> (Map.IntMap Int)
createZeroesMap count = Map.fromList [(index, 0) | index <- [0..count]]

instance IntArray (Map.IntMap Int) where
  getElem = getMapElem
  setElem = setMapElem
  createZeroesIntArray = createZeroesMap

incrementMapAt :: (Map.IntMap Int) -> Int -> (Map.IntMap Int)
incrementMapAt list index = setMapElem list index ((getMapElem list index) + 1)

fill :: forall a. IntArray a => a -> a
fill list = foldl (\zs -> \i ->  incrementElem zs i) (createZeroesIntArray ((maximum list) + 1)) list

fillList :: [Int] -> [Int]
fillList list = foldl (\zs -> \i ->  incrementListAt zs i) (createZeroesList ((maximum list) + 1)) list

fillMap :: (Map.IntMap Int) -> (Map.IntMap Int)
fillMap list = foldl (\zs -> \i ->  incrementMapAt zs i) (createZeroesMap ((maximum list) + 1)) list

main :: IO ()
main = putStrLn $ show (fill @[Int] [0,2,4,2])