# Generalized matrix trace

Inspiration.

Given (by any means):

• A two-argument (or single argument consisting of a two-element list) black box function, f: ℤ+ × ℤ+ → ℤ+ (input and output are 1, 2, 3,…)
• A strictly positive integer matrix with at least two rows and two columns

return the matrix's function trace.

What is a function trace?

A normal matrix trace is the sum of the major diagonal (top-left to bottom-right) of a matrix:

[[1,2,3],[4,5,6],[7,8,9]][1,5,9]1+5+915

But instead of summing, we want to apply f along the diagonal:

[[1,2,3],[4,5,6],[7,8,9]][1,5,9]f(f(1,5),9) or f(1,f(5,9))

Please state whether you use left-to-right or right-to-left.

The given matrix and all intermediate values will be strictly positive integers within your language's integer domain. The matrix may be non-square.

### Examples

f(x,y) = xy, [[1,2,3],[4,5,6],[7,8,9]]1×5×945

f(x,y) = xy, [[1,2,3],[4,5,6],[7,8,9]]1591

f(x,y) = x-y, [[4,5,6],[1,2,3]]4-22

f(x,y) = (x+y)⁄2, [[2,3,4],[5,6,7],[8,9,10]]5 or 7

f(x,y) = x+2y, [[1,2,3],[4,5,6],[7,8,9]]47 or 29

f(x,y) = max(x,y), [[1,2,3],[4,5,6],[7,8,9]]max(1,5,9)9

f(x,y) = 2x, [[1,2,3],[4,5,6],[7,8,9]]2 or 4

f(x,y) = lcm(x,y), [[2,2,2],[2,2,3],[2,3,3],[4,4,4]]lcm(2,2,3)6

Reference implementation.

• What is the diagonal of [[2,2,2],[2,2,3],[2,3,3],[4,4,4]]? – totallyhuman Jan 24 '18 at 12:21
• @totallyhuman:[2,2,3] – Emigna Jan 24 '18 at 12:22
• Dammit, I read the title as "Generalized Matrix trance" and was sorely disappointed when the page loaded – tar Jan 25 '18 at 14:50

# R, 40 30 bytes

function(m,F)Reduce(F,diag(m))

Try it online!

Verify the test cases.

Traverses down the diagonal, so left-to-right in this case. For arithmetic operators, you can use "+" or backticks around the operators (+,*,-,%/%,^,%%)

Pretty straightforward: Reduce is R's equivalent to a fold, and the diagonal of a matrix is those elements a_ij where i==j, i.e., where the row and column indices are the same. diag has the appropriate behavior for non-square matrices.

Thanks @Laikoni for helping me fix the previously invalid solution!

f!m=foldl1 f[h|h:_<-zipWith drop[0..]m]

Associates to the left, try it online! (replace foldl1 by foldr1 for right-associative)

