{-|
Module : Array
Description : Fast immutable arrays. The elements in an array must have the same type.
License : BSD 3
Maintainer : terezasokol@gmail.com
Stability : experimental
Portability : POSIX
Fast immutable arrays. The elements in an array must have the same type.
-}
module Array
( Array
-- * Creation
, empty, initialize, repeat, fromList
-- * Query
, isEmpty, length, get
-- * Manipulate
, set, push, append, slice
-- * Lists
, toList, toIndexedList
-- * Transform
, map, indexedMap, foldr, foldl, filter
) where
import Data.Foldable (foldl', product, sum)
import Prelude (Applicative, Char, Eq, Functor, Monad, Num, Ord, Show, flip, fromIntegral, mappend, mconcat, otherwise, pure)
import Data.Vector ((!?), (++), (//))
import Basics ((&&), (+), (-), (<), (<=), (<|), (>>), Bool, Int, clamp)
import List (List)
import Maybe (Maybe (..))
import qualified Data.Vector
import qualified Data.Foldable
import qualified Data.Maybe as HM
import qualified List as List
import qualified Tuple as Tuple
{-| An array.
-}
newtype Array a
= Array (Data.Vector.Vector a)
deriving (Eq, Show)
{-| Return an empty array.
> length empty == 0
-}
empty :: Array a
empty =
Array Data.Vector.empty
{-| Determine if an array is empty.
> isEmpty empty == True
-}
isEmpty :: Array a -> Bool
isEmpty =
unwrap >> Data.Vector.null
{-| Return the length of an array.
> length (fromList [1,2,3]) == 3
-}
length :: Array a -> Int
length =
unwrap
>> Data.Vector.length
>> fromIntegral
{-| Initialize an array. `initialize n f` creates an array of length `n` with
the element at index `i` initialized to the result of `(f i)`.
> initialize 4 identity == fromList [0,1,2,3]
> initialize 4 (\n -> n*n) == fromList [0,1,4,9]
> initialize 4 (always 0) == fromList [0,0,0,0]
-}
initialize :: Int -> (Int -> a) -> Array a
initialize n f =
Array
<| Data.Vector.generate
(fromIntegral n)
(fromIntegral >> f)
{-| Creates an array with a given length, filled with a default element.
> repeat 5 0 == fromList [0,0,0,0,0]
> repeat 3 "cat" == fromList ["cat","cat","cat"]
Notice that `repeat 3 x` is the same as `initialize 3 (always x)`.
-}
repeat :: Int -> a -> Array a
repeat n e =
Array
<| Data.Vector.replicate (fromIntegral n) e
{-| Create an array from a `List`.
-}
fromList :: List a -> Array a
fromList =
Data.Vector.fromList >> Array
{-| Return `Just` the element at the index or `Nothing` if the index is out of
range.
> get 0 (fromList [0,1,2]) == Just 0
> get 2 (fromList [0,1,2]) == Just 2
> get 5 (fromList [0,1,2]) == Nothing
> get -1 (fromList [0,1,2]) == Nothing
-}
get :: Int -> Array a -> Maybe a
get i array =
case unwrap array !? fromIntegral i of
HM.Just a -> Just a
HM.Nothing -> Nothing
{-| Set the element at a particular index. Returns an updated array.
If the index is out of range, the array is unaltered.
> set 1 7 (fromList [1,2,3]) == fromList [1,7,3]
-}
set :: Int -> a -> Array a -> Array a
set i value array =
let len = length array
vector = unwrap array
result =
if 0 <= i && i < len
then vector // [(fromIntegral i, value)]
else vector
in
Array result
{-| Push an element onto the end of an array.
> push 3 (fromList [1,2]) == fromList [1,2,3]
-}
push :: a -> Array a -> Array a
push a (Array vector) =
Array (Data.Vector.snoc vector a)
{-| Create a list of elements from an array.
> toList (fromList [3,5,8]) == [3,5,8]
-}
toList :: Array a -> List a
toList =
unwrap >> Data.Vector.toList
{-| Create an indexed list from an array. Each element of the array will be
paired with its index.
> toIndexedList (fromList ["cat","dog"]) == [(0,"cat"), (1,"dog")]
-}
toIndexedList :: Array a -> List (Int, a)
toIndexedList =
unwrap
>> Data.Vector.indexed
>> Data.Vector.toList
>> List.map (Tuple.mapFirst fromIntegral)
{-| Reduce an array from the right. Read `foldr` as fold from the right.
> foldr (+) 0 (repeat 3 5) == 15
-}
foldr :: (a -> b -> b) -> b -> Array a -> b
foldr f value array =
Data.Foldable.foldr f value (unwrap array)
{-| Reduce an array from the left. Read `foldl` as fold from the left.
> foldl (::) [] (fromList [1,2,3]) == [3,2,1]
-}
foldl :: (a -> b -> b) -> b -> Array a -> b
foldl f value array =
foldl' (flip f) value (unwrap array)
{-| Keep elements that pass the test.
> filter isEven (fromList [1,2,3,4,5,6]) == (fromList [2,4,6])
-}
filter :: (a -> Bool) -> Array a -> Array a
filter f (Array vector) =
Array (Data.Vector.filter f vector)
{-| Apply a function on every element in an array.
> map sqrt (fromList [1,4,9]) == fromList [1,2,3]
-}
map :: (a -> b) -> Array a -> Array b
map f (Array vector) =
Array (Data.Vector.map f vector)
{-| Apply a function on every element with its index as first argument.
> indexedMap (*) (fromList [5,5,5]) == fromList [0,5,10]
-}
indexedMap :: (Int -> a -> b) -> Array a -> Array b
indexedMap f (Array vector) =
Array (Data.Vector.imap (fromIntegral >> f) vector)
{-| Append two arrays to a new one.
> append (repeat 2 42) (repeat 3 81) == fromList [42,42,81,81,81]
-}
append :: Array a -> Array a -> Array a
append (Array first) (Array second) =
Array (first ++ second)
{-| Get a sub-section of an array: `(slice start end array)`. The `start` is a
zero-based index where we will start our slice. The `end` is a zero-based index
that indicates the end of the slice. The slice extracts up to but not including
`end`.
> slice 0 3 (fromList [0,1,2,3,4]) == fromList [0,1,2]
> slice 1 4 (fromList [0,1,2,3,4]) == fromList [1,2,3]
Both the `start` and `end` indexes can be negative, indicating an offset from
the end of the array.
> slice 1 -1 (fromList [0,1,2,3,4]) == fromList [1,2,3]
> slice -2 5 (fromList [0,1,2,3,4]) == fromList [3,4]
This makes it pretty easy to `pop` the last element off of an array:
`slice 0 -1 array`
-}
slice :: Int -> Int -> Array a -> Array a
slice from to (Array vector) =
let len = Data.Vector.length vector
handleNegative value = if value < 0 then len + value else value
normalize = fromIntegral >> handleNegative >> clamp 0 len
from' = normalize from
to' = normalize to
sliceLen = to' - from'
in
if sliceLen <= 0
then empty
else Array <| Data.Vector.slice from' sliceLen vector
-- INTERNAL
{-| Helper function to unwrap an array.
-}
unwrap :: Array a -> Data.Vector.Vector a
unwrap (Array v) =
v