Namaran

Code daily. Without assist.

2026-11-07

RangeSum.hs

import Data.Array

rangeSum :: Array Int Int -> Int -> Int -> Int
rangeSum pre l r = pre ! r - pre ! l

main :: IO ()
main = do
  let xs = [3, 1, 4, 1, 5]
      pre = listArray (0, length xs) (scanl1 (+) xs)
  print (rangeSum pre 1 4)
  print (rangeSum pre 0 5)

pre ! k にリスト xs の先頭 k 個の和を入れた配列 pre を作り、rangeSum pre l r で l 番目から r - 1 番目まで(0始まり)の要素の和を求めるつもりのプログラムです。main のとおり [3, 1, 4, 1, 5] の1番目から3番目までと、全体の和を表示すると、本来は 6 と 14 が出ます。いまは1行目に 10 が表示され、2行目を表示する前に、配列の要素が未定義だというエラーで止まります。

Answer

Wrong

let xs = [3, 1, 4, 1, 5]
    pre = listArray (0, length xs) (scanl1 (+) xs)

添字の範囲 (0, length xs) は0から5までの6個ですが、scanl1 (+) xs は [3, 4, 8, 9, 14] の5個しか作りません。listArray はリストの長さが範囲と合うかを調べず、前から順に詰めるので、pre ! 0 が3、pre ! 4 が14になり、pre ! 5 には値がありません。1つ目の rangeSum pre 1 4 は pre ! 4 - pre ! 1 の 14 - 4 で 10 になります。pre ! k が先頭 k + 1 個の和になっていて、区間が1つ右へずれているからです。

2つ目の rangeSum pre 0 5 の pre ! 5 は、添字5が範囲の中なので (!) の範囲検査を通ります。それでも要素が無いので、値を求めた時点で、未定義の配列要素だというエラーになります。配列の要素は使われるまで評価されないので、listArray の時点では何も起きず、1行目は表示されます。(!) が確かめるのは添字が範囲に入っているかだけで、その位置に値が入っているかではありません。

Right

let xs = [3, 1, 4, 1, 5]
    pre = listArray (0, length xs) (scanl (+) 0 xs)

scanl (+) 0 xs は先頭に0を置いて [0, 3, 4, 8, 9, 14] の6個を作るので、範囲 (0, length xs) とちょうど合い、pre ! k が先頭 k 個の和になります。1つ目は pre ! 4 - pre ! 1 の 9 - 3 で 6、2つ目は 14 - 0 で 14 です。pre ! 0 が0なので、先頭から始まる区間も同じ式で求まります。