Skip to content

Implementing AList -> vector (and arrays) #1143

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

Open
tanyongkiam opened this issue Mar 14, 2025 · 0 comments
Open

Implementing AList -> vector (and arrays) #1143

tanyongkiam opened this issue Mar 14, 2025 · 0 comments

Comments

@tanyongkiam
Copy link
Contributor

This issue is about implementing an efficient conversion of 'a alist indexed by num into a 'a vector.

The length of the resulting vector can be left implementation-dependent, but should be long enough to hold the entire alist (in particular, it could just be the max element + 1).

This conversion is very useful when the alist is constructed then frequently looked up. This lookup operation ought to be done in O(1).

One can use this conversion to give 'a sptree fast lookups as well.

The efficient path to such a conversion is as follows:

  1. Set up an array that can hold all the elements
  2. Fill the array up
  3. primitively convert the array into a vector

Steps 1 and 2 can already be done.

The challenging part of this issue is to add the primitive operation to CakeML that converts an array into vector without copying the array.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant