Short circuiting folds

Questions
1

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
2

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

3 Likes
3

Great answer, I love to hand roll recursion.

1 Like
4

don’t we all :partying_face:

1 Like
5

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

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

1 Like
7

It’s called “bespoke recursion”

8

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 Updates or Scripts 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
9

@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
10

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
11

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 thefoldr 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
12

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