Wolfram Kahl writes:
| 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.
IIRC a (Cantor?) diagonalisation is a bijection between the natural
numbers and the Cartesian product of finitely many countable sets
(usually 2 or more). It establishes that that Cartesian product is
also countable, e.g. to prove that the rational numbers are countable.
Using that definition I'd expect a family of diagonalisation functions
with these type signatures:
diag2 :: ([a],[b]) -> [(a,b)]
diag3 :: ([a],[b],[c]) -> [(a,b,c)]
diag4 :: ([a],[b],[c],[d]) -> [(a,b,c,d)]
...
However, assuming that a = b = c = etc., it can be generalised to:
> diag :: [[a]] -> [[a]]
... and can be implemented without relying on integers:
> diag = foldr (diag2 []) [[]] where
> diag2 zs (x:xs) ys = (zipWith (:) (x:zs) ys) ++ diag2 (x:zs) xs ys
> diag2 zs [] (_:ys) = (zipWith (:) zs ys) ++ diag2 zs [] ys
> diag2 _ _ _ = []
Part of the trick is that zs is always finite. That saves us from
getting stuck forever on any particular zip, which would in general
make some of the intended range unreachable.
I've tested it with:
diag ([] :: [[Int]])
diag ([[]] :: [[Int]])
diag [[1..4]]
diag [[1..4],[1..4]]
take 21 (diag [[1..],[1..]])
take 17 (diag (replicate 6 "-+"))
take 12 (diag [[1,2],[1..],[1..]])
take 28 (diag [[1..],[1..],[1..]])
... at which point it ceased to be fun to check by hand.
Regards,
Tom
