How does Array.Extra.all short circuit?

Learn
1

I got curious to see if Array.Extra.all short circuits on the first False.

I’ve used Debug.log to trace what happens. As can be seen in the logs in my Ellie experiment Array.Extra.all do short circuit on the first False.

Looking at the source for Array.Extra.all:

  • it uses Array.foldl
  • which uses JsArray.fold
  • which uses a Javascript for loop to calculate the final accumulator value.

It is not obvious to me how this short circuits. Is there some underlying Javascript optimisation that discovers that the accumulator will stay False once it becomes False in the for loop? If yes, how does it work? If no, what is it that makes it possible to short circuit?

1 Like
2

I think the accumulator soFar becomes False and then the expression soFar && isOkay element never evaluates the isOkay element bit sionce && short circuits. But it will still loop over the entire array, all the way to the end.

You could experiement by changing the all code to:

all : (element -> Bool) -> (Array element -> Bool)
all isOkay =
    Array.foldl
        (\element soFar -> isOkay element && soFar)
        True

Then running that through your Ellie.

3

Thank you @rupert!

This makes perfekt sense. The && operator short circuits but not the foldl itself.

I got curious in the first place, since folds usually have not way of short circuiting. But, since I only introduced log messages in the ìsOkay function I wrongly got the impression of the whole Array.Extra.all short circuiting.

4

If I really want/need a short circuit version of Array.Extra.all I guess I will have roll my own recursive function like this:

all : (a -> Bool) -> Array a -> Bool
all isOkay array =
    let
        step index =
            case Array.get index array |> Maybe.map isOkay of
                Just True ->
                    step (index + 1)

                Just False ->
                    False

                Nothing ->
                    True
    in
    step 0
5

Turns out this has already been tested and evaluated by the Array.Extra developers. Since arrays in Elm are implemented using som kind of trees (for sharing of immutable data) array look up in Elm is not O(1). Read more here.

6

You can always write a version of fold that has an optional break in it:

type Next a = Cont a | Break a

foldl : (a -> b -> Next b) -> b -> List a -> b
foldl fn acc vals =
    case vals of 
        [] -> acc
        v :: vs -> 
            case fn v ac of
                Cont newAcc -> foldl fn newAcc vs
                Break newAcc -> newAcc
1 Like
7

Yea. for List there’s stoppableFold.

2 Likes
8

With Arrays I iterated over a slice using Array.get:

This was used to implement a GapBuffer for a text editor. I certainly found that doing it this way was efficient enough to get a UI that scrolled smoothly. But yes, the Array.get access is O(Log n), so not as fast as it could be:

Demo: https://kind-colden-ebafc2.netlify.app/

1 Like
9

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