• how about foldl1 f$zipWith(!!)m[0..]? – proud haskeller Jan 25 '18 at 17:52 • @proudhaskeller: That's what others tried already, but that fails on non-square matrices.. – ბიმო Jan 25 '18 at 17:56 # Mathematica, 16 bytes -1 byte thanks to Martin Ender. #~Tr~Fold[g]@*0& Try it online! ## Alternate solution, 17 bytes Fold[g]@*Diagonal Try it online! • 17 bytes (black-box functions can be assumed under a given name) – Mr. Xcoder Jan 24 '18 at 13:09 • That @*{} syntax doesn't make a lot of sense (you probably meant @*List), but the fact that it works anyway is pretty cool. In fact, it means you can replace the {} with a 0 and save a byte. – Martin Ender Jan 24 '18 at 13:47 • @MartinEnder I actually did have List first but I tried {} just for the heck of it and was extremely surprised that it worked. Makes sense but how does 0 work? o0 – totallyhuman Jan 24 '18 at 14:05 • @totallyhuman The same way as {}. You're currently using {} as a function (or actually as a "head" using Mathematica terminology). If you used a generic f there, you'd get f[1,2,3] (if that's the diagonal). But with {} you get {}[1,2,3]. That's a completely meaningless expression, but heads can be arbitrary expressions themselves, and if Mathematica doesn't know what to do with them, it just leaves them as they are. Most of Mathematica's list manipulation functions actually work with expressions with an arbitrary head and in the case of Fold, the head is just ignored. [tbc] – Martin Ender Jan 24 '18 at 14:07 • So you can use 0 as the head instead, which gives 0[1,2,3] which is still meaningless, but works all the same. – Martin Ender Jan 24 '18 at 14:08 # Octave, 6157 53 bytes function m=g(f,m)for i=diag(m)'(2:end)m=f(m(1),i);end Try it online! Defines a function g which takes a function handle f and matrix m. On the first iteration, m(1) returns the top-left matrix element; after that, it just returns m. • 53 bytes – Giuseppe Jan 24 '18 at 14:55 • @Giuseppe That's what I did with my initial 61-byte version. Of course, I should've combined the strong points of my 57- and 61 byte version, which indeeds gives a 53 byte answer. Thanks for making me look at that again! – Sanchises Jan 24 '18 at 14:56 # Clean, 56 bytes t[[h:_]]f=h t[[h]:_]f=h t[[h:_]:r]f=f h(t[t\\[_:t]<-r]f) Try it online! Folds from right-to-left. [t\\[_:t]<-r] is the same as map tl r, but does not need import StdEnv. • Very elegant avoidance of StdEnv – Οurous Jan 24 '18 at 21:23 # Haskell, 4745 42 bytes f%((h:t):r)|[]<-t*>r=h|x<-tail<$>r=f h$f%x Try it online! Defines a function (%) which takes a function and a matrix as a list of lists as input. The function is folds from right-to-left: f % [[1,2,3], -> f 1 ( f % [[5,6], -> f 1 ( f 5 ( f % [[9]] ) ) -> f 1 ( f 5 ( f 9 ) ) ) [4,5,6], [8,9]] ) [7,8,9]] f % ((h:t):r) -- (h:t) is the first row and r the remaining rows | [] <- t *> r = h -- a shorter way of checking wether t==[] or r==[] | x<-tail<$>r = f h $f%x -- apply f to h and the result of recursively calling (%) on -- the remaining matrix with the first column removed Edit: -2 bytes thanks to BMO and -3 bytes thanks to Zgarb! • 43 bytes by using$ and simplifying the conditional with *>. – Zgarb Jan 24 '18 at 13:25
• @Zgarb Nice idea to use *>! – Laikoni Jan 24 '18 at 13:27

# APL (Dyalog Unicode), 7 bytes (Adám's SBCS)

⎕/1 1⍉⎕

Try it online!

-3 thanks to a suggestion to convert this to a full program by Adám.

Right-to-left.

• No need to use Adám's SBCS here: you could just use Dyalog Classic's. – Zacharý May 25 '18 at 2:30
• @Zacharý The thing is that I'm answering in Dyalog Unicode, Classic is getting deprecated over time. – Erik the Outgolfer May 25 '18 at 8:40
• Not the codepage thoughm the codepage will live on – Zacharý May 25 '18 at 14:43
• @Zacharý Well, let's rather be consistent. :P – Erik the Outgolfer May 25 '18 at 17:06

f#m=foldl1 f$zipWith(!!)m[0..length(m!!0)-1] Try it online! # Standard ML (MLton), 59 bytes fun t[h::_]f=h|t([h]::_)f=h|t((h::_)::r)f=f(h,t(map tl r)f) Try it online! Folds from right-to-left. ### Ungolfed: fun trace [h::_] f = h | trace ([h]::_) f = h | trace ((h::_)::r) f = f (h, trace (map tl r) f) Try it online! # Python 2, 61 bytes lambda f,m:reduce(f,[l[i]for i,l in enumerate(m)if len(l)>i]) Try it online! This works left-to-right. • @AsoneTuhid it can be any way, check the (x+y)⁄2 and x+2yexamples – Rod Jan 24 '18 at 14:41 • Right, I misread, sorry – Asone Tuhid Jan 24 '18 at 17:20 ## JavaScript (ES6), 58 56 bytes g=(f,a,r=a[i=0][0],e=a[++i]&&a[i][i])=>e?g(f,a,f(r,e)):r Folds left-to-right. Edit: Saved 2 bytes by using the fact that the array is strictly positive. Alternate solution, also 56 bytes: (f,a,g=r=>(e=a[++i]&&a[i][i])?g(f(r,e)):r)=>g(a[i=0][0]) • It doesn't look like you need the 1/ and you can save another 2 bytes by moving some stuff around: f=>a=>(h=r=>(e=a[++i]&&a[i][i])?h(f(r,e)):r)(a[i=0][0]). TIO – Shaggy Jan 24 '18 at 15:38 • @Shaggy Oh, it's strictly positive, I hadn't seen that. – Neil Jan 24 '18 at 17:36 • Apparently we can assume that black-box functions are assigned to a predefined variable so you could save 2 bytes if you want to take advantage of that. – Shaggy Jan 25 '18 at 11:35 • @Shaggy Actually I think it would save 4 bytes (2x f,) off the first version? – Neil Jan 25 '18 at 16:10 • You're right; sorry, forgot to count the f, when calling g again. – Shaggy Jan 25 '18 at 16:26 # JavaScript, 46 bytes f=>a=>a.reduce((p,l,i)=>l[i]?f(p[0]|p,l[i]):p) Thanks to @Shaggy, use bitwise or save one byte. That's magic. g = f=>a=>a.reduce((p,l,i)=>l[i]?f(p[0]|p,l[i]):p) c=()=>o.value=g(eval((x,y)=>${f.value}))(m.value.split(/\n/g).map(x=>x.trim().split(/\s+/).filter(v=>v.length).map(v=>+v)).filter(x=>x.length))
<p>a = <textarea id=m>1 2 3
4 5 6
7 8 9</textarea></p>
<p>f = (x, y) => <input id=f type=text value="x + y" /></p>
<p><button onclick=c()>Calc</button></p>
<p>Result = <output id=o></output></p>

