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] -&gt; [Int]
sqrarr xss = helper  xss []


helper::[Int] -&gt; [Int] -&gt; [Int]
helper  [] acc = acc
helper [x] acc = [(x^ 2)] ++ acc
helper (x:xss) acc = case abs x &gt; abs (List.last xss) of
  False -&gt; helper (x: (List.init xss)) (((List.last xss)^2): acc)
  True -&gt; 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] -&gt; [Int]
sqrarr2 xss = helper2 0 (length xss -1)
                (listArray (0,(length xss -1)) xss)
                []


helper2::Int -&gt; Int -&gt; Array Int Int -&gt; [Int] -&gt; [Int]
helper2 l r arr acc = case l &gt; r of
  True -&gt; acc
  False -&gt; case abs (arr!l) &gt; abs (arr!r) of
    False -&gt; helper2 l (r - 1) arr ((arr!r ^ 2):acc)
    True -&gt; helper2 (l + 1) r arr ((arr!l ^ 2):acc)
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