Hi,
you write (message from Tom Pledger on Thu, 15 Jul 1999 13:33:06 +1200 (NZT))
(and I hope you do not mind that I send this response to the list, too):
>
> Someone was saying that my diag function ran out of space, but I've
> lost track of the message. Was it yours?
>
Yes, it was mine.
> Anyway, just in case it was, here's what I suspect happened:
>
> > diagMJ :: [[a]] -> [a]
> > diagWK :: [[a]] -> [a]
> > diagTP :: [[a]] -> [[a]]
>
> The following are comparable tests:
>
> > diagMJ [[(x,y) | x <- [1..]] | y <- [1..]]
> > diagWK [[(x,y) | x <- [1..]] | y <- [1..]]
> > diagTP [[1..],[1..]]
>
> This, on the other hand, represents a diag problem in infinitely many
> dimensions
Now I understand the point of your definition! Nice!
For the sake of completeness, here is that definition again:
> diagTP :: [[a]] -> [[a]]
> diagTP = foldr (diag2 []) [[]] where
> diag2 [] [] _ = []
> diag2 _ _ [] = []
> diag2 zs (x:xs) ys = (zipWith (:) (x:zs) ys) ++ diag2 (x:zs) xs ys
> diag2 zs [] (_:ys) = (zipWith (:) zs ys) ++ diag2 zs [] ys
Sorry I did not really look into it before!
So, relating to what has been discussed on the list in the meantime,
your definition generalises
> (//) :: [a] -> [b] -> [(a,b)]
to any finite number of arguments, i.e., dimensions,
something which is not so easy to achieve with the
> diag :: [[a]] -> [a]
approach that has the number of dimensions in its typing.
> and AFAIK *must* run out of something:
>
> > diagTP [[(x,y) | x <- [1..]] | y <- [1..]]
>
So I should diagonalise over that result ;-^)
> test1 = diagWK (diagTP [[(x,y) | y <- [0..]] | x <- [0..]])
Unfortunately even that loops.
This is because your definition has to insist on
finding the last element of ys before returning a first element.
There is, of course, the fundamental problem in here that
there are more infinite lists of natural numbers than fit
even into an infinite list of lists of natural numbers.
Therefore we have to abandon some of our expectations.
Something we still may try to achieve, however,
is a version of diagTP that accepts infinite lists as arguments,
and then returns, in a certain sense, *as many inifinite lists as possible*,
i.e., a function
> diagINF :: [[a]] -> [[a]]
such that (with any diag from diagMPJ, diagSK, diagJF, diagWK)
> test2 = diag (map prefixes (diagINF (repeat [0..])))
eventually reaches every finite sequence of natural numbers
(the problem NOT being test2 itself, but diagINF!)
with
> prefixes [] = [[]]
> prefixes (x:xs) = [] : map (x:) (prefixes xs)
I hope it will be sufficient to restrict argument lists for diagINF
to contain only NONEMPTY lists.
It may be easier to demand that all element lists are infinite.
It should, however, not be relevant whether the argument list itself
is finite or not, or should it?
Best regards,
Wolfram
