Count inversions: StackOverflowError in Frege, works fine in Haskell

Question

I am trying to count inversions for a list of numbers. The following Frege program works for small set of numbers but throws StackOverflowError for 100000 numbers.

import frege.IO

inversionCount [] _ = (0, [])
inversionCount [x] _ = (0, [x])
inversionCount xs n = (count, sorted) where
  count = lcount + rcount + mergecount
  (lcount, lsorted) = inversionCount left lsize
  (rcount, rsorted) = inversionCount right rsize
  (mergecount, sorted) = inversionMergeCount lsorted lsize rsorted rsize (0, [])
  (left, right) = splitAt mid xs
  mid = n `quot` 2
  lsize = mid
  rsize = n - mid

inversionMergeCount xs _ [] _ (acc,sorted) = (acc, reverse sorted ++ xs)
inversionMergeCount [] _ ys _ (acc,sorted) = (acc, reverse sorted ++ ys)
inversionMergeCount (xs@(x:restx)) m (ys@(y:resty)) n (acc, sorted)
  | x < y = inversionMergeCount restx (m - 1) ys n (acc, x:sorted)
  | x > y = inversionMergeCount xs m resty (n - 1) (acc + m, y:sorted)
  | otherwise = inversionMergeCount restx (m - 1) resty (n - 1) (acc, x:y:sorted)

main (fileName:_) = do
  input <- readFile fileName
  let xs = map atoi (lines input)
  println . fst $ inversionCount xs 100000

--Haskell's readFile using Java's Scanner
type JScanner = JScannerT RealWorld

data JScannerT s = native java.util.Scanner where
  native new :: File -> ST s (Exception JScanner)
  native useDelimiter :: JScanner -> String -> ST s JScanner
  native next :: JScanner -> ST s String

readFile f = do
  file <- File.new f
  exceptionScanner <- JScanner.new file
  let scanner = either throw id exceptionScanner
  scanner.useDelimiter "\\Z"
  scanner.next

The same code in Haskell works fine:

import System.Environment

inversionCount [] _ = (0, [])
inversionCount [x] _ = (0, [x])
inversionCount xs n = (count, sorted) where
  count = lcount + rcount + mergecount
  (lcount, lsorted) = inversionCount left lsize
  (rcount, rsorted) = inversionCount right rsize
  (mergecount, sorted) = inversionMergeCount lsorted lsize rsorted rsize (0, [])
  (left, right) = splitAt mid xs
  mid = n `quot` 2
  lsize = mid
  rsize = n - mid

inversionMergeCount xs _ [] _ (acc,sorted) = (acc, reverse sorted ++ xs)
inversionMergeCount [] _ ys _ (acc,sorted) = (acc, reverse sorted ++ ys)
inversionMergeCount (xs@(x:restx)) m (ys@(y:resty)) n (acc, sorted)
  | x < y = inversionMergeCount restx (m - 1) ys n (acc, x:sorted)
  | x > y = inversionMergeCount xs m resty (n - 1) (acc + m, y:sorted)
  | otherwise = inversionMergeCount restx (m - 1) resty (n - 1) (acc, x:y:sorted)


main = do
  (fileName: _) <- getArgs
  contents <- readFile fileName
  let xs :: [Int]
      xs = map read (lines contents)
  print . fst $ inversionCount xs 100000

What could be the cause for stack overflow? Is it some function not being tail-recursive?

Answer 1

Haskell most likely has a better strictness analyser, or tail recursion is implemented differently, or the runtime simply has more stack available.

First thing I would try is setting -Xss8m, or even 16m.

If that doesn't help, keep in mind that lazy arguments that are updated with applications of strict functions like (-), (+) etc. build up thunks that sometimes later will have to be evaluated at once. This is the same problem as with foldl, and it looks like the second argument of inversionMergeCount and inversionCount suffer of this.

The Frege compiler should warn about this, if it sees this, but it doesn't as of now.

Another point is, why do you pass the last 2 arguments in tuples? You could also make acc strict.

Answer 2

As per Ingo's suggestion, I made the changes and the code is now working. I also had to make the count as Integer instead of Int to avoid int overflow. Here is the updated code with strict annotations and Integer conversion:

inversionCount [] _ = (zero, [])
inversionCount [x] _ = (zero, [x])
inversionCount xs n = (count, sorted) where
  count = lcount + rcount + mergecount
  (lcount, lsorted) = inversionCount left lsize
  (rcount, rsorted) = inversionCount right rsize
  (mergecount, sorted) = inversionMergeCount lsorted lsize rsorted rsize zero []
  (left, right) = splitAt mid xs
  mid = n `quot` 2
  lsize = mid
  rsize = n - mid


inversionMergeCount xs _ [] _ !acc sorted = (acc, reverse sorted ++ xs)
inversionMergeCount [] _ ys _ !acc sorted = (acc, reverse sorted ++ ys)
inversionMergeCount (xs@(x:restx)) !m (ys@(y:resty)) n !acc sorted
  | x < y = inversionMergeCount restx (pred m) ys n acc (x:sorted)
  | x > y = inversionMergeCount xs m resty (pred n) (acc + m.big) (y:sorted)
  | otherwise = inversionMergeCount restx (pred m) resty (pred n) acc (x:y:sorted)