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\$
0

1 Answer 1

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
\$\endgroup\$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.