Jón Fairbairn <[EMAIL PROTECTED]> writes:
>
> > diagonalise:: [[a]] -> [a]
> > diagonalise l = d [] l
>
>
> > d [] [] = []
> > d acc [] = -- d [] acc would do, but muddles the order;
> > heads acc ++ d (rests acc) []
> > d ls (l1:rest) = heads (ls') ++ d (rests ls') rest
> > where ls' = l1: ls
>
> > heads l = [a | (a: _) <- l]
> > rests l = [as | (_: as) <- l]
>
This differs from the versions given by Mark Jones, Stefan Kahrs and myself
in that it does the diagonals ``upside down''.
However, methodologically it is actually very close to my version,
and even closer to some predecessor of that that I do not have anymore.
In fact, if I introduce into DiagWK3 the corresponding muddling avoidance,
we get:
DiagWK4:
> diag :: [[a]] -> [a]
> diag [] = []
> diag (l:ls) = split id [l] ls
> where
> split :: ([[a]] -> [[a]]) -> [[a]] -> [[a]] -> [a]
> split a [] ls = case ls of
> [] -> split id [] (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
Then a tiny change turns the diagonals ``upside down'', too:
DiagWK5:
> diag :: [[a]] -> [a]
> diag [] = []
> diag (l:ls) = split id [l] ls
> where
> split :: ([[a]] -> [[a]]) -> [[a]] -> [[a]] -> [a]
> split a [] ls = case ls of
> [] -> split id [] (a [])
> (l:ls) -> split id (l : (a [])) ls -- CHANGED!!
> split a (l : ls) r = case l of
> [] -> split a ls r
> (x:xs) -> x : split (a . (xs :)) ls r
The timing differences between DiagJF and DiagWK5 are probably
mostly due to some combination of
* the double list analysis effort in heads and rests
* and the tradeoff between lists with (++) and functions with (.).
It might be interesting to look into the compiled code in detail.
20000 200000 2000000 5000000
DiagMPJ 0:00.16 0:02.32 0:37.55 1:48.09
DiagMPJ1 0:00.12 0:01.50 0:23.83 1:06.71
DiagMPJ1a 0:00.12 0:01.47 0:23.54 1:06.04
DiagJF 0:00.13 0:01.64 0:21.85 0:57.99
DiagWK3 0:00.12 0:01.34 0:18.82 0:52.31
DiagWK4 0:00.11 0:01.33 0:19.29 0:53.22
DiagWK5 0:00.12 0:01.34 0:18.92 0:52.06
Wolfram
