 # Short circuiting folds

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?

1 Like

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

3 Likes

Great answer, I love to hand roll recursion.

1 Like

don’t we all 1 Like

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?
1 Like

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

1 Like

It’s called “bespoke recursion”

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.

``````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

``````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:

``````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

``````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.

3 Likes

@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` ?

1 Like

`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:

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

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

``````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]`.

1 Like

Yes.

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.

2 Likes