toString for lists

G.P.H. Josten gjosten@sci.kun.nl
Tue, 1 Jun 1999 09:42:44 +0200 (MET DST)


On Tue, 1 Jun 1999, Richard A. O'Keefe wrote:

> "G.W.M. Vissers" <vissers@theochem.kun.nl> wrote:
> 	
> 	I was doing some debugging when I noticed how unfortunate the
> 	standard toString for lists is.   This toString function is
> 	defined in StdList as:
> 
>     instance toString [x] | toChar x
>         where
>         toString::![x] -> {#Char} | toChar x
>         toString xs = ltosacc xs ""
>             where
>             ltosacc [h:t] acc = ltosacc t (acc +++ toString (toChar h))
>             ltosacc []    acc = acc
> 	
> 	The problem is that this method only works for lists of elements
> 	that can be converted into characters.
> 
> That's not the only problem.  Unless the Clean system is doing some
> heavy-duty magic underneath, building a string of N characters will
> take O(N**2) time this way.  I would have expected
> 
>         toString :: ![x] -> {#Char} | toChar x
>         toString xs = {toChar x \\ x <- xs}
> 
> which requires O(N) intermediate storage while you wait to find out
> how big the string is going to be, but should take O(N) time overall.
> (Does it?  Just what _does_ clean do with array comprehensions?)
> Just to put some numbers on this, I compiled and ran the following
> program:
> 
> 	module Foo
> 	import StdEnv
> 	
> 	sawtooth 0 c = []
> 	sawtooth n c = [c : sawtooth (n-1) (if (c == 122) 97 (c+1))
> 
> 	test = sawtooth 20000 97
> 
> 	Start = size (tostring test)
> 
> On an 84MHz SPARCstation 5, this took 0.14 seconds, and scaled linearly.
> Change one character, getting
> 
> 	Start = size (toString test)
> 
> and the test took 7.2 seconds, scaling quadratically.
> 
> 	For most types a toString is predefined, but
> 	not a toChar.
> 
> That's right; _this_ one is just the toString for Char lists and Int lists.
> 
> 	 Besides I don't see the use of first converting the element
> 	into a character, and then making a string out of it. Would'n it be a lot
> 	easier to convert the elemnts of the list into Strings directly, like:
> 	
> 	instance toString [x] | toString x       
> 	 where
> 	        toString::![x] -> {#Char} | toString x
> 	        toString xs = ltosacc xs ""
> 	        where
> 	                ltosacc [h:t] acc = ltosacc t (acc +++ toString h)
> 	                ltosacc []        acc = acc
> 	
> That would have even *worse* runtime performance than the poor one we
> already have, and in any case it is not what you want for debugging.
> For debugging, you would like [1,2,3] to be turned into "[1,2,3]",
> but the code you've offered would produce "123".
> 


For debugging purposes, the function called 'trace' has been implemented.
This can (??) be used to dump your result from any location in the code to
screen, the same way as Clean does at the end of your program...

> What you want is what Haskell has.  Haskell has a typeclass
Show.
> 

*snip*

Greetings,
Geert