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.
- The required functionality is added as a library, in contrast with patching
the syntax
- 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.
