Why is the F# version of this program 6x faster than the Haskell one?

Question

Haskell version(1.03s):

module Main where   import qualified Data.Text as T   import qualified Data.Text.IO as TIO   import Control.Monad   import Control.Applicative ((<$>))   import Data.Vector.Unboxed (Vector,(!))   import qualified Data.Vector.Unboxed as V    solve :: Vector Int -> Int   solve ar =     V.foldl' go 0 ar' where       ar' = V.zip ar (V.postscanr' max 0 ar)       go sr (p,m) = sr + m - p    main = do     t <- fmap (read . T.unpack) TIO.getLine -- With Data.Text, the example finishes 15% faster.     T.unlines . map (T.pack . show . solve . V.fromList . map (read . T.unpack) . T.words)       <$> replicateM t (TIO.getLine >> TIO.getLine) >>= TIO.putStr 

F# version(0.17s):

open System  let solve (ar : uint64[]) =     let ar' =          let t = Array.scanBack max ar 0UL |> fun x -> Array.take (x.Length-1) x         Array.zip ar t      let go sr (p,m) = sr + m - p     Array.fold go 0UL ar'  let getIntLine() =     Console.In.ReadLine().Split [|' '|]     |> Array.choose (fun x -> if x <> "" then uint64 x |> Some else None)      let getInt() = getIntLine().[0]  let t = getInt() for i=1 to int t do     getInt() |> ignore     let ar = getIntLine()     printfn "%i" (solve ar) 

The above two programs are the solutions for the Stock Maximize problem and times are for the first test case of the Run Code button.

For some reason the F# version is roughly 6x faster, but I am pretty sure that if I replaced the slow library functions with imperative loops that I could speed it up by at least 3 times and more likely 10x.

Could the Haskell version be similarly improved?

I am doing the above for learning purposes and in general I am finding it difficult to figure out how to write efficient Haskell code.

Answer 1

If you switch to ByteString and stick with plain Haskell lists (instead of vectors) you will get a more efficient solution. You may also rewrite the solve function with a single left fold and bypass zip and right scan ⁽¹⁾. Overall, on my machine, I get 20 times performance improvement compared to your Haskell solution ⁽²⁾.

Below Haskell code performs faster than the F# code:

import Data.List (unfoldr) import Control.Applicative ((<$>)) import Control.Monad (replicateM_) import Data.ByteString (ByteString) import qualified Data.ByteString as B import qualified Data.ByteString.Char8 as C  parse :: ByteString -> [Int] parse = unfoldr $ C.readInt . C.dropWhile (== ' ')  solve :: [Int] -> Int solve xs = foldl go (const 0) xs minBound     where go f x s = if s < x then f x else s - x + f s  main = do     [n] <- parse <$> B.getLine     replicateM_ n $ B.getLine >> B.getLine >>= print . solve . parse 

<sub>1. See edits for an earlier version of this answer which implements solve using zip and scanr.
2. HackerRank website shows even a larger performance improvement.</sub>