def osa_row

cli@0.2.0.0 · cli.bend:5692

import Base

5692# Row i of optimal string alignment for a[i]: up starts at d[i-1][j-1], up2
5693# at d[i-2][j-2], and left is d[i][j-1].
5694def osa_row(bs: String, bp: Maybe<&2, Char>, +a: Char,
5695    +ap: Maybe<&2, Char>, +up: List<&2, Nat>, +up2: List<&2, Nat>,
5696    left: Nat) -> List<&2, Nat>:
5697  match bs:
5698    case SNil{}: Nil{}
5699    case SCon{+b, tail}:
5700      +diag = head_nat(up)
5701      +rest = tail_nats(up)
5702      +edit = Nat.min(Nat.min((head_nat(rest) + 1n : Nat), (left + 1n : Nat)),
5703        Bool.pick(Nat, Char.is_eq(a, b), diag, (diag + 1n : Nat)))
5704      +best = Bool.pick(Nat, Bool.and(same_char(bp, a), same_char(ap, b)),
5705        Nat.min(edit, (head_nat(up2) + 1n : Nat)), edit)
5706      best <> osa_row(tail, Some{b}, a, ap, rest, tail_nats(up2), best)