相关疑难解决方法(0)

这是代码:

{-# LANGUAGE FlexibleContexts #-}

import Data.Int
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Generic as V

{-# NOINLINE f #-} -- Note the 'NO'
--f :: (Num r, V.Vector v r) => v r -> v r -> v r
--f :: (V.Vector v Int64) => v Int64 -> v Int64 -> v Int64
--f :: (U.Unbox r, Num r) => U.Vector r -> U.Vector r -> U.Vector r
f :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64 …

我有一个明确的尾递归函数用于查找(选择nk)mod10007(k非负)

为什么这个函数会为大输入消耗大量内存？(即100000000选择50000000)我可以理解它是否可能很慢,但它不应该使用超过常量内存,应该吗？(假设GHC知道尾调优化)

GHC版本7.8.3

modulus :: Int
modulus = 10007

choose :: Int -> Int -> Int
choose n1 k1
    | s1 > 0 = 0
    | otherwise = q1
  where
    (q1, s1) = doChoose n1 k1 (1, 0)
    doChoose :: Int -> Int -> (Int, Int) -> (Int, Int)
    doChoose _ 0 (qr, sr) = (qr, sr)
    doChoose n k (qr, sr) =
        doChoose (n `seq` (n-1)) (k-1) (qr `seq` (qn * qr `rem` modulus * inv qk …