| 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.
Here's my definition of an integer free diagonalization function.
It is quite different to Wolfram's version because it doesn't
use higher-order functions as data. However, as written, I think
it is a nice example of programming with higher-order functions,
and, in particular, using function composition to construct a
pipelined program:
> diag :: [[a]] -> [a]
> diag = concat . foldr skew [] . map (map (\x -> [x]))
> where skew [] ys = ys
> skew (x:xs) ys = x : comb (++) xs ys
This uses an auxiliary function comb, which is like zipWith
except that it doesn't throw away the tail of one list when it
reaches the end of the other:
> comb :: (a -> a -> a) -> [a] -> [a] -> [a]
> comb f (x:xs) (y:ys) = f x y : comb f xs ys
> comb f [] ys = ys
> comb f xs [] = xs
Notice that there is only one recursive call in this whole
program, and that's in the implementation of comb, not in diag!
How does it work? Think of the input list of lists like this:
[ [ a1, a2, a3, ... ],
[ b1, b2, b3, ... ],
[ c1, c2, c3, ... ],
... ]
Applying map (map (\x -> [x])) to this replaces each element with
a singleton list:
[ [ [a1], [a2], [a3], ... ],
[ [b1], [b2], [b3], ... ],
[ [c1], [c2], [c3], ... ],
... ]
Next, we use (foldr skew []) to skew the picture like this:
[ [ [a1], [a2], [a3], ... ],
[ [b1], [b2], [b3], ... ],
[ [c1], [c2], [c3], ... ],
... ]
and concatenate the lists in each column:
[ [a1], [a2,b1], [a3,b2,c1], ... ]
(This is the key part, and you may need to think about it some more
to see how it actually works!) Finally, the concat function flattens
this into a single list:
[ a1, a2, b1, a3, b2, c1, ... ]
This works for any type and for any combination of finite and
infinite lists (provided, of course, that none of the lists or
tails are _|_ !)
Have fun!
Mark
