[Haskell-cafe] How to define Show [MyType] ?

[Ryan Ingram]

On Sat, Dec 6, 2008 at 3:39 PM, Dmitri O.Kondratiev <dokondr at gmail.com> wrote:
> Daniel, thanks!
> I used your advice, it works, yet some more questions, if you don't mind :)
> So:
> {--
> Why showList returns a function of type:
> type ShowS = String -> String
> In fact showList returns a function which already contains all values
> from list converted to a single string.
> Why return function instead of a ready to use string?
> --}

ShowS is for efficiency; consider evaluating this:
( ( ( "1" ++ "2" ) ++ "3" ) ++ "4" ) ++ "5"

("1" ++ "2") evaluates to "12", allocating 1 list cell
("12" ++ "3") evalutes to "123", allocating 2 list cells
("123" ++ "4") evaluates to "1234", allocating 3 list cells
("1234" ++ "5") evaluates to "12345", allocating 4 list cells

In general, n left-recursive applications of ++ take O(n^2) time and space.

Now, instead, if you represent each string as a function which concatenates
itself with its argument, you end up with this: ( '1': ), ( '2': ), etc.

You can then "concatenate" these functions via function composition:
( ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) . ( '4': ) ) . ( '5': )

This is already in normal form; but watch what happens when we apply it to []:
( ( ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) . ( '4': ) ) . ( '5': ) ) ""
=> ( ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) . ( '4': ) ) "5" ,
allocating 1 cons cell
=> ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) "45", allocating 1 cons cell
=> ( ( '1': ) . ( '2':) ) "345", allocating 1 cons cell
=> ( '1': ) "2345", allocating 1 cons cell
=> "12345", allocating 1 cons cell

This has allocations and time *linear* in the number of function compositions.

> *ShowFleet> t2 fleet
> "Ship \"HMS Fly\" is a \"sloop\" with 16 cannons  <*> Ship \"HMS Surprise\" is a
>  \"frigate\" with 42 cannons  <*> "
> *ShowFleet>
>
> More questions:
> 1)Where characters \" come from in this case?
> 2)How showList function 'removes' characters \" from the output?
> What magic goes behind the scenes here?

1) They come from the "show" instance for String.  Try "putStrLn (t2
fleet)" instead.

2) There's no magic; if the result at the ghci prompt is an instance
of Show, it calls show and prints the result.

In the first case, the result was a [Fleet], which is an instance of
Show, so show is called, which
(in the instance (Show a => Show [a])) calls showList from Show Fleet,
and prints the result.

In the second case, you are evaluating a String; then showList from
Show Char gives you the representation.

It's the same as this:

ghci> [1,2,3]
[1,2,3]

ghci> show [1,2,3]
"[1,2,3]"

ghci> "hello\nworld\n"
"hello\nworld\n"

ghci> putStr "hello\nworld\n"
hello
world

  -- ryan