# Slightly generalised \`accumulate\`

**URL:** <https://discourse.julialang.org/t/slightly-generalised-accumulate/45039>\
**Category:** General Usage\
**Tags:** question\
**Created:** [August 16, 2020, 12:04pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039 "2020-08-16T12:04:42Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![willtebbutt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/willtebbutt/32/6790_2.png) [@willtebbutt](https://discourse.julialang.org/u/willtebbutt)\
**Post date:** [August 16, 2020, 12:04pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/1 "2020-08-16T12:04:42Z")

</div>

`accumulate` (a.k.a. `scan`, `prefix` etc) is great, but I’ve got a situation in which I need something very slightly different, and wonder whether anyone knows whether

1. it has a name
2. someone has already implemented it

Specifically, as I understand it `accumulate` eats a binary function `f` and an iterator `xs` and does something that’s roughly equivalent to (but presumably more clever than) the following:

```julia
function my_accumulate(f, xs, init)
    output = Vector{typeof(init)}(undef, length(xs))
    y = init
    for (n, x) in enumerate(xs)
        y = f(y, x)
        output[n] = y
    end
    return output
end

```

Now, I’ve got a function `g` that outputs a length 2 `Tuple` where I want to return the first element as part of `output` and pass the second on to the next iteration. Again, writing the for loop, something like this:

```julia
function not_quite_my_accumulate(g, xs, init)
    output = Vector{typeof(init)}(undef, length(xs))
    w = init
    for (n, x) in enumerate(xs)
        w, y = g(w, x)
        output[n] = y
    end
    return output
end

```

In general one _could_ implement `not_quite_my_accumulate` using `accumulate` by storing both `w` and `y` in `output` / passing them both on to the next iteration and then playing around with the result, but in my application it tends to be the case that `y` is quite small while `w` is rather large. Consequently I can’t afford to store all the intermediate values of `w`.

I couldn’t see anything about this in the docs, and I’m not sure whether it’s a function that has a name, so any advice would be much appreciated!

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 16, 2020, 12:31pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/2 "2020-08-16T12:31:55Z")

</div>

> [@willtebbutt](#):
>
> `accumulate` eats a binary function `f`

Eats a function. :😂 two-argument would be less ambiguous

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 16, 2020, 1:21pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/3 "2020-08-16T13:21:34Z")

</div>

> [@willtebbutt](#):
>
> ```julia
> function not_quite_my_accumulate(g, xs, init)
> output = Vector{typeof(init)}(undef, length(xs))
> w = init
> for (n, x) in enumerate(xs)
> w, y = g(w, x)
> output[n] = y
> end
> return output
> end
> 
> ```

Your code is quite easy to understand, I would use anything fancier. BUt sorry no help, i can’t think of a function. Others might though.

---

<div class="post-metadata">

**Author:** ![piever](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/piever/32/1815_2.png) [@piever](https://discourse.julialang.org/u/piever)\
**Post date:** [August 16, 2020, 2:11pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/4 "2020-08-16T14:11:02Z")

</div>

I guess there are a couple of tricks that can be useful. If `w` is type-stable, you could create a structure that encodes `w` and updates it as you iterate.

```julia
julia> mutable struct WithState{F, S} # somewhat similar to `Flux.Recur`
           f::F
           state::S
       end

julia> function (st::WithState)(x)
           w, y = st.f(st.state, x)
           st.state = w
           return y
       end

julia> map(WithState(g, init), xs) # not 100% sure that `map` guarantees to be run sequentially, though in practice I think it does

```

If you want to be efficient while allowing `w` to change type, you have to play around with `foldl`. For example, you could do

```julia
julia> res, _ = foldl(xs, init=(Union{}[], init)) do (vec, w), x
           ŵ, y = g(w, x)
           return push!!(vec, y), ŵ # `push!!` allows widening of the vector
       end

```

In general, playing around with the function you pass to `foldl` is a key idea for [Transducers](https://juliafolds.github.io/Transducers.jl/stable/) (or at least, that’s my understanding). Maybe the above could somehow be done as a transducer, but I don’t understand the details of the framework well enough to be sure.

---

<div class="post-metadata">

**Author:** ![willtebbutt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/willtebbutt/32/6790_2.png) [@willtebbutt](https://discourse.julialang.org/u/willtebbutt)\
**Post date:** [August 16, 2020, 2:25pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/5 "2020-08-16T14:25:43Z")

</div>

Good point – I hadn’t considered using mutation. It’s definitely an option, but I’ll hold off on marking it as a solution as a non-mutating solution would also be nice.

---

<div class="post-metadata">

**Author:** ![willtebbutt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/willtebbutt/32/6790_2.png) [@willtebbutt](https://discourse.julialang.org/u/willtebbutt)\
**Post date:** [August 16, 2020, 2:42pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/6 "2020-08-16T14:42:07Z")

</div>

Thanks for pointing me towards `Transducers.jl` – it looks like its [ScanEmit](https://juliafolds.github.io/Transducers.jl/stable/reference/manual/#Transducers.ScanEmit) transducer is actually what I want. It has roughly the same behaviour as `not_quite_my_accumulate`:

```julia
julia> not_quite_my_accumulate(tuple, 1:3, 0)
3-element Array{Int64,1}:
 1
 2
 3

julia> collect(ScanEmit(tuple, 0), 1:3)
3-element Array{Int64,1}:
 0
 1
 2

```

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [August 16, 2020, 2:56pm UTC](https://discourse.julialang.org/t/slightly-generalised-accumulate/45039/7 "2020-08-16T14:56:16Z")

</div>

You can also implement a custom iterator and keep track of the state that way. It generally only requires you overload `length` and `iterate`.

```julia
struct MyAccumulator{G, X, I<:Union{eltype(X), Nothing}}
    g::G
    xs::X
    init::I
end

MyAccumulator(g, xs) = MyAccumulator(g, xs, nothing)
Base.length(MA::MyAccumulator) = length(MA.xs)

function Base.iterate(MA::MyAccumulator{G, X, I}, state = (1, something(MA.init, one(I))))
    i, w = state
    i > length(MA.xs) && return nothing

    w, x = MA.g(w, @inbounds MA.xs[i])
    return (x, (i+1, w))
end

julia> collect(MyAccumulator((w,x) -> (w+x, w*x), [1,2,3,4]))
4-element Array{Any,1}:
  1
  4
 12
 28

```

Note that the return type is `Array{Any}` because `eltype` isn’t implemented (it’s a bit tricky since g can do anything, but you could look at how `accumulate` does it in Base to figure out a good general way).

I don’t think the interface above is necessarily the best for what you want, but maybe it can inspire a better direction.