2
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your time \$\endgroup\$ – presci Feb 26 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.