Koen Claessen <[EMAIL PROTECTED]>
proposes the following diagonalisation function:
>
> [ (a,b) | (a,b) <- [1..] // [1..] ]
>
> For a suitable definition of (//), for example:
>
> (//) :: [a] -> [b] -> [(a,b)]
> xs // ys = diagonalize 1 [[(x,y) | x <- xs] | y <- ys]
> where
> diagonalize n xss =
> xs ++ diagonalize (n+1) (xss1 ++ xss2)
> where
> (xs,xss1) = unzip [ (x,xs) | (x:xs) <- take n xss ]
> xss2 = drop n xss
>
> And it works for any type.
The core function here is
> (diagonalize (1 :: Integer)) :: [[a]] -> [a]
This function diagonalises finite or infinite lists
with arbitrary finite or infinite element lists.
To me, it seems unsatisfactory to have a solution to this pure list problem
with auxiliary functions relying on integers.
It turns out to be a nice exercise to implement
> diagonalise :: [[a]] -> [a]
without any reference to numbers.
Spoiler ahead:
I arrive at the appended version (which does not even use pairs).
Have fun!
Wolfram
====================================================================
Warning: Spoiler ahead!!
====================================================================
> diagonalise :: [[a]] -> [a]
> diagonalise = 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 [] r = f a r
> split a ([] : ls) r = split a ls r
> split a ((x:xs) : ls) r = x : split (a . (xs :)) ls r
