This is an alternative site for discovering Elm packages. You may be looking for the official Elm package site instead.
1.0.0 2.0.0

CollectionsNg.Array

Fast immutable arrays. The elements in an array must have the same type.

Arrays

type alias Array a = { length : Int , nodes : Tree Int a }

Representation of fast immutable arrays. You can create arrays of integers (Array Int) or strings (Array String) or any other type of value you can dream up.

Creation

empty : Array a

Return an empty array.

length empty == 0
repeat : Int -> a -> Array a

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).

initialize : Int -> (Int -> a) -> Array a

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]
fromList : List a -> Array a

Create an array from a list.

Query

isEmpty : Array a -> Bool

Determine if an array is empty.

isEmpty empty == True
length : Array a -> Int

Return the length of an array.

length (fromList [1,2,3]) == 3
get : Int -> Array a -> Maybe a

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

Manipulate

set : Int -> a -> Array a -> Array a

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]
push : a -> Array a -> Array a

Push an element to the end of an array.

push 3 (fromList [1,2]) == fromList [1,2,3]
append : Array a -> Array a -> Array a

Append two arrays to a new one.

append (repeat 2 42) (repeat 3 81) == fromList [42,42,81,81,81]
slice : Int -> Int -> Array a -> Array a

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

Lists

toList : Array a -> List a

Create a list of elements from an array.

toList (fromList [3,5,8]) == [3,5,8]
toIndexedList : Array a -> List ( Int, a )

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")]

Transform

map : (a -> b) -> Array a -> Array b

Apply a function on every element in an array.

map sqrt (fromList [1,4,9]) == fromList [1,2,3]
indexedMap : (Int -> a -> b) -> Array a -> Array b

Apply a function on every element with its index as first argument.

indexedMap (*) (fromList [5,5,5]) == fromList [0,5,10]
filter : (a -> Bool) -> Array a -> Array a

Keep only elements that satisfy the predicate:

filter isEven (fromList [1..6]) == (fromList [2,4,6])
foldl : (a -> b -> b) -> b -> Array a -> b

Reduce an array from the left. Read foldl as fold from the left.

foldl (::) [] (fromList [1,2,3]) == [3,2,1]
foldr : (a -> b -> b) -> b -> Array a -> b

Reduce an array from the right. Read foldr as fold from the right.

foldr (+) 0 (repeat 3 5) == 15
module CollectionsNg.Array
    exposing
        ( Array
        , empty
        , isEmpty
        , length
        , initialize
        , repeat
        , fromList
        , toList
        , toIndexedList
        , push
        , get
        , set
        , foldr
        , foldl
        , append
        , filter
        , map
        , indexedMap
        , slice
        )

{-| Fast immutable arrays. The elements in an array must have the
same type.

# Arrays
@docs Array

# Creation
@docs empty, repeat, initialize, fromList

# Query
@docs isEmpty, length, get

# Manipulate
@docs set, push, append, slice

# Lists
@docs toList, toIndexedList

# Transform
@docs map, indexedMap, filter, foldl, foldr
-}

import CollectionsNg.Hamt as Hamt exposing (Tree)


{-| Representation of fast immutable arrays. You can create arrays of integers
(`Array Int`) or strings (`Array String`) or any other type of value you can
dream up.
-}
type alias Array a =
    { length : Int
    , nodes : Tree Int a
    }


{-| Return an empty array.

    length empty == 0
-}
empty : Array a
empty =
    Array 0 Hamt.empty


{-| Determine if an array is empty.

    isEmpty empty == True
-}
isEmpty : Array a -> Bool
isEmpty arr =
    arr.length == 0


{-| Return the length of an array.

    length (fromList [1,2,3]) == 3
-}
length : Array a -> Int
length arr =
    arr.length


{-| 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 stop f =
    initialize' stop 0 f empty


initialize' : Int -> Int -> (Int -> a) -> Array a -> Array a
initialize' stop idx f acc =
    if stop <= idx then
        acc
    else
        initialize' stop (idx + 1) f <| push (f idx) acc


{-| 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 =
    initialize n (always e)


{-| Create an array from a list.
-}
fromList : List a -> Array a
fromList ls =
    List.foldl push empty ls


{-| Create a list of elements from an array.

    toList (fromList [3,5,8]) == [3,5,8]
-}
toList : Array a -> List a
toList arr =
    foldr (\n acc -> n :: acc) [] arr


{-| 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 arr =
    List.map2 (,) [0..(arr.length - 1)] (toList arr)


{-| Push an element to the end of an array.

    push 3 (fromList [1,2]) == fromList [1,2,3]
-}
push : a -> Array a -> Array a
push a arr =
    { length = arr.length + 1
    , nodes = Hamt.set arr.length arr.length a arr.nodes
    }


{-| 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 idx arr =
    if idx >= arr.length || idx < 0 then
        Nothing
    else
        Hamt.get idx idx arr.nodes


{-| 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 idx val arr =
    if idx >= arr.length || idx < 0 then
        arr
    else
        { arr | nodes = Hamt.set idx idx val arr.nodes }


{-| 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 folder init arr =
    foldr' folder init (arr.length - 1) arr


foldr' : (a -> b -> b) -> b -> Int -> Array a -> b
foldr' folder acc idx arr =
    if idx == -1 then
        acc
    else
        case Hamt.get idx idx arr.nodes of
            Just x ->
                foldr' folder (folder x acc) (idx - 1) arr

            Nothing ->
                Debug.crash "This is a bug. Please report this."


{-| 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 folder init arr =
    foldl' folder init 0 arr


foldl' : (a -> b -> b) -> b -> Int -> Array a -> b
foldl' folder acc idx arr =
    if idx == arr.length then
        acc
    else
        case Hamt.get idx idx arr.nodes of
            Just x ->
                foldl' folder (folder x acc) (idx + 1) arr

            Nothing ->
                Debug.crash "This is a bug. Please report this."


{-| 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 a b =
    foldl push a b


{-| Keep only elements that satisfy the predicate:

    filter isEven (fromList [1..6]) == (fromList [2,4,6])
-}
filter : (a -> Bool) -> Array a -> Array a
filter pred arr =
    let
        update n acc =
            if pred n then
                push n acc
            else
                acc
    in
        foldl update empty arr


{-| 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 mapper arr =
    foldl (\n acc -> push (mapper n) acc) empty arr


{-| 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 mapper arr =
    indexedMap' mapper empty 0 arr


indexedMap' : (Int -> a -> b) -> Array b -> Int -> Array a -> Array b
indexedMap' mapper acc idx arr =
    if idx == arr.length then
        acc
    else
        case Hamt.get idx idx arr.nodes of
            Just x ->
                indexedMap' mapper (push (mapper idx x) acc) (idx + 1) arr

            Nothing ->
                Debug.crash "This is a bug. Please report this."


{-| 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 arr =
    let
        correctFrom =
            translateIndex from arr

        correctTo =
            translateIndex to arr
    in
        if isEmpty arr || correctFrom > correctTo then
            empty
        else
            slice' correctFrom correctTo empty arr


slice' : Int -> Int -> Array a -> Array a -> Array a
slice' from to acc arr =
    if from == to then
        acc
    else
        case Hamt.get from from arr.nodes of
            Just x ->
                slice' (from + 1) to (push x acc) arr

            Nothing ->
                Debug.crash "This is a bug. Please report this."


translateIndex : Int -> Array a -> Int
translateIndex idx arr =
    let
        posIndex =
            if idx < 0 then
                arr.length + idx
            else
                idx
    in
        if posIndex < 0 then
            0
        else if posIndex >= arr.length then
            arr.length - 1
        else
            posIndex