Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow building lists via sums and products, not just [] and :: #281

Open
byorgey opened this issue Jun 22, 2021 · 2 comments
Open

Allow building lists via sums and products, not just [] and :: #281

byorgey opened this issue Jun 22, 2021 · 2 comments

Comments

@byorgey
Copy link
Member

byorgey commented Jun 22, 2021

It seems a bit inconsistent that all other recursive types will be built directly from sums and products, and use left, right, and tuples for construction and pattern-matching, but the built-in list type has [] and :: as constructors. It's worth thinking carefully about the pedagogy here.

Probably one would introduce sets first, and set operations like sums and product, then start making recursive type definitions, using lists as a first example. In which case this could make a lot of sense. Probably we still want [x,y,z] as built-in syntax sugar, though...

@byorgey
Copy link
Member Author

byorgey commented Jun 27, 2021

Another option would be to enable the list cons operator via a language extension, but always allow building lists via more primitive sum and product types.

byorgey added a commit that referenced this issue Jun 27, 2021
The `Cons` constructor of various AST types, containing an Int and a
list of sub-things, was not pulling its weight at all:

  - The Int was always either 0 or 1
  - The list always had exactly 0, 1, or 2 things in it
  - It was wastefully used for both sums (in which case the list has exactly 1
    thing) and products (in which case the Int is always 0).

This commit changes things so that we now have separate Unit, Inj
Side, and Pair constructors. It makes things a tiny bit more
complicated with lists, since now e.g. a list cons (::) consists of an
Inj with a nested Pair, and we have to be careful to reduce both when
doing WHNF. But it also paves the way for making lists not quite
so magical; see #281 .

I was kind of hoping it might speed things up, with e.g. fewer tiny
useless lists floating around, but it didn't seem to have any
appreciable affect on the runtime of the test suite.

Also add a convenience function `vint` which is like `vnum` but
operates on an `Integer` (which is very common).
@byorgey
Copy link
Member Author

byorgey commented Mar 19, 2022

I think this is really important pedagogically, but after some thought I can't figure out how to make it work. We could simply make a synonym type List(a) = Unit + a * List(a) in a library module. List syntax sugar would continue to work since after f100fff we already represent lists this way. The thing I can't figure out is how to deal with built-in things that use container variables. So far it seems like inferring container type variables + representing List(a) as "just" a type synonym are incompatible; the problem is that it would break structural subtyping. e.g. List(N) would be a subtype of both c N and Unit + b.

@byorgey byorgey changed the title Get rid of built-in list cons operator? Allow building lists via sums and products, not just [] and :: Aug 28, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant