# skew-list: Random access lists: skew binary

This package provides ordinary random access list, `SkewList`

implemented using skew binary approach.

It's worth comparing to ordinary lists, binary random access list (as in `ral`

package) and vectors (`vector`

package)
across two operations: indexing and consing.

Consing | Indexing | |

Ordinary list, `[a]` | O(1) | O(n) |

Binary list, `RAList a` | O(log n) | O(log n) |

Vector, `Vector` | O(n) | O(1) |

Sequence, `Seq` | O(1) | O(log n) |

Skew binary list, `SkewList` | O(1) | O(log n) |

`SkewList`

improves upon ordinary list, the cons operation is still
constant time (though with higher constant factor), but indexing
can be done in a logarithmic time.

Binary list cons is slower, as it might need to walk over whole
*log n* sized structure.

`Vector`

is the other end of trade-off spectrum: indexing is constant time
operation, but consing a new element will need to copy whole spine.

`Seq`

from Data.Sequence has similar (but amortized) complexity bounds for
cons and index as `SkewList`

. However (it seems) that indexing is quicker for
`SkewList`

in practice. Also `SkewList`

has strict spine.
On the other hand, `Seq`

has quick append if you need that.

If you need both: fast consing and index, consider using `SkewList`

.

## Modules

[Index] [Quick Jump]

## Downloads

- skew-list-0.1.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

#### Maintainer's Corner

For package maintainers and hackage trustees

Candidates

- No Candidates

Versions [RSS] | 0.1 |
---|---|

Change log | ChangeLog.md |

Dependencies | base (>=4.12.0.0 && <4.21), deepseq (>=1.4.4.0 && <1.6), hashable (>=1.4.1.0 && <1.5), indexed-traversable (>=0.1.1 && <0.2), QuickCheck (>=2.14.2 && <2.16), strict (>=0.4.0.1 && <0.6) [details] |

License | BSD-3-Clause |

Copyright | (c) 2022 Oleg Grenrus |

Author | Oleg Grenrus <oleg.grenrus@iki.fi> |

Maintainer | Oleg.Grenrus <oleg.grenrus@iki.fi> |

Revised | Revision 3 made by phadej at 2024-06-15T13:27:26Z |

Category | Data |

Home page | https://github.com/phadej/skew-list |

Bug tracker | https://github.com/phadej/skew-list/issues |

Source repo | head: git clone https://github.com/phadej/skew-list.git |

Uploaded | by phadej at 2023-01-03T14:58:07Z |

Distributions | NixOS:0.1 |

Reverse Dependencies | 1 direct, 0 indirect [details] |

Downloads | 78 total (11 in the last 30 days) |

Rating | (no votes yet) [estimated by Bayesian average] |

Your Rating | |

Status | Docs available [build log] Last success reported on 2023-01-03 [all 1 reports] |