Repository: tweag/nickel (rust)

Issue:
Short-circuiting version of `fold_left`
**Is your feature request related to a problem? Please describe.**

`fold_left` is a useful combinator, and the one most often used for general iteration in functional programming (preferred over `fold_right`). However, as opposed to `fold_right`, it's not short-circuiting. For example, here is an excerpt of the implementation of `std.contract.Sequence`:

```nickel
std.array.fold_left
  (
    fun acc Contract =>
      acc
      |> match {
        'Ok value =>
          std.contract.apply_as_custom Contract label value,
        # if we encountered an error at some point in the pipeline, we
        # just forward it from this point
        error => error
      }
  )
  ('Ok value)
  contracts
```

The idea is that we want apply the contracts from the given `contracts` list as long as they don't return an error, but stop at the first error. But we have to manually match on the accumulator and propagate the short-circuiting case all-along (`error => error`), which is a bit clumsy. This isn't the only place where this takes place.

**Describe the solution you'd like**

Add a function in the stdlib that would have a signature like:

```nickel
try_fold_left: forall a b c. (a  -> c -> Result a b) -> a -> Array c -> Result a b
```

Where `Result a b := [| 'Ok a, 'Error b |]` (or something different, like `Some/None`, `Continue/Stop`, etc.). Whether it would be just sugar for the previous example, or it would use a special primop to actually be short-circuiting is an important question but even just a helper function to avoid the propagate-the-error boilerplate would be useful.

Pull request description:
Add short-circuiting fold_left
Fixes #1997, subject to bikeshedding of names.

Patch:
diff --git a/core/stdlib/std.ncl b/core/stdlib/std.ncl
index 1c5871ce..ec684639 100644
--- a/core/stdlib/std.ncl
+++ b/core/stdlib/std.ncl
@@ -297,6 +297,58 @@
           in
           go acc 0,
 
+    try_fold_left
+      : forall a b c. (a -> c -> [| 'Ok a, 'Error b |]) -> a -> Array c -> [| 'Ok a, 'Error b |]
+      | doc m%"
+          Folds a function over an array from left to right, possibly stopping early.
+
+          This differs from `fold_left` in that the function being folded returns either
+          `'Error y` (meaning that the folding should terminate, immediately returning
+          `'Error y`) or `'Ok acc` (meaning that the folding should continue as usual,
+          with the new accumulator `acc`). This early return can be used as an optimization,
+          to avoid evaluating the whole array.
+
+          # Examples
+
+          This defines a function that returns the first element satisfying a predicate.
+
+          ```nickel
+          let find_first: forall a. (a -> Bool) -> Array a -> [| 'Some a, 'None |]
+            = fun pred xs =>
+              # Our fold function, which just ignores the accumulator and immediately
+              # returns an element if it satisfies the predicate. Note that `'Error`
+              # (which is the short-circuiting branch) means that we found something.
+              let f = fun _acc x => if pred x then 'Error x else 'Ok null in
+              try_fold_left f null xs |> match {
+                'Ok _ => 'None,
+                'Error x => 'Some x,
+              }
+          in
+          let even = fun x => x % 2 == 0 in
+          find_first even [1, 3, 4, 5, 2] =>
+            'Some 4
+          ```
+        "%
+      = fun f acc array =>
+        let length = %array/length% array in
+        if length == 0 then
+          'Ok acc
+        else
+          let rec go = fun acc n =>
+            if n == length then
+              'Ok acc
+            else
+              %array/at% array n
+              |> f acc
+              |> match {
+                'Error e => 'Error e,
+                'Ok next_acc =>
+                  go next_acc (n + 1)
+                  |> %seq% next_acc
+              }
+          in
+          go acc 0,
+
     fold_right
       : forall a b. (a -> b -> b) -> b -> Array a -> b
       | doc m%"
@@ -1212,19 +1264,9 @@
         %contract/custom%
           (
             fun label value =>
-              std.array.fold_left
-                (
-                  fun acc Contract =>
-                    acc
-                    |> match {
-                      'Ok value =>
-                        std.contract.apply_as_custom Contract label value,
-                      # if we encountered an error at some point in the pipeline, we
-                      # just forward it from this point
-                      error => error
-                    }
-                )
-                ('Ok value)
+              std.array.try_fold_left
+                (fun acc Contract => std.contract.apply_as_custom Contract label acc)
+                value
                 contracts
           ),
 
@@ -1570,33 +1612,30 @@
         %contract/custom%
           (
             fun label value =>
-              std.array.fold_left
+              std.array.try_fold_left
                 (
-                  fun acc Contract =>
-                    acc
+                  fun _acc Contract =>
+                    let label =
+                      %label/with_message%
+                        "any_of: a delayed check of the picked branch failed"
+                        label
+                    in
+                    std.contract.apply_as_custom Contract label value
+                    # We want to short-circuit on contract success. Since try_fold_left
+                    # short-circuits on failure, we need to flip the two.
                     |> match {
-                      # if the previous contracts failed, we keep trying the
-                      # next
-                      'Error _ =>
-                        let label =
-                          %label/with_message%
-                            "any_of: a delayed check of the picked branch failed"
-                            label
-                        in
-                        std.contract.apply_as_custom Contract label value,
-                      # if one contract succeeded before, we just forward the
-                      # value
-                      ok => ok,
+                      'Ok value => 'Error value,
+                      'Error msg => 'Ok msg
                     }
                 )
-                ('Error {})
+                ('Ok null)
                 contracts
               |> match {
-                'Error _ =>
+                'Ok _ =>
                   'Error {
                     message = "any_of: value didn't match any of the contracts",
                   },
-                ok => ok,
+                'Error value => 'Ok value,
               }
           ),
 
diff --git a/doc/manual/contracts.md b/doc/manual/contracts.md
index 16db8a99..541cb411 100644
--- a/doc/manual/contracts.md
+++ b/doc/manual/contracts.md
@@ -296,10 +296,8 @@ in
 } | Schema
 ```
 