• This doesn't seem to work if the matrix has more rows than columns. – Shaggy Jan 25 '18 at 10:45
• @Shaggy so sad, 47 bytes now... – tsh Jan 25 '18 at 11:01
• Yeah, that's what I had originally, too. Was just about to edit the fix into my solution but you beat me too it :( I think you can get one byte back, though, by using bitwise OR, though. – Shaggy Jan 25 '18 at 11:04
• @Shaggy so magic – tsh Jan 25 '18 at 11:09
• Forgot to mention: Apparently we can assume that black-box functions are assigned to a predefined variable so you could save 3 bytes if you wanted to take advantage of that. – Shaggy Jan 25 '18 at 15:33

# Java 8, 8881 70 bytes

m->{int r=m[0][0],i=1;try{for(;;)r=f(r,m[i][i++]);}finally{return r;}}

Folds [[1,2,3],[4,5,6],[7,8,9]] to f(f(1,5),9).

-7 bytes indirectly thanks to @KamilDrakari by using a similar trick as he did in his C# answer: instead of having a maximum boundary for the loop based on the rows/columns, simply try-catch the ArrayIndexOutOfBoundsException.
-11 bytes replacing catch(Exception e) with finally.

Try it online.

m->{int r=m[0][0],i=1;for(;i<Math.min(m.length,m[0].length);)r=f(r,m[i][i++]);return r;}

Try it online.

Explanation:

m->{                   // Method with integer-matrix parameter and integer return-type
int r=m[0][0],       //  Start the result at the integer of position 0,0 (0-indexed)
i=1;             //  Start the index at 1 (0-indexed)
try{for(;;)          //  Loop indefinitely
r=f(r,m[i][i++]);} //   Call f with the result + next diagonal cell as arguments
//   (and increase i by 1 with i++ afterwards)
finally{             //  If an ArrayIndexOutOfBoundsException occurred we're done,
return r;}}         //   in which case we return the result-integer

Black box input format:

Assumes a named function int f(int x,int y) is present, which is allowed according to this meta answer.

I have an abstract class Test containing the default function f(x,y), as well as the lambda above:

abstract class Test{
int f(int x,int y){
return x+y;
}

public java.util.function.Function<int[][],Integer>c=
m->{int r=m[0][0],i=1;for(;i<Math.min(m.length,m[0].length);)r=f(r,m[i][i++]);return r;}
;
}

For the test cases, I overwrite this function f. For example, the first test case is called like this:

System.out.println(new Test(){
@Override
int f(int x,int y){
return x*y;
}
}.c.apply(new int[][]{
new int[]{1,2,3},
new int[]{4,5,6},
new int[]{7,8,9}
}));

# Attache, 14 bytes

Fold#/Diagonal

Try it online! Set to f and call as f[function, array].

## Explanation

This is a fork of two functions: Fold and /Diagonal. This, for arguments f and a, is equivalent to:

Fold[f, (/Diagonal)[f, a]]

/, when applied monadically to a function, returns a function that is applied to its last argument. So, this is equivalent to:

Fold[f, Diagonal[a]]

