CakeML / CakeML/cakeml

Implementing AList -> vector (and arrays)

Open
#1,143 1 comment 0 reactions 0 assignees View on GitHub
basis extensions
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

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**.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.