@hackage data-index0.1.0.0

Extending the concept of indices for lists and other containers

What is it?

This is an attempt to rethink the concept of list indexing, implemented in Haskell. Here are some examples (do cabal install before it):

Prelude> import Data.List.Index as LI
Prelude LI> [1..7] LI.!! 1
2
Prelude LI> [1..7] LI.!! end
7
Prelude LI> [1..7] LI.!! (end-2)
5
Prelude LI> [1..7] LI.!! mid
4
Prelude LI> LI.drop 13 ['a'..'z']
"nopqrstuvwxyz"
Prelude LI> LI.drop mid ['a'..'z']
"nopqrstuvwxyz"
Prelude LI> LI.splitAt mid "Hello World!"
("Hello ","World!")
Prelude LI> LI.splitAt (mid - 1) "Hello World!"
("Hello"," World!")

Why would someone need this?

Well, there already are a few of programming languages in which one can access lists from their end, rather than from the beginning.

  • Some of them use a negative index (e.g. Python, Perl) like a[-2]. It's not safe way though, because this approach may disguise an error of violating lists' range.
  • The others use a special keyword or a symbol (e.g. Tcl, Matlab, Julia, D) like a[end-1]. It's a good option, although it requires support from the language syntax.

Other programming languages do not have such a feature. This package data-index tries to get it done for Haskell in a rather peculiar way.

  1. The required functionality is added as a library, in contrast with patching the syntax
  2. Not only an access from the end of a list is added, but also an access from any user-defined place, i.e. from the middle.

How is this done?

The concept of a list index was invented anew. What is an access to a list by index anyway? Well, this is a function of two arguments that takes a list and a some abstract place, and returns a value from the place. This place must be defined in a list-independent way. These are examples of such places: the third element from the beginning, the second element from the end, the middle. That's how it can be done:

newtype Index i = Index (forall a . [a] -> i)
idx   = Index (\t -> 2)                -- third element from the beginning
idx'  = Index (\t -> length t - 2)     -- second element from the end
idx'' = Index (\t -> length t `div` 2) -- the middle

One can notice that with such a definition, Index turns out to be something very similar to Reader monad, saving forall. Furthermore, "classical" indices from the beginning become pure indices, in virtue of

pure i = Index (const i)

New Index is Num instance as well, allowing using not only t !! end, but also t !! (end-2) or t !! 1, due to

(-) = liftA2 (-)
fromInteger = pure . fromInteger

Functions redefining

The only problem is to make functions to work with new Index instead of Int. At present this is getting done by manual redefining each needed function via do-notation, because I don't know how to do it better. Container polymorphism is also done, so the actual definition of Index is:

newtype Index t i = Index {runIndex :: forall a . t a -> i}

Therefore, for each necessary container t corresponding functions working with indices as Int have to be redefined to functions working with Index t Int. Until now this is done for Data.List and Data.Sequence, but it's easy to implement Index for any linear container, e.g. Vector.