% Some generally useful function that could go into a prelude


function even_elts(xs) = {xs[2*i] : i in &((#xs+1)/2)}
function odd_elts(xs) = {xs[2*i+1] : i in &(#xs/2)}

function interleave(xs,ys) = concat({[x,y] : x in xs; y in ys})

function bottop(v) = let n = (#v+1)/2 in partition(v, [n,#v-n])

function last(v) = v[#v-1]

function reverse(xs) = {xs[#xs-i-1] : i in &#xs}


% Some scans


% Only works for input length a power of 2
% The scan that Blelloch calls tree scan
% This is an exclusive scan. Output does not depend
% on last element of input
function scan_op(op,identity,a) =
if #a == 1 then [identity]
else
  let  e = even_elts(a);
       o = odd_elts(a);
       s = scan_op(op,identity,{op(e,o): e in e; o in o})
  in interleave(s,{op(s,e): s in s; e in e})

% Another exclusive scan
% Can you make this work for input lengths not a power of two?
function scan12(f, b, xs) =
  if #xs == 1 then [b]
  else
    let n = #xs / 2;
	ps = partition(xs, {2 : _ in &n});
        ts = {f(p[0], p[1]) : p in ps};
        ys = scan12(f, b, ts)
    in  concat({[y, f(y, p[0])] : y in ys; p in ps})




% An inclusive scan. The most obvious recursive decomposition.
function sklansky(op,a) =
 if #a == 1 then a
 else
  let hs = {sklansky(op,x) : x in bottop(a)};
      x  = last(hs[0]);
      rs = {op(x,y) : y in hs[1]}
  in hs[0] ++ rs




   
% Batcher's bitonic sorter (see lecture)


% bitonic merger
function bitonic_sort(a) =
if (#a == 1) then a
else
    let
	bot = bottop(a)[0];
	top = bottop(a)[1];
	mins = {min(bot,top):bot in bot;top in top};
	maxs = {max(bot,top):bot in bot;top in top}
    in concat({bitonic_sort(x) : x in [mins,maxs]})

% bitonic sorter
function batcher_sort(a) =
if (#a == 1) then a
else
    let b = {batcher_sort(x) : x in bottop(a)}
    in bitonic_sort(b[0]++reverse(b[1]))