haskellで効率的にinverse series sumを行うには？

Question

これは私がhaskellで変換しようとしているコードです。しかし、不変性によって問題が生じます。可変変数なしで計算を行う方法。 [1..20]のリストを作成してマッピングすると、効率的なスペースのようには見えません。不変性を逃れる方法やテクニックはありますか？

int main() 
{ 
    int i,n=0; 
    double sum= 0.0; 
    for (i=1; i<20; ++i) 
    { 
     n += i; 
     sum = 1/(double) n; 
    } 
    printf("The sum is: %lf",sum); 
    return 0; 
} 

Answer 1

使用scanl1n秒のリストを生成する：そこから

> scanl1 (+) $ [1..19] 
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190] 

を、逆で

> map (1/) . scanl1 (+) $ [1..19] 
[1.0,0.3333333333333333,0.16666666666666666, ...] 

を計算し、それらを合計することは簡単なことである：

> sum . map (1/) . scanl1 (+) $ [1..19] 
1.8999999999999997 

ハスケルコードは、値を不変として扱い、中間リストの束を生成しているようだが、コンパイラは効率的な実行可能ファイルを生成するのに十分なほどスマートです。

Answer 2

一時的に不変性をエスケープするには、the ST monadを使用できます。

しかし、その必要はありません。次の式では、すべてが原因Stream Fusionに、コンパイラによって最適化されます。

sum (map (\n -> 1/fromIntegral n) [1..20]) 

Answer 3

あなたはGHCが-ddump-asmで生成したコードを調べることができます。

このプログラムコンパイルします。次に、12345の検索をasm-outputを見て、あなたはこのループが表示されます

$ ghc -O2 Main.hs -ddump-asm > asm-output 

：

_c47b: 
     addq %r14,%rsi 
     incq %r14 
_c476: 
     cmpq $12345,%r14 
     jne _c47b 

このショーで

main = print $ 1.0/fromIntegral (sum [(1::Int)..12345]) 

をリスト[1..12345]は実際には作成されていません。

更新あなたが三角数の逆数を合計することを目的と思わ

、 すなわち1/1 + 1/3 + 1/6 + ...それはあなたが書くことを意図し、次のとおりです。

我々が無い間ことをもう一度見生成されたアセンブリを調べる

main = print $ sum $ map (\x -> 1/(fromIntegral x)) $ scanl (+) 1 [(2::Int)..12345] 

：これは、ようHaskellで表現することができる

sum += 1.0/(double) n; 

仲介リストが作成されます。ここでは

_c4ao: 
     cvtsi2sdq %rsi,%xmm0 
     movsd _n4aP(%rip),%xmm2 
     divsd %xmm0,%xmm2 
     addsd %xmm2,%xmm1 
     incq %r14 
_c4ad: 
     addq %r14,%rsi 
     cmpq $12345,%r14 
     jne _c4ao 

%r14は%rsiが変数nと%xmm1はアキュムレータsumであり、あなたのCコード内のカウンターiです。