63292


大きな数の二項係数を大量に計算する必要のある場面において、以下の様に二項係数を計算する関数binomを定義しようと思い、階乗やその逆数を保持するリストfactList,factInvListを定義しました。

しかし、binomが呼び出される場面において、遅延評価のため、毎回このリストが計算されているように思われます。

リストを一回計算したらそれを使いまわすような仕様にするにはどの様に改善すればいいのでしょうか。

法を1000000007として計算しています。

[code]

    base :: Integer
    base = 1000000007
    
    modBase :: Integer -> Integer
    modBase n = n `mod` base
    
    timesOnBase :: Integer -> Integer -> Integer
    timesOnBase a b = modBase $ a * b
    
    power :: Integer -> Integer -> Integer
    power x n
       | n == 0         = 1
       | n `mod` 2 == 0 = power (timesOnBase x x) (n `div` 2)
       | otherwise      = timesOnBase x $ power x $ n-1
    
    inv :: Integer -> Integer
    inv n = power n $ base - 2
    
    factList :: [Integer]
    factList = makeFactList base
       where
          makeFactList :: Integer -> [Integer]
          makeFactList n = scanl (timesOnBase) 1 [1..n]
    
    factInvList :: [Integer]
    factInvList = map inv factList
    
    --binom n m = nCm
    binom :: Int -> Int -> Integer
    binom n m = (factList !! n) `timesOnBase` (factInvList !! m) `timesOnBase` (factInvList !! (n-m))
    
    
[/code]


CC BY-SA 4.0
2020-02-22T10:41:03.083
63277
2020-02-23T01:38:17.910
2020-02-22T10:52:36.263
24965
24965
question
haskell
Haskellで定数を先に計算する方法


> しかし、binomが呼び出される場面において、遅延評価のため、毎回このリストが計算されているように思われます。

@metropolis さんのコメントのとおり、実際には`factList`は必要に応じて一度しか計算されていません。

恐らく実行時間が想定より長くかかることから疑われたのかと思いますが、このコードの実行時間を改善するとしたら私ならリストの代わりに`vector`パッケージの`Vector`型を使うでしょう。  
リストには一応インデックスでアクセスするための演算子 `!!`
が提供されてますが、インデックス（右辺に指定した整数）が大きくなればなるほど時間がかかってしまうので、今回の用途には適していません。


CC BY-SA 4.0
2020-02-23T01:38:17.910
63292
2020-02-23T01:38:17.910
8007
63277
answer