# Why is multiplication A\*B\*C left-associative (\`foldl\`) not right-associative (\`foldr\`)?

**URL:** <https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552>\
**Category:** General Usage\
**Tags:** question\
**Created:** [November 15, 2018, 8:52am UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552 "2018-11-15T08:52:07Z")\
**Posts on this page:** 12\
**Page:** 2

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [November 15, 2018, 3:26pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/21 "2018-11-15T15:26:33Z")

</div>

I would say this is very worthwhile and probably the right way to go, but am weary of it using `*`. It would be nice to have to prototyped in v1.0 using a different operator.

---

<div class="post-metadata">

**Author:** ![dlfivefifty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlfivefifty/32/1959_2.png) [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)\
**Post date:** [November 15, 2018, 3:36pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/22 "2018-11-15T15:36:38Z")

</div>

I actually had it left-associative at first. I think I’ll do this:

1. Have _both_ `leftmaterialize` and `rightmaterialize`
2. `materialize(M::Mul) = leftmaterialize(M)`
3. `M*x` lowers to `materialize(Mul(M.factors..., x))` and is _slow_ and _unadvised_
4. `M⋆x` lowers to `rightmaterialize(Mul(M.factors..., x))` and is fast.

Weak Laplacians can still be written `Δ = B'D'D*B`, as the construction of the operators works fine either case.

---

<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:** [November 15, 2018, 3:41pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/23 "2018-11-15T15:41:36Z")

</div>

> [@dlfivefifty](#):
>
> Yes I normally just use parentheses, but I have a use case where there is a need for long sequences of operations, which requiring parentheses is error prone.

What about something like this?

```julia
julia> reduce(
           (x,y)->begin 
              println("I am doing $y*$x");
              y*x;
           end, 
           reverse(
           "abcd" # here I simulate array of matrices/vectors ;)
           ))
I am doing c*d
I am doing b*cd
I am doing a*bcd
"abcd"

```

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [November 15, 2018, 3:42pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/24 "2018-11-15T15:42:34Z")

</div>

You can also make use of [https://github.com/AustinPrivett/MatrixChainMultiply.jl](https://github.com/AustinPrivett/MatrixChainMultiply.jl) for an optimal `materialize` as the default? This works on any matrices, and would end up doing the `rightmaterialize` in an `A*B*v`.

---

<div class="post-metadata">

**Author:** ![fhenneke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fhenneke/32/2211_2.png) [@fhenneke](https://discourse.julialang.org/u/fhenneke)\
**Post date:** [November 15, 2018, 3:57pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/25 "2018-11-15T15:57:22Z")

</div>

As another data point, [https://github.com/Jutho/LinearMaps.jl](https://github.com/Jutho/LinearMaps.jl) uses lazy right to left evaluation for products of `LinearMap`s.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [November 16, 2018, 9:31pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/26 "2018-11-16T21:31:04Z")

</div>

That’s also our approach in [LinearOperators.jl](https://github.com/JuliaSmoothOptimizers/LinearOperators.jl).

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [November 17, 2018, 9:09am UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/27 "2018-11-17T09:09:02Z")

</div>

BTW, `*` in Julia’s AST do not say it’s left- or right-associative:

```julia
julia> dump(:(1 * 2 * 3))
Expr
  head: Symbol call
  args: Array{Any}((4,))
    1: Symbol *
    2: Int64 1
    3: Int64 2
    4: Int64 3

```

(I found that it’s strange. Why is that?)

So it’s easy to get right-associative `*` a la future-import (provided you do it before any use of `*`):

```julia
julia> module RightAssociative
       *(a) = Base.:*(a)
       *(a, b) = Base.:*(a, b)
       *(args...) = *(args[1:end-2]..., *(args[end-1], args[end]))
       end
Main.RightAssociative

julia> using .RightAssociative: *

julia> Base.:*(x::Symbol, y) = Symbol("($x * $y)")

julia> :a * :b * :c
Symbol("(a * (b * c))")

```

where the result of the last output would be `Symbol("((a * b) * c)")` without `using .RightAssociative: *`.

---

<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:** [November 17, 2018, 11:03am UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/28 "2018-11-17T11:03:21Z")

</div>

> [@tkf](#):
>
> (I found that it’s strange. Why is that?)

I just guess: you could for example multiply 3 matrices without intermediate allocation? (So it looks to me rather beautiful than strange)

```julia
julia> import Base.*

julia> *(a,b,c) = a+b+c
* (generic function with 344 methods)

julia> 3*4 == 3*4*5
true

```

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [November 17, 2018, 4:53pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/29 "2018-11-17T16:53:21Z")

</div>

One could define `function Base.:*(args::Vararg{AbstractArray,N}) where N` to choose the optimal order based on `size`s (maybe dispatch on `DenseArray`).

Why isn’t `LinearAlgebra` doing that?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [November 17, 2018, 6:55pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/30 "2018-11-17T18:55:33Z")

</div>

> [@foobar\_lv2](#):
>
> choose the optimal order based on `size` s

I can see the point. But you can do the same argument for any (potentially) associative binary operators like function composition. I felt puzzling because it seems this representation is used only for `*` and `+` AFAICT:

```julia
julia> dump(:(a + b + c))
Expr
  head: Symbol call
  args: Array{Any}((4,))
    1: Symbol +
    2: Symbol a
    3: Symbol b
    4: Symbol c

julia> dump(:(a - b - c))
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol -
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol -
        2: Symbol a
        3: Symbol b
    3: Symbol c

julia> dump(:(a ∘ b ∘ c))
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol ∘
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol ∘
        2: Symbol a
        3: Symbol b
    3: Symbol c

```

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [November 17, 2018, 7:00pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/31 "2018-11-17T19:00:10Z")

</div>

> [@tkf](#):
>
> only for `*` and `+` AFAICT

Looking at the parser, it’s used for `++` as well:

> <https://github.com/JuliaLang/julia/blob/90e3155fc41ee9cf6ebefe1aeb2cb77d7c37bcfa/src/julia-parser.scm#L903-L904>

---

<div class="post-metadata">

**Author:** ![dlfivefifty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlfivefifty/32/1959_2.png) [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)\
**Post date:** [November 17, 2018, 7:22pm UTC](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552/32 "2018-11-17T19:22:19Z")

</div>

> [@foobar\_lv2](#):
>
> We already have \circ = `∘` for a right-associative multiplication with the correct intuition

On second thought, (linear) operators are really “functions of vectors” (at least in their mathematical definition), so the mathematical notation ABCx is actually shorthand for `(A∘B∘C)(x)`, _not_ `A*B*C*x`…

[Previous page](https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552.md?page=1)