src/Sequence.bend

bend-edit-distance@0.2.2.0 · 14 lines · 2 definitions

1import Base
2
3# Base.String.length builds one continuation per character on Bend 2.0.37's
4# device stack (2048 words). An accumulator keeps this traversal flat, so
5# supported 4096-byte inputs do not exhaust a lane before Myers starts.
6def length_from(sequence: String, count: Nat) -> Nat:
7  match sequence:
8    case SNil{}:
9      count
10    case SCon{_, tail}:
11      length_from(tail, 1n+count)
12
13def length(sequence: String) -> Nat:
14  length_from(sequence, 0n)