I want inputs on how I can square the sorted Array more efficiently in haskell. I wrote a very naive algorithm to solve the problem. What I am doing is comparing the head and the last element of list on absolute value and whichever is max I square the element and add it to accumulator.
But I think it is very slow. Is there any data structure that I can use to make it more efficient.
import qualified Data.List as List
sqrarr:: [Int] -> [Int]
sqrarr xss = helper xss []
helper::[Int] -> [Int] -> [Int]
helper [] acc = acc
helper [x] acc = [(x^ 2)] ++ acc
helper (x:xss) acc = case abs x > abs (List.last xss) of
False -> helper (x: (List.init xss)) (((List.last xss)^2): acc)
True -> helper xss ((x ^ 2):acc)
The above code works and gives the desired input
sqrarr [-7, -4, 2,5,8]
[4,16,25,49,64]
I have found another solution
import Data.Array
sqrarr2::[Int] -> [Int]
sqrarr2 xss = helper2 0 (length xss -1)
(listArray (0,(length xss -1)) xss)
[]
helper2::Int -> Int -> Array Int Int -> [Int] -> [Int]
helper2 l r arr acc = case l > r of
True -> acc
False -> case abs (arr!l) > abs (arr!r) of
False -> helper2 l (r - 1) arr ((arr!r ^ 2):acc)
True -> helper2 (l + 1) r arr ((arr!l ^ 2):acc)