Haskell report: deriving Show & Read instances, Appendix D

[Simon Peyton-Jones]

Folks

Olaf points out a problem with the specification of 'deriving' Show.
In particular:

|  "The representation will be enclosed in parentheses=20
| if the precedence of the top-level constructor operator in x=20
| is less than d."=20

Olaf proposes that we should change "less than" to "less than or equal
to".

His reasoning is below, and seems persuasive to me.  Briefly, the=20
consequences of the change would be:

a) The current specification yields syntactically incorrect Haskell for
some associativities.  The changed specification would avoid this.

b) The changed spec would yield more than the minimum number
of parentheses.

c) The current spec makes it hard for simple recursive descent
parsers, such as that suggested by the Report for Read, to avoid
divergence on left recursion. The changed spec makes it easy.

d) The downside is that all compilers would need to change, slightly.

Any comments?

Simon


| In all Haskell implementations (tested Hugs,Ghc and nhc98)=20
| show sometimes produces output that does not represent=20
| well-formed expressions. For example:
|=20
| data Tree a =3D Node a | Tree a :^: Tree a | Tree a ::: Tree a=20
|   deriving (Eq,Show)
|=20
| infixl 6 :::
| infixr 6 :^:
|=20
| main =3D print ((Node True :^: Node False) ::: Node True)
|=20
| yields
|=20
| Node True :^: Node False ::: Node True
|=20
| The expression is ill-formed because one constructor is left-=20
| and the other one is right-associative.
|=20
| Finally, left-recursive data constructors that are=20
| left-associative lead read into infinite recursion. Example:
|=20
| infixl 5 :^:
|  =20
| data Tree a =3D  Leaf a  |  Tree a :^: Tree a deriving (Show,Read)
|=20
| main =3D do
|   print (read "(Leaf True :^: Leaf False) :^: Leaf True" :: Tree Bool)
|=20
|=20
| I have a solution for the two last problems. It means all=20
| Haskell compilers have to change, but I believe that it is worth it.
|=20
| The source of the show problem is that show tries to handle=20
| associativity of infix constructors. But there is no way to=20
| do this correctly. showsPrec gets as argument the precedence=20
| of the surounding expression, but not its associativity. This=20
| associativity would be needed to use associativity of=20
| constructors correctly.
|=20
| The solution is simple: dont' try to use associativity to=20
| avoid parenthesis. Thus you get some superfluous paranthesis,=20
| but the output is always correct and the implementation of=20
| deriving is even a bit simpler. E.g.:
|=20
|         showsPrec d (u :^: v) =3D showParen (d > 5) showStr
|             where
|                showStr =3D showsPrec 6 u .=20
|                          showString " :^: " .
|                          showsPrec 6 v
| For all of
|=20
| infix 5 :^:
| infixl 5 :^:
| infixr 5 :^:
|=20
| The second advantage of this simplification is, that the=20
| additional parentheses prevent infinite left recursion. You=20
| can read in the tree expression given above, because=20
| parentheses are now compulsory:
|=20
|   instance (Read a) =3D> Read (Tree a) where
|=20
|           readsPrec d r =3D  readParen (d > 5)
|                            (\r -> [(u:^:v,w) |
|                                    (u,s) <- readsPrec 6 r,
|                                    (":^:",t) <- lex s,
|                                    (v,w) <- readsPrec 6 t]) r
|=20
|                         ++ readParen (d > 9)
|                            (\r -> [(Leaf m,t) |
|                                    ("Leaf",s) <- lex r,
|                                    (m,t) <- readsPrec 10 s]) r
|=20
| What do you think?
|=20
| Discussing all the other minor problems with the report=20
| specification doesn't make sense before this major issue is=20
| cleared up.
|=20
| Ciao,
| Olaf
|=20
| --=20
| OLAF CHITIL,=20
|  Dept. of Computer Science, The University of York, York YO10=20
| 5DD, UK.=20
|  URL: http://www.cs.york.ac.uk/~olaf/
|  Tel: +44 1904 434756; Fax: +44 1904 432767
|=20