Count inversions: StackOverflowError in Frege, works fine in Haskell
frege, haskell
Solution
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.
Problem
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?