Solution to Hackerrank challenge "Sherlock and Queries"

First, here is the full challenge description:


Watson gives to Sherlock an array: \$A_1, A_2, ..., A_N\$. He also gives to
Sherlock two other arrays: \$B_1, B_2, ..., B_M\$ and \$C_1, C_2, ..., C_M\$.


Then Watson asks Sherlock to perform the following program:

for i = 1 to M do
    for j = 1 to N do
        if j % B[i] == 0 then
            A[j] = A[j] * C[i]
        endif
    end do
end do

Can you help Sherlock and tell him the resulting array A? You should
print all the array elements modulo \$(10^9 + 7)\$.


Input Format


The first line contains two integer numbers \$N\$ and \$M\$. The next line
contains \$N\$ integers, the elements of array A. The next two lines
contains \$M\$ integers each, the elements of array B and C.


Output Format


Print \$N\$ integers, the elements of array A after performing the program
modulo \$(10^9 + 7)\$.


Constraints


\$1 ≤ N, M ≤ 10^5\$

\$1 ≤ B[i] ≤ N\$

\$1 ≤ A[i], C[i] ≤ 10^5\$


Sample Input

4 3
1 2 3 4
1 2 3
13 29 71

Sample Output

13 754 2769 1508

And here is the code of my solution:

```
import Control.Applicative
import Control.Arrow
import Control.Monad.Primitive
import Control.Monad.ST
import Data.Int
import Data.List.Split
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.Map as M
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as Vmu

type Vec = V.Vector Int64

(|>) :: a -> (a -> b) -> b
(|>) x y = y x
infixl 0 |>

main :: IO ()
main = do
[n, m] >> map read) getLine
inputLines B.getContents
let [a, b, c] = map readInts inputLines
solve n m a b c |> V.toList >>> map show >>> unwords |> putStrLn

-- http://stackoverflow.com/questions/25913481/read-numbers-from-stdin-into-a-data-vector-unboxed-vector-int64
readInts :: B.ByteString -> Vec
readInts = B.split ' ' >>> mapMaybe (B.readInt >>> liftA fst) >>>
map fromIntegral

Your Haskell code is quite a tangle. I think you may have jumped the gun a bit with all those mutable vectors. Before reaching for mutation and iterative solutions in a Haskell program, take a step back and look at the shape of the problem before you. In this case the execution of the algorithm doesn't actually depend on any intermediate values, that is, there aren't any conditionals or jumps predicated on the A array itself right? There's a straight transform of input to output which is where functional lazy solutions can really shine.

Here's my version.

module Main where

main :: IO ()
main = do
        input  ((Int, Int), [Int], [Int], [Int])
readInput s = 
        let 
            ( [n, m] : a : b : c : _) = map (map read) . map words . lines $ s
        in
            ( (n, m) , a , b , c )

solve :: Int -> Int -> [Int] -> [Int] -> [Int] -> [Int]
solve n _ as bs cs = map product . zipWith (:) as
                   $ [ [ c | (b, c) <- zip bs cs, j `mod` b == 0] | j <- [1..n]]

You can see most of the program is devoted to input and output, and only two lines (three if you count the function type signature) are required to implement the algorithm itself. Here's the trick.

The loops can be reordered so that instead of mutating an input array, you're actually producing an output list of multiplicands.

$ [ [ _ ] | j <- [1..n]]

Iterating on the j index was the inner loop originally, but because j indexes the output list I move it to the outside to take advantage of the 1-1 correspondence with the input list.

[c | (b, c) <- zip bs cs, j `mod` b == 0]

By noticing that the B and C arrays are only ever used in lockstep, I can throw out the i index (and the m array size at that, I left it as an argument just for correspondence with the original problem statement and your version). bs and cs are then zipped so that I can walk over them pairwise. When the test on b succeeds, I just include c in the output as a multiplicand.

zipWith (:) as

Because the output of the list comprehensions now contains lists of multiplicands from C that correspond to indices in A, I just pop the multipliers onto the front of the multiplicand lists and then...

map product

Compute the product at each index. The rest of the code is just pretty-printing and IO.

On the very small sample input you provided my version actually runs a fraction of a second faster than yours, my guess is that's due to the overhead you incur from setting up your vectors. If you have a larger sample input I'd be very interested to see the performance. I would wager that our two versions stay within an order of magnitude of each other on running time, and they should use roughly the same amount of space due to lazy evaluation in my version. Theoretically. ;)

StackExchange Code Review Q#63253, answer score: 2