Solving balanced parentheses problem using Dart's type system(shilangyu.dev)

5 pointsby shilangyu3 lata temu2 comments

Solving balanced parentheses problem using Dart's type system

https://shilangyu.dev/balanced-parentheses-dart-3/

2 comments

Balanced parentheses can also be encoded in Swift or Rust.

Another way to think about the problem is that we can define a finitely-presented monoid, called the bicyclic monoid, with identity element e, two generators a and b, and the relation ab=e:

    <a, b where ab=e>

Then, ( corresponds to a and ) corresponds to b, and a string like aaababbb is balanced if it is equivalent to e via the identity element.

A finitely-presented monoid corresponds directly to a protocol declaration in Swift:

    protocol P {
        associatedtype A: P
        associatedtype B: P where A.B == Self
    }

Now you can declare a function which is generic over a type conforming to `P`:

    sameType<T>(_: T.Type, _: T.Type) {}

    func f<T: P>(_: T) {
        sameType(T.A.A.A.B.A.B.B.B.self, T.self)  // type checks
        sameType(T.B.B.A.self, T.self)  // error, not balanced
    }

The call to sameType() will type check if and only if both type arguments are equivalent.

In Rust you can similarly define a trait with two associated types and a where clause (I haven't tried it but it should work).

shilangyu3 lata temu

Nice example! Indeed, this language has a few interesting equivalent problem statements.