random-access-lists

Random Access Lists
-------------------

This is an implementation of Random Access Lists, as described by
David Van Horn in SRFI-101: Purely Functional Random Access Pairs and
Lists.  

I've ported this library to Common Lisp but it is otherwise his work,
and is distributed under the same terms as that implementation:

>  SRFI 101: Purely Functional Random-Access Pairs and Lists
>  Copyright (c) David Van Horn 2009.  All Rights Reserved.
>
>  Permission is hereby granted, free of charge, to any person obtaining
>  a copy of this software and associated documentation
>  files (the "Software"), to deal in the Software without restriction,
>  including without limitation the rights to use, copy, modify, merge,
>  publish, distribute, sublicense, and/or sell copies of the Software,
>  and to permit persons to whom the Software is furnished to do so,
>  subject to the following conditions:
>
>  The above copyright notice and this permission notice shall be
>  included in all copies or substantial portions of the Software.
>
>  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
>  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
>  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
>  NONINFRINGEMENT. REMEMBER, THERE IS NO SCHEME UNDERGROUND. IN NO EVENT
>  SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
>  DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
>  OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
>  THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Random Access Lists are a persistent data structure with `O(1)` `cons`,
`car`, `cdr`, and so forth but with much better performance for random
access and random persistent update, `O(log(n))`.

Usage:
------

Creation: 

    (ra-list 1 2 3 4) ; -> #S(PL-CONS
      :SIZE 1
      :TREE 1
      :REST #S(PL-CONS ...))

Access:

    (setq r (ra-list 1 2 3 4))
    (ra-list-ref r 2) -> 3
    (ra-car r) -> 1
    (ra-cdr r) -> #S(PL-CONS :SIZE 3 :TREE #S(PL-NODE ...))

Update:

    (ra-list-ref (ra-list-set r 2 100) 2) -> 100
    (ra-list-ref r 2) -> 3

Updates are _persistent_, in that they do not change previous version
of the list.  They merely return a new list with the updated value in
place.

Many functions of the `ra-caddr`, `ra-cddr`, etc are also provided
along with basic list manipulation functions like `ra-map`.
    

random-access-lists

Upstream URL

Author

Maintainer

License

random-access-lists

Version:

Authors:

Maintainers:

Dependencies:

Dependencies (1)

Dependents (1)