reverse-list: reversed lists/snoc lists

[ bsd3, data, library ] [ Propose Tags ]

The key idea of this library is to leverage the type system to control the performance characteristics of list-manipulation code. It defines the type RList, which is a snoc-list rather than a cons-list. It also creates a symmetric module for cons-lists, which focuses on the efficient and safe use of linked lists. See README.md for more information.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.2.0, 0.3.0.0
Change log CHANGELOG.md
Dependencies base (>=4.8.2 && <4.17), containers (>=0.6 && <0.7), contiguous (>=0.6 && <0.7), deepseq (>=1.4 && <1.5) [details]
License BSD-3-Clause
Copyright 2022-2023 Marseille Bouchard
Author Marseille Bouchard
Maintainer zankoku.okuno@gmail.com
Category Data
Home page https://github.com/edemko/reverse-list
Bug tracker https://github.com/edemko/reverse-list/issues
Uploaded by edemko at 2023-02-25T14:16:43Z
Distributions NixOS:0.3.0.0
Downloads 81 total (4 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for reverse-list-0.3.0.0

[back to package description]

reverse-list

The key idea of this library is to leverage the type system to control the performance characteristics of list-manipulation code. It defines the type Tsil, which is a snoc-list rather than a cons-list. It also creates a symmetric module for cons-lists, which focuses on the efficient and safe use of linked lists.

Admittedly, parsing Strings as in this example is bad for performance anyway, but the potential bugs are the same for any use of lists as accumulators:

import qualified Data.List.Snoc as Tsil

parseSqlString :: String -> Maybe String
parseSqlString str0 = case str0 of
  '\'':rest -> loop "" rest
  _ -> Nothing
  where
  loop :: Tsil Char -> String -> Maybe (String, String)
  loop acc [] = Nothing
  loop acc ('\'':'\'':rest) = loop (acc `Snoc` '\'') rest
  -- here, it is impossible to accidentally return the accumulator without reversing:
  loop acc ('\'':rest) = Just (Tsil.toList acc, rest)
  loop acc (c:rest) = loop (acc `Snoc` c) rest

Currently, we only support the basic introduction/elimination forms (though reasonably ergonomically), and conversions. Additional functions should certainly be exposed, after due consideration is given to their semantics, including performance. If you run into anything you think deserved to be exported, open an issue or a pull request and I'll be happy to get it done.