data-index (empty) → 0.1.0.0

raw patch · 8 files changed

+343/−0 lines, 8 filesdep +basedep +containersdep +doctestsetup-changed

Dependencies added: base, containers, doctest

Files

LICENSE +30/−0
README.md +92/−0
Setup.hs +2/−0
data-index.cabal +38/−0
src/Data/Index.hs +44/−0
src/Data/List/Index.hs +53/−0
src/Data/Sequence/Index.hs +82/−0
tests/doctests.hs +2/−0

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright Ilya Pershin here (c) 2018++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Ilya Pershin here nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ README.md view

@@ -0,0 +1,92 @@+# 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):++```haskell+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:++```haskell+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+    +```haskell+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++```haskell+(-) = 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:++```haskell+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`.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ data-index.cabal view

@@ -0,0 +1,38 @@+-- Initial data-index.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++name:                data-index+version:             0.1.0.0+synopsis:            Extending the concept of indices for lists and other containers+description:         Please see the README on GitHub at <https://github.com/Toucandy/data-index#readme>+homepage:            https://github.com/Toucandy/data-index#readme+bug-reports:         https://github.com/Toucandy/data-index/issues+license:             BSD3+license-file:        LICENSE+author:              Ilya Pershin+maintainer:          pershin2010@gmail.com+copyright:           2018 Ilya Pershin+category:            Data+build-type:          Simple+extra-source-files:  README.md+cabal-version:       >=1.10++source-repository head+  type: git+  location: https://github.com/Toucandy/data-index++library+  exposed-modules:+      Data.Index+      Data.List.Index+      Data.Sequence.Index+  build-depends:       base >=4.8 && <5.0, containers+  hs-source-dirs:      src+  default-language:    Haskell2010++test-suite doctests+  type:                exitcode-stdio-1.0+  hs-source-dirs:      tests+  main-is:             doctests.hs+  build-depends:       base, doctest >= 0.8+  default-language:    Haskell2010

+ src/Data/Index.hs view

