In the meantime I have discovered a flaw in my original
diagonalisation in that it looped in finite cases.
This can easily be mended:
DiagWK1:
> diag :: [[a]] -> [a]
> diag = f id where
> f :: ([[a]] -> [[a]]) -> [[a]] -> [a]
> f a [] = split id (a []) []
> f a (l:ls) = split id (a [l]) ls
> split :: ([[a]] -> [[a]]) -> [[a]] -> [[a]] -> [a]
> split a [] [] = diag (a []) -- this line was originally missing
> split a [] r = f a r
> split a ([] : ls) r = split a ls r
> split a ((x:xs) : ls) r = x : split (a . (xs :)) ls r
Now we can eliminate f:
DiagWK2:
> diag :: [[a]] -> [a]
> diag [] = []
> diag (l:ls) = split id [l] ls
> where
> split :: ([[a]] -> [[a]]) -> [[a]] -> [[a]] -> [a]
> split a [] [] = diag (a [])
> split a [] (l:ls) = split id (a [l]) ls
> split a ([] : ls) r = split a ls r
> split a ((x:xs) : ls) r = x : split (a . (xs :)) ls r
Another, equivalent version:
DiagWk3:
> diag :: [[a]] -> [a]
> diag [] = []
> diag (l:ls) = split id [l] ls
> where
> split :: ([[a]] -> [[a]]) -> [[a]] -> [[a]] -> [a]
> split a [] ls = case ls of
> [] -> diag (a [])
> (l:ls) -> split id (a [l]) ls
> split a (l : ls) r = case l of
> [] -> split a ls r
> (x:xs) -> x : split (a . (xs :)) ls r
The timimgs are now:
20000 200000 2000000
DiagMPJ 0:00.16 0:02.32 0:37.55
DiagMPJ1 0:00.12 0:01.50 0:23.83
DiagWK1 0:00.12 0:01.34 0:19.02
DiagWK2 0:00.12 0:01.35 0:19.09
DiagWK3 0:00.12 0:01.34 0:18.82
The only thing that surprises me is
that the compiler does not do the optimization from DiagWK2 to DiagWK3 itself.
Wolfram