This folds the function f over the main diagonal of a.

• A home-brewed language which is readable‽ – Adám Jan 25 '18 at 15:16
• @Adám ;D yes indeed! – Conor O'Brien Jan 25 '18 at 15:30

# AWK, 77 bytes

func z(F,M,r){for(e=1;e<M[1]&&e<M[2];)r=@F(r==""?M[1,1]:r,M[++e,e])
return r}

Try it online!

I was curious if AWK could do functional programming at all. I think this counts.

The "Matrix" is defined as a standard associative array, with extra fields M[1]=#rows and M[2]=#columns. The function name is passed in as a string which is evaluated via the @F(...) syntax. Evaluation is performed left to right. The r parameter is a placeholder to prevent overwriting an existing r variable and to avoid the need to reinitialize for each call. Typically extra space is added to designate such placeholders in AWK, but this is code golf, so every byte counts. :)

The TIO link implements all the test cases.

# 05AB1E, 15 10 bytes

Folds from right-to-left
Saved 5 bytes using a new built-in as suggested by Kevin Cruijssen

Å\[.g#I.V

Explanation

Works the same as the old version, except that Å\ is a new built-in for pushing the main diagonal.

Try it online! or as a Test Suite

Old Version

¬g£vyNè}[.g#I.V

Try it online! or as a Test suite

Explanation

¬                 # get the head of the input (first row)
g                # get its length (number of columns)
£               # take that many rows from input
v              # for each row_index, row (N,y) do:
y             # push the row
Nè           # get the nth element of the row
}          # end loop
[.g#      # loop until one value remain on the stack
I.V   # run the input function
• ¬g£vyNè}[ can be Å\[ now, saving 5 bytes. – Kevin Cruijssen Feb 18 '19 at 14:19

# Husk, 7 bytes

Thanks @Zgarb for fixing my submission!

Ḟ₁§z!Tŀ

Associates to the left, Try it online! (for a right-associative version simply replace by F)

### Explanation

Unfortunately there's no easy way to get the diagonal of a matrix, so most the bytes are for that:

Ḟ₁§z!Tŀ  -- function ₁ is the function and matrix A implicit, example:
§      -- fork A
T   -- | transpose A: [[1,4,7],[2,5,8],[3,6,9]]
ŀ  -- | enumerate A: [1,2,3]
z!    -- and zipWith index: [1,5,9]
Ḟ₁       -- right fold function
• Huh, built-in for anti-diagonals, but not for diagonals‽ – Adám Jan 24 '18 at 12:27
• @Adám I assume that's because you can compute antidiagonals of infinite matrices but not diagonals. – Martin Ender Jan 24 '18 at 12:29

# SNOBOL4 (CSNOBOL4), 86 bytes

T	I =1
T =M<1,1>
I	I =I + 1
T =EVAL(F '(T,M<I,I>)')	:S(I)F(RETURN)
DEFINE('T(M,F)')

Try it online!

Defines a function T (for TRACE) that takes an ARRAY and a string F that's the name of a function. Folds left-to-right.

<pre id=o></pre>

# APL NARS, 20 bytes, 10 chars

{⍺⍺/1 1⍉⍵}

test:

f←{⍺⍺/1 1⍉⍵}
⎕←q←3 3⍴⍳10
1 2 3
4 5 6
7 8 9
×f q
45
*f q
1
{⍺+2×⍵}f q
47
⌈f q
9
{2×⍺+0×⍵}f q
2
-f ⊃(4 5 6)(1 2 3)
2
{(⍺+⍵)÷2}f ⊃(2 3 4)(5 6 7)(8 9 10)
5
∧f ⊃(2 2 2)(2 2 3)(2 3 3)(4 4 4)
6

# Jelly, 5 bytes

Left-to-right.

ŒDḢç/

Try it online!

Disclaimer: I do not know if this an acceptable input method for black-box functions. This assumes that the function is implemented in the link above, and is thus "named" (that is, it's callable with) ç, but otherwise I have no way to assign it to ç. If anyone has more experience with Jelly + black box functions, I would appreciate thoughts. After spending some time in chat, we figured that using ç might indeed be valid.

## Clojure, 30 bytes

#(reduce %2(map nth %(range)))

Reduces "from the left".

# Ruby, 55 53 bytes

->f,m,n=m[i=0][0]{(k=m[i+=1]&.[]i)?(n=f[n,k];redo):n}

Try it online!