@@ -0,0 +1,44 @@+{-# LANGUAGE Rank2Types #-}++-- | 'Index', necessary instances for it, 'end' and 'mid' for any container+module Data.Index where++import Control.Applicative+import Control.Monad++-- | This type can contain any container-independent values to be indexed with+newtype Index t i = Index {runIndex :: forall a . t a -> i}++-- | Flipped version of 'runIndex'+run :: t a -> Index t i -> i+run = flip runIndex++-- | Reader-like Monad instance+instance Monad (Index t) where+    idx >>= f = Index $ \t -> run t $ f $ run t idx++-- | Reader-like Applicative instance+instance Applicative (Index t) where+    pure i = Index (const i)+    (<*>) = ap++-- | Reader-like Functor instance+instance Functor (Index t) where+    fmap = ap . return++-- | Num instance is done via 'liftA2' and 'pure'+instance Num i => Num (Index t i) where+    (+) = liftA2 (+)+    (-) = liftA2 (-)+    (*) = liftA2 (*)+    abs = liftA abs+    signum = liftA signum+    fromInteger = pure . fromInteger++-- | The end of any linear container+end :: Foldable t => Index t Int+end = Index (\t -> length t - 1)++-- | The middle of any linear container+mid :: Foldable t => Index t Int+mid = Index (\t -> length t `div` 2)

+ src/Data/List/Index.hs view

@@ -0,0 +1,53 @@+-- | Redefined index-related functions for Data.List+module Data.List.Index (+    module Data.Index,+    module Data.List.Index+    ) where++import Data.Index+import Prelude hiding ((!!), take, drop, splitAt)+import qualified Data.List as List++-- |+-- >>> [1..7] !! 1+-- 2+-- >>> [1..7] !! end+-- 7+-- >>> [1..7] !! (end-2)+-- 5+-- >>> [1..7] !! mid+-- 4+(!!) :: [a] -> Index [] Int -> a+t !! idx = run t $ do+    i <- idx+    return $ t List.!! i++-- |+-- >>> take 10 ['a'..'z']+-- "abcdefghij"+-- >>> take (mid - 3) ['a'..'z']+-- "abcdefghij"+take :: Index [] Int -> [a] -> [a]+take idx t = run t $ do+    i <- idx+    return $ List.take i t++-- |+-- >>> drop 13 ['a'..'z']+-- "nopqrstuvwxyz"+-- >>> drop mid ['a'..'z']+-- "nopqrstuvwxyz"+drop :: Index [] Int -> [a] -> [a]+drop idx t = run t $ do+    i <- idx+    return $ List.drop i t++-- |+-- >>> splitAt mid "Hello World!"+-- ("Hello ","World!")+-- >>> splitAt (mid - 1) "Hello World!"+-- ("Hello"," World!")+splitAt :: Index [] Int -> [a] -> ([a], [a])+splitAt idx t = run t $ do+    i <- idx+    return $ List.splitAt i t

+ src/Data/Sequence/Index.hs view

@@ -0,0 +1,82 @@+-- | Redefined index-related functions for Data.Sequence+module Data.Sequence.Index (+    module Data.Index,+    module Data.Sequence.Index+    ) where++import Data.Index+import Prelude hiding (take, drop, splitAt)+import Data.Sequence (Seq)+import qualified Data.Sequence as Seq++-- |+-- >>> index (Seq.fromList [0..100]) 100+-- 100+-- >>> index (Seq.fromList [0..100]) end+-- 100+-- >>> index (Seq.fromList [0..100]) (end-4)+-- 96+-- >>> index (Seq.fromList [0..100]) 51+-- 51+-- >>> index (Seq.fromList [0..100]) (mid+1)+-- 51+index :: Seq a -> Index Seq Int -> a+index t idx = run t $ do+    i <- idx+    return $ Seq.index t i++-- |+-- >>> adjust (pred . pred) 25 (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklmnopqrstuvwxyx"+-- >>> adjust (pred . pred) end (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklmnopqrstuvwxyx"+-- >>> adjust (pred . pred) mid (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklmlopqrstuvwxyz"+-- >>> adjust (pred . pred) (mid+1) (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklmnmpqrstuvwxyz"+adjust :: (a -> a) -> Index Seq Int -> Seq a -> Seq a+adjust f idx t = run t $ do+    i <- idx+    return $ Seq.adjust f i t++-- |+-- >>> update mid '?' (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklm?opqrstuvwxyz"+-- >>> update 24 '?' (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklmnopqrstuvwx?z"+-- >>> update (end-1) '?' (Seq.fromList ['a'..'z'])+-- fromList "abcdefghijklmnopqrstuvwx?z"+update :: Index Seq Int -> a -> Seq a -> Seq a+update idx x t = run t $ do+    i <- idx+    return $ Seq.update i x t++-- |+-- >>> take 10 (Seq.fromList ['a'..'z'])+-- fromList "abcdefghij"+-- >>> take (mid - 3) (Seq.fromList ['a'..'z'])+-- fromList "abcdefghij"+take :: Index Seq Int -> Seq a -> Seq a+take idx t = run t $ do+    i <- idx+    return $ Seq.take i t++-- |+-- >>> drop 13 (Seq.fromList ['a'..'z'])+-- fromList "nopqrstuvwxyz"+-- >>> drop mid (Seq.fromList ['a'..'z'])+-- fromList "nopqrstuvwxyz"+drop :: Index Seq Int -> Seq a -> Seq a+drop idx t = run t $ do+    i <- idx+    return $ Seq.drop i t++-- |+-- >>> splitAt mid (Seq.fromList "Hello World!")+-- (fromList "Hello ",fromList "World!")+-- >>> splitAt (mid - 1) (Seq.fromList "Hello World!")+-- (fromList "Hello",fromList " World!")+splitAt :: Index Seq Int -> Seq a -> (Seq a, Seq a)+splitAt idx t = run t $ do+    i <- idx+    return $ Seq.splitAt i t

+ tests/doctests.hs view

@@ -0,0 +1,2 @@+import Test.DocTest+main = doctest ["-isrc", "src"]