A module that abstracts over common collection types

Collection.elm

module Collection
    exposing
        ( Collection
        , isEmpty
        , length
        , head
        , tail
        , take
        , drop
        , slice
        , filter
        , empty
        , singleton
        , append
        , concat
        , map
        , indexedMap
        , foldl
        , foldr
        , fromList
        , toList
        , fromArray
        , toArray
        , fromMaybe
        )

{-| Collection is an abstraction over individual collection data structures. If you can't decide
whether to use a List or an Array -- well, now you don't have to.

In general this module will simply dispatch function calls to the underlying data structure, hence the
overhead should be quite minimal. There are a few exceptions, notably around `append`, which when given
a list and an array will need to pick one of these. From an API standpoint, this is invisible to you,
but there might be performance implications to this.

If you find particular functions missing from this module, it may well be an indication that you actually
need a particular collection type rather than this common subset.

Note also that we can easily add support for further collections in a minor update and you code will now magically
support these!


# Creating a collection

@docs fromList, fromArray, fromMaybe, singleton, empty


# Basics

@docs isEmpty, length, append


# Taking collections appart

@docs head, tail, take, drop, slice, filter, toList, toArray


# Mapping, folding

@docs map, indexedMap, foldl, foldr, concat

-}

import Array exposing (Array)


type Collection a
    = L (List a)
    | A (Array a)


{-| Determine if a collection is empty.

    isEmpty (fromList [])
    --> True

-}
isEmpty : Collection a -> Bool
isEmpty c =
    case c of
        L list ->
            List.isEmpty list

        A array ->
            Array.isEmpty array


{-| Determine the length of a collection.

    length (fromList [1,2,3])
    --> 3

-}
length : Collection a -> Int
length c =
    case c of
        L list ->
            List.length list

        A array ->
            Array.length array


{-| Extract the first element of a collection.

    head (fromList [1,2,3])
    --> Just 1
    head (fromList [])
    --> Nothing

-}
head : Collection a -> Maybe a
head c =
    case c of
        L list ->
            List.head list

        A array ->
            Array.get 0 array


{-| Extract the rest of the collection.

    tail (fromList [1,2,3])
    --> Just [2,3]
    tail (fromList [])
    --> Nothing

-}
tail : Collection a -> Maybe (Collection a)
tail c =
    case c of
        L list ->
            List.tail list |> Maybe.map L

        A array ->
            let
                l =
                    Array.length array
            in
                if l > 1 then
                    Array.slice 1 l array |> A |> Just
                else
                    Nothing


{-| Keep only elements that satisfy the predicate.

    filter isEven (fromList [1,2,3,4,5,6]) == [2,4,6]

-}
filter : (a -> Bool) -> Collection a -> Collection a
filter p c =
    case c of
        L list ->
            L (List.filter p list)

        A array ->
            A (Array.filter p array)


{-| Take the first n members of a collection.

    take 2 (fromList [1,2,3,4])
    --> fromList [1,2]

-}
take : Int -> Collection a -> Collection a
take count c =
    case c of
        L list ->
            L <| List.take count list

        A array ->
            Array.slice 0 count array |> A


{-| Drop the first n members of a collection.

    drop 2 (fromList [1,2,3,4])
    --> fromList [3,4]

-}
drop : Int -> Collection a -> Collection a
drop count c =
    case c of
        L list ->
            L <| List.drop count list

        A array ->
            Array.slice count (Array.length array) array |> A


{-| Get a sub-section of an collection: `(slice start end collection)`. 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 collection.

    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 collection: `slice 0 -1 collection`

-}
slice : Int -> Int -> Collection a -> Collection a
slice s e c =
    case c of
        L list ->
            let
                l =
                    List.length list

                ns =
                    if s < 0 then
                        l + s
                    else
                        s

                ne =
                    if e < 0 then
                        l + e
                    else
                        e
            in
                if ns > ne then
                    L []
                else
                    L (listSlice 0 ns ne list [])

        A array ->
            Array.slice s e array |> A


listSlice : Int -> Int -> Int -> List a -> List a -> List a
listSlice current start end list result =
    case list of
        [] ->
            List.reverse result

        x :: xs ->
            if current < start then
                listSlice (current + 1) start end xs result
            else if current < end then
                listSlice (current + 1) start end xs (x :: result)
            else
                List.reverse result


{-| Create an empty collection
-}
empty : Collection a
empty =
    L []


{-| Create a collection with only one element.
-}
singleton : a -> Collection a
singleton =
    List.singleton >> L


{-| Put two collections together.
-}
append : Collection a -> Collection a -> Collection a
append a b =
    case ( a, b ) of
        ( L al, L bl ) ->
            L (List.append al bl)

        ( A aa, A ba ) ->
            A (Array.append aa ba)

        -- See https://ellie-app.com/jwkv6n9VBa1/0
        ( L al, A ba ) ->
            A (Array.append (Array.fromList al) ba)

        ( A aa, L bl ) ->
            A (Array.append aa (Array.fromList bl))


{-| Concatenate a bunch of lists into a single list:

    concat (fromList [fromList [1,2], fromList [3], fromList [4,5]])
    --> fromList [1,2,3,4,5]

-}
concat : Collection (Collection a) -> Collection a
concat =
    foldr append empty


{-| Apply a function to every element of a collection.

    map sqrt (fromList [1,4,9])
    --> fromList [1,2,3]

    map not (fromList [True,False,True])
    --> fromList [False,True,False]

-}
map : (a -> b) -> Collection a -> Collection b
map f c =
    case c of
        L list ->
            L (List.map f list)

        A array ->
            A (Array.map f array)


{-| 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) -> Collection a -> Collection b
indexedMap f c =
    case c of
        L list ->
            L (List.indexedMap f list)

        A array ->
            A (Array.indexedMap f array)


{-| Reduce a collection from the left. Read foldl as “fold from the left”.

    foldl (::) [] (fromList [1,2,3])
    --> [3,2,1]

-}
foldl : (a -> b -> b) -> b -> Collection a -> b
foldl f d c =
    case c of
        L list ->
            List.foldl f d list

        A array ->
            Array.foldl f d array


{-| Reduce a collection from the right. Read foldl as “fold from the right”.

    foldr (+) [] (fromList [1,2,3])
    --> 6

-}
foldr : (a -> b -> b) -> b -> Collection a -> b
foldr f d c =
    case c of
        L list ->
            List.foldr f d list

        A array ->
            Array.foldr f d array


{-| Convert the collection to a list.
-}
toList : Collection a -> List a
toList c =
    case c of
        L list ->
            list

        A array ->
            Array.toList array


{-| Convert the collection to an array.
-}
toArray : Collection a -> Array a
toArray c =
    case c of
        L list ->
            Array.fromList list

        A array ->
            array


{-| Create a collection from a list
-}
fromList : List a -> Collection a
fromList =
    L


{-| Create a collection from an array
-}
fromArray : Array a -> Collection a
fromArray =
    A


{-| Create a collection from a maybe

The inverse (i.e. `toMaybe`) is called `head`.

-}
fromMaybe : Maybe a -> Collection a
fromMaybe m =
    case m of
        Just a ->
            singleton a

        Nothing ->
            empty