Handling bounds errors safely whilst keeping a relaxed type

Learn
1

Hi all,

I’m playing around with a heap implementation, which is effectively just an array under the hood. In parts of the system I swap information around depending on the sorting requirements of the data structure:

{-| Swap data between two locations in the array.
-}
swap : Int -> Int -> Array a -> Array a
swap idx1 idx2 array =
    let
        data1 =
            unsafeGet idx1 array

        data2 =
            unsafeGet idx2 array
    in
    array |> Array.set idx1 data2 |> Array.set idx2 data1

{-| An unsafe method to get values from the array.
-}
unsafeGet : Int -> Array a -> a
unsafeGet i array =
    case Array.get i array of
        Just x ->
            x

        Nothing ->
            Debug.todo "handle this"

As you can see, my types are ANY here, which is ultimately causing problems since I can’t really return a concrete value on the Nothing path.

The rest of my implementation makes sure I don’t go out of bounds when calling this, so the Debug path is ‘never’ hit. I’d like to put this in a package though, so would ultimately like to handle the exception.

For my specific case I’ll be using an Array (List number), so I could constrict the type and return an empty list on the Nothing branch: problem solved. That doesn’t allow the function to be general & in turn this isn’t a great heap implementation.

I’ve come across this pattern a lot recently, and since 0.19 stops us from being lazy and calling Debug.crash, I’d like to learn how you would handle situations like this?

2

How about doing something like this for your swap function:

swap : Int -> Int -> Array a -> Array a
swap idx1 idx2 array =
    Array.get idx1 array
        |> Maybe.andThen
            (\val1 ->
                Array.get idx2 array
                    |> Maybe.map ((,) val1)
            )
        |> Maybe.map
            (\( val1, val2 ) ->
                ( val1, Array.set idx1 val2 array )
            )
        |> Maybe.map
            (\( val1, nextArray ) ->
                Array.set idx2 val1 nextArray
            )
        |> Maybe.withDefault array

Its a bit ugly, maybe someone can come up with a cleaner version…

At the end it supplies a default path which is just to return the original array if either of the Array.get operations fail - which should never happen if the rest of your implementation is correct.

3

This is a bit better:

swap : Int -> Int -> Array a -> Array a
swap idx1 idx2 array =
    (Maybe.map2 (,)
        (Array.get idx1 array)
        (Array.get idx2 array)
    )
        |> Maybe.map
            (\( val1, val2 ) ->
                ( val1, Array.set idx1 val2 array )
            )
        |> Maybe.map
            (\( val1, nextArray ) ->
                Array.set idx2 val1 nextArray
            )
        |> Maybe.withDefault array
1 Like
4

There is no way to implement an unsafeGet without using a Debug call or having a default value.

so you could either make unsafeGet take a default:

unsafeGet : Int -> a -> Array a -> a
unsafeGet idx default array =
    Array.get i array
        |> Maybe.withDefault default

or have swap return a default:

swap : Int -> Int -> Array a -> Array a
swap idx1 idx2 array =
    let 
        doSwap val1 val2 =
            array
                |> Array.set idx1 val2
                |> Array.set idx2 val1
    in
    Maybe.map2 doSwap
        (Array.get idx1 array)
        (Array.get idx2 array)
        |> Maybe.withDefault inputArray
1 Like
5

Thanks guys. That certainly cleared a few questions up for me.

My sticking point was trying to keep the unsafeGet method separate, as I use it in a few other places too. But really, it’s not too much of a hassle to bring it inside a let block.

Both of your solutions will help me in different ways once I extend this to the rest of the implementation.

6

This gives me an idea of a function that could be added to elm-community/dict-extra and array-extra if there was one:

swap : Int -> Int -> Array a -> Array a
swap : comparable -> comparable -> Dict comparable v -> Dict comparable v

The contract would be, the functions swaps the data values located by the keys, if the keys are both valid, otherwise it just returns the data structure unchanged. There may be other dict-like data structures where swap operations are handy.

7

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.