-`Between5And9` and `Between0And1` are awkwardly similar. Because custom
-contracts are nothing more than functions, we can use function arguments as
-parameters for contracts. Given how partial function application works,
-parameters must appear first, before the `label` and `value` arguments:
+`Between5And9` and `Between0And1` are awkwardly similar. Instead, we can use a
+single function parametrized by some arguments which returns a contract:
 
 ```nickel
 let Between = fun min max =>
@@ -323,18 +321,15 @@ in
 ### Contracts parametrized by contracts
 
 Contracts parametrized by other contracts are not really special amongst
-parametrized contracts, but note that although contracts can be built from
-functions, they can be different objects as well, such as record. Contract
-application behaves differently than bare function application. Thus, when
-manually handling another unknown contract `Contract`, do not apply it as a
-function `Contract label value`, but use `std.contract.apply Contract label
-value` or `std.contract.apply_as_custom Contract label value` instead (the
-difference between both variants is explained in the next subsection).
-
-Parameters that are also contracts are usually generic. In particular, they are
-not necessarily predicates or validators but can contain delayed checks. In
+parametrized contracts: it's just that the additional argument turns out to be a
+contract as well. Usually, a contract taking a contract parameter will
+eventually apply it, using either `std.contract.apply` or
+`std.contract.apply_as_custom` (the difference between these is explained in the
+next subsection).
+
+Parameters that are also contracts may contain delayed checks. In
 consequence, a contract parametrized by another unknown contract must usually be
-written as a [general custom contract](#general-custom-contracts) using the
+written as a [custom contract](#general-custom-contracts) as well, using the
 constructor `std.contract.custom`.
 
 One example is a `Nullable` contract, which accepts a value that is either
@@ -401,7 +396,7 @@ abort upon failure, or to proceed transparently with the evaluation of `value`.
 
 On the other hand, `std.contract.apply_as_custom` should be used in the
 situation where a parametrized contract performs some immediate checks and then
-completely transfers the execution to other contracts. This is precisely the
+completely transfers the execution to another contract. This is precisely the
 case of the `Nullable` example above:
 
 ```nickel #repl
@@ -426,20 +421,22 @@ error: contract broken by a value
 ```
 
 In this case, we do want the contract application to return either `'Ok` or
