toString for lists

Richard A. O'Keefe ok@atlas.otago.ac.nz
Tue, 1 Jun 1999 16:09:24 +1200 (NZST)


"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".

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

    :: Chars :== [Char] // Haskell actually calls this String
    :: ShowS :== Chars -> Chars

    class Show a where
       showsPrec :: Int -> a -> ShowS
       showList  :: [a] -> ShowS
       
       showList []     s = ['[':[']':s]]
       showList [x:xs] s = ['[':shows x (showl xs s)]
         where showl []     s = [']':s]
               showl [x:xs] s = [',':shows x (showl xs s)]

    show :: a -> Chars | Show a
    show x = shows x []
    
    showChar :: Char -> ShowS
    showChar c s = [c:s]
    
    showChars :: Chars -> ShowS // Haskell calls this showString
    showChars s1 s2 = s1 ++ s2

    ...

There's a bunch of other stuff, including built in rules for tuples
and an easy way to automatically derive a Show instance for a new
datatype.

Plug one more thing on top of this:

    asString :: a -> String | ShowS a
    asString x = toString (show x)

and you're away laughing, with an extensible and *efficient* way
to convert values to strings.  Haskell has a corresponding Read
class which is, um, less efficient, but still remarkably useful.

If, for example, you use Hugs for debugging your code, this
machinery is _exactly_ what Hugs uses for displaying things, and
in practice it's quite straightforward to use.