Hi all,
since I have gotten into the habit to relate proposed diagonalisation
function, I will not resist this time, either ;-)
Koen Claessen <[EMAIL PROTECTED]> writes:
>
> as // bs = diag [] [ [ (a,b) | a <- as] | b <- bs ]
>
> diag current [] = diag [] current
> diag current (new : pending) = heads ++ diag (new : tails) pending
> where
> (heads,tails) = unzip [ (c,cs) | (c:cs) <- current ]
>
> I thought it was short and sweet :-)
It is. At a price, though:
Just as my first versions, it does not terminate in finite cases; try:
take 20 (diag [] [[3..],[1,2]])
Otherwise, it is in the class of ``upside-down diagonals'':
Main> take 20 (diag [] [[(x,y) | y <- [0..] ] | x <- [0..]])
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)
,(4,0),(3,1),(2,2),(1,3),(0,4),(5,0),(4,1),(3,2),(2,3),(1,4)]
and is very close to the variant of J�n Fairbairn:
> diag:: [[a]] -> [a]
> diag 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]
The second line of J�n Fairbairn's ``d'' handles termination;
this is what is missing in Koen Claessen's solution.
Koen Claessen's ``new'' is analysed one round earlier
in J�n Fairbairn's solution (and also in my corresponding solution DiagWK5).
The pairs in Koen Claessen's solution seem to be more expensive than
the double anaysis in J�n Fairbairn's solution:
20000 200000 2000000 5000000
DiagKC 0:00.14 0:01.73 0:24.27 1:05.41
DiagJF 0:00.13 0:01.64 0:21.85 0:57.99
DiagWK5 0:00.12 0:01.34 0:18.92 0:52.06
The infinite dimensional problem is also quite fun --- I think I shall try
to accumulate some more interesting stuff in this direction and then
set out to condense it in some form suitable for publication,
perhaps even as a Functional Programming Pearl.
Wolfram