-`'Error`. Indeed, we haven't decided yet if we should return `'Ok` or not:
-`Contract` might itself returns an immediate error through `'Error` which we
-would like to propagate.
-
-Not only `apply_as_custom` spares us from wrapping the result in `'Ok`, but the
-most important benefit is to make more contract error catchable by propagating
-`'Error`. For example, with the current version, `Nullable Number` is an
-immediate contract that returns `'Error` if the value is neither `null` nor a
-`Number` (say, `"a"`). Such an immediate contract plays well with boolean
-operations on contracts, can be converted back to a predicate, etc.
-
-Had we use `std.contract.apply` in this case, this would turn the `Number`
-sub-check to a delayed check, and applying the contract to `"a"` would now throw
-an uncatchable contract error.
+`'Error`. Indeed, we don't know yet if we should return `'Ok` or not: `Contract`
+might itself returns an immediate error through `'Error` which we would like to
+bubble up as an immediate error too.
+
+`apply_as_custom` preserves immediate errors, while `apply` converts them to
+blame errors (it also spares us from wrapping the result in `'Ok` but this is
+more anecdotal). This makes more contract errors catchable.
+
+For example, with the current version, `Nullable Number` is an immediate
+contract that returns `'Error` if the value is neither `null` nor a `Number`
+(say, `"a"`). We can in particular use it with boolean contract combinators,
+such as in `std.contract.any_of [Nullable Number, String]`, with the expected
+behavior. Had we used `std.contract.apply` in this case, this would turn the
+`Number` sub-check to a delayed check, meaning that `"a" | std.contract.any_of
+[Nullable Number, String]` would now error out unduly. See [boolean
+combinators](#boolean-combinators)] for more details on `any_of`.
 
 ## Compound contracts
 
@@ -865,17 +862,17 @@ working example in this section.
 Another use-case for custom delayed contracts is to write a contract that is
 parametrized by another contract, such as the `Nullable` contract implemented in
 [the parametrized contracts section](#contracts-parametrized-by-contracts).
-Because the parameter contract is generic and can have a delayed part as well,
+Because the parameter contract is generic and can have a delayed part,
 `Nullable` needs to be written as a contract with a potential delayed part as
 well.
 
 Imagine we want to write a contract similar to `{_ | Bool}`, that is a
 dictionary of booleans, but we also want keys to be valid numbers (although
 represented as strings). A valid value could look like `{"1": true, "2": false,
-"10": true}`. If we use an immediate contract (a predicate or a validator), it's
-impossible to preserve laziness: as soon as your contract is called, you would
-need to produce a yes or no answer, and checking that fields are all `Bool`
-requires evaluating their content first.
+"10": true}`. If we use a predicate or a validator, it's impossible to preserve
+laziness: as soon as your contract is called, you would need to produce a yes or
+no answer, and checking that fields are all `Bool` requires evaluating their
+content first.
 
 What we can do is to not perform all the checks right away, but **return a new
 value which is wrapping the original value with delayed checks inside**:
@@ -888,8 +885,7 @@ value which is wrapping the original value with delayed checks inside**:
         let with_delayed_checks =
           value
           |> std.record.map
-            (
-              fun name value =>
+            (fun name value =>
                 let label_with_msg =
                   std.contract.label.with_message "field `%{name}` is not a boolean" label
                 in
@@ -929,8 +925,8 @@ then, because records (and record mapping) are lazy, *this doesn't actually
 execute the `Bool` contracts right away*. Each contract will only be run when
 the individual fields will be accessed or exported.
 
-We proceed to the immediate checks. We first check if the value is a record and
-return `'Error {..}` otherwise. Then, we iterate over all the record field
+We then proceed to the immediate checks. We first check if the value is a record
+and return `'Error {..}` otherwise. Then, we iterate over all the record field
 names and check that each one is a sequence of digits. We use a right fold
 because of its short-circuiting capabilities: as soon as an `'Error` is
 encountered, `fold_right` doesn't need to evaluate the rest and returns
@@ -943,7 +939,7 @@ We could theoretically have made the whole contact delayed by pushing the
 immediate checks down each field, together with the `Bool` contract application,
 but it's neither necessary nor desirable: as long as we don't force fields, it's
 better to perform as many checks as possible immediately, to report errors early
-and because it behaves better with respect to some contract operations.
+and because it behaves better with respect to boolean contract combinators.
 
 Let us see if we indeed preserved laziness:
 
@@ -1056,7 +1052,8 @@ Instead, it performs some of them immediately and **returns a new value, which
 is wrapping the original value with delayed checks inside**. Doing so preserves
 laziness of the language and only triggers the checks when the values are used
 or exported in a configuration. This is the reason for general custom contracts
-to have an immediate part and a delayed part.
+to return an updated value as `'Ok new_value` while validators simply return
+`'Ok`.
 
 ## Boolean combinators
 
@@ -1130,7 +1127,7 @@ default.
 
 However, if you hit this limitation, you can always decide to build a custom
 contract that will be able to discriminate between more values immediately, at
-the cost of evaluating more data immediately.
+the cost of evaluating more data.
 
 For example, consider an encoding of an enum as a record with a tag and a value:
 accepted values are records of the shape `{tag, value}` where the value is a
@@ -1142,7 +1139,7 @@ the previous section: this is equivalent to the contract `{ tag | 'String, value
 | String }`, and will reject the seemingly legal value `{ tag = 'Number, value =
 1+1 }`.
 
-The trick is to use a custom contract that will do more immediate checks. There
+The trick is to use a custom contract that performs more immediate checks. There
 are many different ways to approach this problem, depending on the specifics of
 each situation. Here, we'll write a little `Tagged` contract wrapper that takes
 a record contract, expects `tag` to exist and to be set to a fixed value, and
diff --git a/doc/manual/typing.md b/doc/manual/typing.md
index 7163ab19..8c280bc1 100644
--- a/doc/manual/typing.md
+++ b/doc/manual/typing.md
@@ -588,9 +588,9 @@ calling to the statically typed `std.array.filter` from dynamically typed code:
 ```nickel #repl
 > std.array.filter (fun x => if x % 2 == 0 then x else null) [1,2,3,4,5,6]
 error: contract broken by the caller of `filter`
-    ┌─ <stdlib/std.ncl>:377:25
+    ┌─ <stdlib/std.ncl>:429:25
     │
-377 │       : forall a. (a -> Bool) -> Array a -> Array a
+429 │       : forall a. (a -> Bool) -> Array a -> Array a
     │                         ---- expected return type of a function provided by the caller
     │
     ┌─ <repl-input-6>:1:55


Test patch:
diff --git a/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_reversed_indices.ncl.snap b/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_reversed_indices.ncl.snap
index 2ba94fc5..423b2001 100644
--- a/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_reversed_indices.ncl.snap
+++ b/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_reversed_indices.ncl.snap
@@ -4,9 +4,9 @@ expression: err
 ---
 error: contract broken by the caller of `range`
        invalid range
-    ┌─ <stdlib/std.ncl>:705:9
+    ┌─ <stdlib/std.ncl>:757:9
     │
-705 │       | std.contract.unstable.RangeFun Dyn
+757 │       | std.contract.unstable.RangeFun Dyn
     │         ---------------------------------- expected type
     │
     ┌─ [INPUTS_PATH]/errors/array_range_reversed_indices.ncl:3:19
diff --git a/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_step_negative_step.ncl.snap b/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_step_negative_step.ncl.snap
index 621bed3b..2d1ed5e2 100644
--- a/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_step_negative_step.ncl.snap
+++ b/cli/tests/snapshot/snapshots/snapshot__eval_stderr_array_range_step_negative_step.ncl.snap
@@ -4,9 +4,9 @@ expression: err
 ---
 error: contract broken by the caller of `range_step`
        invalid range step
-    ┌─ <stdlib/std.ncl>:680:9
+    ┌─ <stdlib/std.ncl>:732:9
     │
-680 │       | std.contract.unstable.RangeFun (std.contract.unstable.RangeStep -> Dyn)
+732 │       | std.contract.unstable.RangeFun (std.contract.unstable.RangeStep -> Dyn)
     │         ----------------------------------------------------------------------- expected type
     │
     ┌─ [INPUTS_PATH]/errors/array_range_step_negative_step.ncl:3:27