# Short circuiting folds

**URL:** <https://forum.canton.network/t/short-circuiting-folds/2781>\
**Category:** App Development\
**Created:** [June 29, 2021, 5:17pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781 "2021-06-29T17:17:10Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Leonid\_Rozenberg](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/leonid_rozenberg/32/48_2.png) [@Leonid\_Rozenberg](https://forum.canton.network/u/Leonid_Rozenberg)\
**Post date:** [June 29, 2021, 5:17pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/1 "2021-06-29T17:17:11Z")

</div>

Do `foldl` or `foldr` short circuit in Daml like they do in Haskell?

AFAIU, they can’t as that depends on lazy evaluation of the folded over elements. One can recover some control by introducing a short circuiting operation (ex. `if` `then` `else`, `(||)`, or `(&&)`) inside the lambda argument?

---

<div class="post-metadata">

**Author:** ![cocreature](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/cocreature/32/36_2.png) [@cocreature](https://forum.canton.network/u/cocreature)\
**Post date:** [June 29, 2021, 5:18pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/2 "2021-06-29T17:18:00Z")

</div>

There is no shortcircuiting here. If you want to shortcircuit you have to handroll your recursion.

---

<div class="post-metadata">

**Author:** ![Leonid\_Rozenberg](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/leonid_rozenberg/32/48_2.png) [@Leonid\_Rozenberg](https://forum.canton.network/u/Leonid_Rozenberg)\
**Post date:** [June 29, 2021, 5:26pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/3 "2021-06-29T17:26:04Z")

</div>

Great answer, I love to hand roll recursion.

---

<div class="post-metadata">

**Author:** ![cocreature](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/cocreature/32/36_2.png) [@cocreature](https://forum.canton.network/u/cocreature)\
**Post date:** [June 29, 2021, 5:27pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/4 "2021-06-29T17:27:29Z")

</div>

don’t we all 🥳

---

<div class="post-metadata">

**Author:** ![Leonid\_Rozenberg](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/leonid_rozenberg/32/48_2.png) [@Leonid\_Rozenberg](https://forum.canton.network/u/Leonid_Rozenberg)\
**Post date:** [June 29, 2021, 5:35pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/5 "2021-06-29T17:35:11Z")

</div>

I have two follow ups.

1. Does the Daml compiler perform tail call optimizations?
2. And now that exceptions are in the language, is there any performance benefit to using them to escape from a long call stack?

---

<div class="post-metadata">

**Author:** ![Leonid\_Rozenberg](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/leonid_rozenberg/32/48_2.png) [@Leonid\_Rozenberg](https://forum.canton.network/u/Leonid_Rozenberg)\
**Post date:** [June 29, 2021, 6:01pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/6 "2021-06-29T18:01:13Z")

</div>

I’ll split this into two separate questions, so that @cocreature can get credit for answering even more questions!

---

<div class="post-metadata">

**Author:** ![anthony](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/anthony/32/419_2.png) [@anthony](https://forum.canton.network/u/anthony)\
**Post date:** [June 29, 2021, 6:05pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/7 "2021-06-29T18:05:34Z")

</div>

> [@Leonid\_Rozenberg](#):
>
> I love to hand roll recursion.

It’s called “bespoke recursion”

---

<div class="post-metadata">

**Author:** ![Stephen](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/stephen/32/102_2.png) [@Stephen](https://forum.canton.network/u/Stephen)\
**Post date:** [June 30, 2021, 5:01pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/8 "2021-06-30T17:01:53Z")

</div>

It depends on what you mean by “short-circuiting”.

1. Not traversing the whole structure.
2. Not running the logic you’ve passed in as a lambda over the whole structure.

(1) requires you to write your own traversal over the structure, as @cocreature says. (2), however, can be solved in several interesting, generic ways.

For example, here is a short-circuit that works to short-circuit `Update`s or `Script`s run through `forA` or similar functions.

```haskell
import DA.Foldable (forA_)
import Daml.Script

newtype ShortCircuit r e m a = ShortCircuit { runSC : r -> m (Either e a) }
  deriving (Functor)

instance Action m => Applicative (ShortCircuit r e m) where
  pure = ShortCircuit . const . pure . Right
  ff <*> fa = do
    f <- ff
    f <$> fa

instance Action m => Action (ShortCircuit r e m) where
  ShortCircuit fa >>= f = ShortCircuit \r ->
    fa r >>= \case
      Left e -> pure $ Left e
      Right a -> f a `runSC` r

testSC = script do
  let folded = [1, 2, 3, 4, 5] `forA_` \n -> ShortCircuit \_ -> do
        debug ("Visiting " <> show n)
        pure $ if n == 3 then Left n else Right ()
  result <- runSC folded ()
  debug $ "final result " <> show result

```

which has the script results

```haskell
Trace: 
  "Visiting 1"
  "Visiting 2"
  "Visiting 3"
  "final result Left 3"

```

and is guaranteed to behave exactly like this for every foldable structure.

When hand-writing a `foldr`, you can take advantage of a similar phenomenon by adding another argument to the lambda you pass in:

```haskell
testFR = script do
  let shortAt z = foldr (\n r s ->
        ("visiting " <> show n) `traceRaw`
        if n == z then s else r (s + n)) identity [1, 2, 3, 4, 5]
  debug $ "with 3 " <> show (shortAt 3 0)
  debug $ "with 42 " <> show (shortAt 42 0)

```

which has the result

```haskell
Trace: 
  visiting 3
  visiting 2
  visiting 1
  "with 3 3"
  visiting 5
  visiting 4
  visiting 3
  visiting 2
  visiting 1
  "with 42 15"

```

again, I am not stopping the fold function itself from visiting every element; however, I am stopping _my own logic_ from being evaluated for each element, and this works for all foldable structures. Which may be sufficient, indeed even more convenient, than trying to satisfy the (1) short-circuiting definition.

---

<div class="post-metadata">

**Author:** ![Leonid\_Rozenberg](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/leonid_rozenberg/32/48_2.png) [@Leonid\_Rozenberg](https://forum.canton.network/u/Leonid_Rozenberg)\
**Post date:** [June 30, 2021, 6:50pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/9 "2021-06-30T18:50:50Z")

</div>

> [@Stephen](#):
>
> ```haskell
> testFR = script do
> let shortAt z = foldr (\n r s ->
> ("visiting " <> show n) `traceRaw`
> if n == z then s else r (s + n)) identity [1, 2, 3, 4, 5]
> debug $ "with 3 " <> show (shortAt 3 0)
> debug $ "with 42 " <> show (shortAt 42 0)
> 
> ```

@Stephen Can you explain how passing the extra argument to the lambda in foldr works? Naively, I think that the second argument accumulator (`b`) is a function `((Int -> Int) -> Int)` (`r` and `s`), but then I am confused as to why we only return an `Int` from the `if-then-else` ?

---

<div class="post-metadata">

**Author:** ![Stephen](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/stephen/32/102_2.png) [@Stephen](https://forum.canton.network/u/Stephen)\
**Post date:** [June 30, 2021, 9:13pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/10 "2021-06-30T21:13:06Z")

</div>

`r: Int -> Int`, `s: Int`, and the lambda returns `Int` as you noticed. So we can line that up with the abstract type of the first argument to foldr:

```haskell
a -> b -> b
Int -> (Int -> Int) -> (Int -> Int)
Int -> (Int -> Int) -> Int -> Int -- means exactly the same thing
n r s body

```

---

<div class="post-metadata">

**Author:** ![Leonid\_Rozenberg](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/leonid_rozenberg/32/48_2.png) [@Leonid\_Rozenberg](https://forum.canton.network/u/Leonid_Rozenberg)\
**Post date:** [July 1, 2021, 12:56am UTC](https://forum.canton.network/t/short-circuiting-folds/2781/11 "2021-07-01T00:56:36Z")

</div>

Thanks, I understand how the type applications work out, but now let me explain the evaluation to make sure that I fully understand what’s going on. There is a bit of an odd thing going on here as the visit tracing lines make it look like we’re folding left. Let’s shorten the list to `[1,2,3]` and evaluate `shortAt 2 0`.

The `shortAt 2` evaluates by having the`foldr` builds up the expression `f 1 (f 2 (f 3 identity))` giving us

```haskell
shortAt 2 0 -- evaluate (shortAt 2) and then f
f 1 (f 2 (f 3 identity)) 0 -- print "visiting 1", evaluate else
f 2 (f 3 identity) (0 + 1) -- print "visiting 2", evaluate then
(0 + 1)

```

Is this correct ? Are there any concerns about the build up of the nested `r` that is passed to `f` ? For example, I probably would not want to do this for a function that just sums the first 10 elements of any `[Int]`.

---

<div class="post-metadata">

**Author:** ![Stephen](https://yyz2.discourse-cdn.com/flex034/user_avatar/forum.canton.network/stephen/32/102_2.png) [@Stephen](https://forum.canton.network/u/Stephen)\
**Post date:** [July 1, 2021, 4:12pm UTC](https://forum.canton.network/t/short-circuiting-folds/2781/12 "2021-07-01T16:12:14Z")

</div>

> [@Leonid\_Rozenberg](#):
>
> Is this correct ?

Yes.

> [@Leonid\_Rozenberg](#):
>
> Are there any concerns about the build up of the nested `r` that is passed to `f` ?

I’m not usually concerned. In the vast majority of practical situations, it doesn’t matter, and what I’m really concerned about is avoiding evaluating the actual logic. Maybe it does for your use case.