cucapra / cucapra/packet-scheduling
Remove Union Flattening
- Dominant language
- TeX
- Stars
- 9
- Forks
- 0
- Avg merge
- 9h 11m
- Merged PRs (30d)
- 27
Description
Perhaps this merits further discussion, but having gone through this a few times, I can see no genuine advantage of making the `set` type recursive. We currently have
```ocaml
type set =
| Class of clss
| Union of set list
```
I propose it to be rewritten as
```ocaml
type set =
| Class of clss
| Union of clss list
```
That is to say, `Union([Class 'A'; Union([Class 'B'; Class 'C'])])` should be treated as equivalent to `Union([Class 'A'; Class 'B'; Class 'C'])`. The latter is much easier and cleaner to work with.
Part of my work this semester involved formally proving that dequeue-side semantics for flattened unions behave the same as recursive ones (i.e., showing that the two sets I described above behave the same way). So I'd feel confident in removing that.
Contributor guide
No contributing guide indexed for this repository
Research direction
Locate the `set` type definition and all uses of `Union`. Trace how recursive and flattened unions are handled, then verify that the flattened representation preserves the stated dequeue-side semantics. Done means the recursive type is removed and the existing behavior remains equivalent.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- ocaml
- Domain
- networking
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100