Skip to content
Snippets Groups Projects
  • Jakob Botsch Nielsen's avatar
    9b209c98
    More efficient list encoding for Countable · 9b209c98
    Jakob Botsch Nielsen authored and Robbert Krebbers's avatar Robbert Krebbers committed
    This changes the encoding used for finite lists of values of countable
    types to be linear instead of exponential. The encoding works by
    duplicating bits of each element so that 0 -> 00 and 1 -> 11, and then
    separating each element with 10. The top 1-bits are not kept since we
    know a 10 is starting a new element which ends with a 1.
    
    Fix #28
    9b209c98
    History
    More efficient list encoding for Countable
    Jakob Botsch Nielsen authored and Robbert Krebbers's avatar Robbert Krebbers committed
    This changes the encoding used for finite lists of values of countable
    types to be linear instead of exponential. The encoding works by
    duplicating bits of each element so that 0 -> 00 and 1 -> 11, and then
    separating each element with 10. The top 1-bits are not kept since we
    know a 10 is starting a new element which ends with a 1.
    
    Fix #28
numbers.v 28.99 KiB