gistfile1.txt

let work_efficient [n] (xs: [n]i32) : [n]i32 =
  unsafe
  let m = ilog2 n

  let upswept =
    loop xs = copy xs for d in m-1..m-2...0 do
    let (is, vs) =
      unzip (tabulate (1<<d)
                      (\i ->
                         let stride = 1<<(m-d)
                         let me = (i+1) * stride - 1
                         let from = me - stride/2
                         in (me, xs[from] + xs[me])))
    in scatter xs is vs

  let upswept[n-1] = 0

  let downswept =
    loop xs = upswept for d in 1...m do
    let (is0, vs0) =
      unzip (tabulate (1<<(d-1))
                      (\i ->
                         let stride = 1<<(1+m-d)
                         let me = (i+1) * stride - 1
                         let from = me - stride/2
                         in (me, xs[from] + xs[me])))

    let (is1, vs1) =
      unzip (tabulate (1<<(d-1))
                      (\i ->
                         let stride = 1<<(1+m-d)
                         let from = (i+1) * stride - 1
                         let me = from - stride/2
                         in (me, xs[from])))

    in scatter xs (is0++is1) (vs0++vs1)

  in downswept