# Terminating sum early

**URL:** <https://discourse.julialang.org/t/terminating-sum-early/15012>\
**Category:** General Usage\
**Tags:** question\
**Created:** [September 16, 2018, 4:23am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012 "2018-09-16T04:23:13Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 16, 2018, 4:23am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/1 "2018-09-16T04:23:13Z")

</div>

I am calculating a sum of values returned by a function, which is supposed to be type stable. The function may be costly, and returns values that are either finite or `-Inf`. In case of `-Inf`, I would like to return early.

MWE (which is of course not costly, the first version does not return early):

```julia
observation_logdensity(μ, x) = x > μ ? -abs2(x - μ) : oftype(promote(x, μ), -Inf)

sample_logdensity1(μ, xs) = sum(observation_logdensity(μ, x) for x in xs)

```

Now I am wondering how to program what I want, so that the accumulator does not change type. The function can return a `<: Real` type (in a type-stable way), especially `ForwardDiff.Dual`. I would like to have a way to figure out the accumulator type. This version does not, so the type changes inevitably:

```julia
function sample_logdensity2(μ, xs)
    total = 0 # in general, I don't know the return type of observation_logdensity
    for x in xs
        total += observation_logdensity(μ, x)
        total == -Inf && return total # terminate early
    end
    total
end

```

This version should figure it out (if `observation_logdensity` is type stable), but it is cumbersome:

```julia
function sample_logdensity3(μ, xs)
    isempty(xs) && return -Inf
    total = observation_logdensity(μ, first(xs))
    for x in Iterators.drop(xs, 1)
        total += observation_logdensity(μ, x)
        total == -Inf && return total # terminate early
    end
    total
end

```

I wonder if there is a way to write it in a more compact way idiomatically. `xs` can be any iterable.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [September 16, 2018, 6:50am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/2 "2018-09-16T06:50:07Z")

</div>

You basically need something like mapreduce with sentinel, right?

```julia
mapreduce(observation_logdensity, +, xs; sentinel=(x->x==-Inf))

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 16, 2018, 7:44am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/3 "2018-09-16T07:44:52Z")

</div>

Is this function hypothetical? I could not find this signature in `Base`.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [September 16, 2018, 7:54am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/4 "2018-09-16T07:54:06Z")

</div>

You can use a `mapreduce` with a wrapper of `+` that errors when one of the terms is not finite, otherwise adds them. Then wrap the whole thing in a `try` `catch` block.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [September 16, 2018, 7:56am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/5 "2018-09-16T07:56:55Z")

</div>

About the type of the result, you can try the solution in [KissThreading.jl/KissThreading.jl at 372a8a599d8116f09ba7c1702b1dff9169dac95c · mohamed82008/KissThreading.jl · GitHub](https://github.com/bkamins/KissThreading.jl/blob/372a8a599d8116f09ba7c1702b1dff9169dac95c/src/KissThreading.jl#L142).

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [September 16, 2018, 8:00am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/6 "2018-09-16T08:00:20Z")

</div>

Sorry! Hypotetical… I could not find it either. 😕

Maybe inspiration for enhancing or for some additional package.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 16, 2018, 8:04am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/7 "2018-09-16T08:04:31Z")

</div>

EDIT: This is probably not what you want, give me a sec.

How about

```julia
function mapreduceuntil(op, unit, xs; sentinel=(x->false))
    u = iterate(xs)
    u === nothing && error("empty reduction")
    y = unit(u[1])
    while u != nothing
        x, s = u
        sentinel(x) && break
        y = op(y, x)
        u = iterate(xs, s)
    end
    y
end

mapreduceuntil(+, zero, [1.0,2.0,Inf], sentinel=isinf)

```

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [September 16, 2018, 8:08am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/8 "2018-09-16T08:08:03Z")

</div>

> Then wrap the whole thing in a `try``catch` block.

Nooo… don’t do this please 🙂

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 16, 2018, 8:33am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/9 "2018-09-16T08:33:42Z")

</div>

Did not look carefully, but I guess you want to stop after overflow and keep `Inf` as result.

```julia
function mapreduceuntil(f, op, unit, xs; sentinel=(x->false), saturation=(y->false))
    u = iterate(xs)
    u === nothing && error("empty reduction")
  
    x, s = f(u[1]), u[2]
    y = unit(x)
    sentinel(x) && return y
    saturation(y) && return y
    y = op(x, y)
    u = iterate(xs, s)

    while u != nothing
        x, s = f(u[1]), u[2]        
        sentinel(x) && break
        saturation(y) && break
        y = op(x, y)
        u = iterate(xs, s)
    end
    y
end

mapreduceuntil(identity, +, zero, [1.0,2.0,Inf, Inf], saturation=isinf)

```

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [September 16, 2018, 9:56am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/10 "2018-09-16T09:56:23Z")

</div>

There are two separate issues here. One is to terminate a reduction early, the other is to write type-stable code that is not cumbersome.

I think Julia could reallyt from a `@typeof` macro that would compute the return type of an expression without actually evaluating it. So one could write `total = zero(@typeof(observation_logdensity(μ, first(xs))))` and that would make `sample_logdensity2` as type-stable and as fast as `sample_logdensity3`

I’m not sure if it’s possible to create such a macro in an efficient way using `Base.return_types`, or if it would require some extra magic.

---

<div class="post-metadata">

**Author:** ![improbable22](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/improbable22/32/5464_2.png) [@improbable22](https://discourse.julialang.org/u/improbable22)\
**Post date:** [September 16, 2018, 10:26am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/11 "2018-09-16T10:26:56Z")

</div>

How about this? I think it will always iterate through `xs`, but won’t call `f` once it’s hit `-Inf`:

```julia
function mysum(f::Function, xs)
    flag::Bool=true
    setflag(y) = begin y==-Inf && (flag=false); y end
    sum(setflag(f(x)) for x in xs if flag)
end

f5(x) = begin @show(x); x>5 ? -Inf : Float64(x) end

mysum(f5, 1:20) ## x = 1.0, x = 2.0, ..., x = 6.0; return -Inf

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 16, 2018, 11:45am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/12 "2018-09-16T11:45:29Z")

