# Square the sorted array using haskell

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)


## 1 Answer

This looks needlessly convoluted: there is a lot happening, all at once, on top of each other.

The way to think about this is: first square each number, then sort the resulting list. The way to transform each element of a list is map. The way to sort is, well, sort. The way to compose two functions (i.e. pass the result of one as argument to the other) is . (dot)

So:

sqrarr = sort . map sq
where
sq x = x * x

• Thank you for your time Feb 26, 2020 at 20:29