Haskell: Можно ли оптимизировать этот код?

Question

У меня есть следующий код. Я хочу знать, можно ли его оптимизировать, чтобы он работал быстрее.

Я хотел решить его с помощью SegmentTree, но я не очень хорошо разбираюсь в Haskell, поэтому я взял следующий список (недревесный) подход.

-- Program execution begins here 
main :: IO() 
main = do 
    _ <- getLine 
    arr <- map (read :: String -> Integer) . words <$> getLine 
    queryList <- readData 
    let queries = map (read :: String -> Integer) queryList 
    putStrLn "" 
    mapM_ print $ compute queries arr 

-- Construct a sublist 
sublist :: Integer -> Integer -> [Integer] -> [Integer] 
sublist start end list = take (fromInteger end - fromInteger start) . drop (fromInteger start) $ list 

-- Calculate the resulting list 
compute :: [Integer] -> [Integer] -> [Integer] 
compute [_] [_] = [] 
compute [_] [] = [] 
compute [_] (_:_) = [] 
compute [] (_:_) = [] 
compute [] [] = [] 
compute (x1:x2:xs) list = result : compute xs list where 
    result = frequency $ sublist x1 x2 list 

-- Read query list, end at terminating condition 
readData :: IO [String] 
readData = do 
    x <- getLine 
    if x == "0" 
    then return [] 
    else do xs <- readData 
      return (words x ++ xs) 

-- Return count of the most frequent element in a list 
frequency :: [Integer] -> Integer 
frequency list = toInteger (snd $ maximumBy (compare `on` snd) counts) where 
    counts = nub [(element, count) | element <- list, let count = length (filter (element ==) list)] 

Thanks.

Answer 1

Предкоммутировать частоты каждого префикса списка. Чтобы вычислить частоты подвычислителя, вычтите частоты двух префиксов, заканчивающихся на двух концах подсписного. Это уменьшит стоимость каждого запроса от O (n^2) до O (n). Чтобы вычислить частоты, используйте сортировку. Это уменьшит стоимость предвычисления от O (n^2) до O (n log n).