import { Seq, Walk, take, nil} from "../../kolibri/sequence/sequence.js";
import { plusOp } from "../../kolibri/sequence/util/helpers.js";
// make a new sequence with the minimum placed at the front, otherwise unchanged
const minToFront = seq => seq.reduce$((acc, cur) =>
acc.isEmpty()
? Seq(cur)
: cur <= acc.head()
? acc.cons(cur)
: acc.snoc(cur)
, Seq()
);
// for each element, make a sequence with the minimum at front and pass on the remainder
// this is strikingly similar to list deconstruction plus recursion on the remainder in haskell
// - *without using recursion*
const cascade = seq => seq.scan( (acc, _cur) =>
minToFront(acc.drop(1))
, minToFront(seq)
);
const sort = seq => seq
.cons(nil) // such that the first element gets its call
.pipe(cascade)
.and(take(1)) // like map(head), but getting rid of last empty sequence
;
// let's check
const results = Seq(
Walk(100,10,-1).pipe(sort).take(5) ['=='] ([10,11,12,13,14]), // in O(5*n), i.e. O(n)
Seq(5,2,6,3).pipe(sort) ['=='] ([2,3,5,6]),
Seq(5,2,6,2).pipe(sort) ['=='] ([2,2,5,6]), // check duplicates
Seq().pipe(sort) ['=='] ([]), // check empty
);
out.innerHTML = results
.map( passed => `<`+`span class="${passed}">${passed}<`+`/span>`)
.reduce$(plusOp, '');