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

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.2.0
Change log CHANGELOG.md
Dependencies base (>=4.14.3 && <4.16), containers (>=0.6 && <0.7), contiguous (>=0.6 && <0.7), deepseq (>=1.4 && <1.5) [details]
License BSD-3-Clause
Copyright 2021 Eric Demko
Author Eric Demko
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 2022-01-28T00:45:39Z
Distributions NixOS:0.2.0
Downloads 26 total (0 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.2.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 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.

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 RList

parseSqlString :: String -> Maybe String
parseSqlString str0 = case str0 of
  '\'':rest -> loop "" rest
  _ -> Nothing
  where
  loop :: RList Char -> [Char] -> Maybe [Char]
  loop acc [] = Nothing
  -- it is impossible to accidentally return the accumulator without reversing
  loop acc "\'" = Just $ Rlist.toList acc
  loop acc ('\'':'\'':rest) = loop (Snoc acc '\'') rest
  loop acc (c:rest) = loop (Snoc acc 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.