def filter_halves.go

unified-nsga-iii@0.2.2.0 · util.bend:305

import Base

305# Independent keep/drop. Mid-split; `take ++ drop` matches the old
306# tail-first cons_if walk (original relative order).
307def filter_halves.go(
308  ~A: Data,
309  ~C: Data,
310  ~p: @+c:C -> @+x:A -> Bool,
311  +ctx: C,
312  +fuel: Nat,
313  xs: List<&2, A>
314) -> List<&2, A>:
315  match fuel xs:
316    case 0n Nil{}:
317      Nil{}
318    case 0n +h <> t:
319      keep_if(A, h, filter_halves.go(~A, ~C, ~p, ctx, 0n, t), p(ctx, h))
320    case 1n+p0 Nil{}:
321      Nil{}
322    case 1n+p0 +h <> Nil{}:
323      keep_if(A, h, Nil{}, p(ctx, h))
324    case 1n+p0 h <> t:
325      +all = {h <> t : List<&2, A>}
326      +mid = Nat.div(list_len(A, all), 2n)
327      a b = filter_halves.go(~A, ~C, ~p, ctx, p0, List.take(&2, A, all, mid)) filter_halves.go(~A, ~C, ~p, ctx, p0, List.drop(&2, A, all, mid))
328      List.append(&2, A, a, b)