</div>

Very clever, thanks. But I am always unsure about generators and scoping, is this allowed?

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [September 16, 2018, 3:37pm UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/13 "2018-09-16T15:37:35Z")

</div>

Sorry to bother with nomenclature but your function is more [reduce](https://docs.julialang.org/en/v1/base/collections/#Base.reduce-Tuple%7BAny,Any%7D) than [mapreduce](https://docs.julialang.org/en/v1/base/collections/#Base.mapreduce-Tuple%7BAny,Any,Any%7D).

And Tamas needs also applying `observation_logdensity` to every element before sum it.

As doc says:

```julia
mapreduce(f, op, A::AbstractArray; dims=:, [init])

  Evaluates to the same as reduce(op, map(f, A); dims=dims, init=init), but is generally faster because the intermediate array is avoided.

```

So with your function Tamas has to write something like:

```julia
mysum(μ, xs) = mapreduceuntil(+, zero,map((x->observation_logdensity(μ, x), xs), sentinel=isinf)
mysum(μ, [1.0,2.0,Inf])

```

…which is generally slower because the intermediate array is needed.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [September 16, 2018, 3:41pm UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/14 "2018-09-16T15:41:56Z")

</div>

There is problem that `setflag` depends on partial sum and not on element.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [September 17, 2018, 7:23am UTC](https://discourse.julialang.org/t/terminating-sum-early/15012/15 "2018-09-17T07:23:33Z")

</div>

Isn’t doc is a little misleading?

> [@Liso](#):
>
> As doc says:
> 
> ```julia
> mapreduce(f, op, A::AbstractArray; dims=:, [init])
> 
> Evaluates to the same as reduce(op, map(f, A); dims=dims, init=init), 
> but is generally faster because the intermediate array is avoided.
> 
> ```

But is it true? Couldn’t we write it as:

```julia
reduce(op, f(i) for i in A; dims=dims, init=init)

```

Benchmark suggests that it is better way:

```julia
julia> @btime reduce(+, i*i for i in [1,2,3])
  36.302 ns (2 allocations: 128 bytes)
14

julia> @btime reduce(+, map(i->i*i, [1,2,3]))
  65.933 ns (3 allocations: 240 bytes)
14

```

although mapreduce still looks better:

```julia
julia> @btime mapreduce(i->i*i, +, [1,2,3])
  31.027 ns (1 allocation: 112 bytes)
14

```