John D. Ramsdell wrote:
This is another Haskell style question.
I had some trouble with the pretty printer that comes with GHC, so I translated one written in Standard ML. I have already translated the program into C, so rewriting it in Haskell was quick and easy for me.
Concerning the choice of a pretty printer, the one bundled in GHC is close to John Hughes. The Design of a Pretty-printing Library. http://citeseer.ist.psu.edu/hughes95design.html but there's also Philip Wadler. A prettier printer. http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf (probably available as a library on hackage). Btw, both papers are marvelous introductions to the derivation of programs from their specification. Compared to that, I'm missing the specification part for your pretty printer. How's it supposed to lay out?
The Standard ML version uses a reference cell to keep track of the space available on a line. I threaded the value of the reference cell through the computation using a where clause to define two mutually recursive equations. The fixed point implicit in the where clause ties the knot in the circular definitions in a way that allows the output string to be efficiently computed front to back.
I showed the code to a colleague, who found the circular definitions opaque. He suggested a better style is to use monads, and describe the computation in a mode that is closer to its origin form in Standard ML.
What style do to you prefer, a knot-tying or a monad-based style? I have enclosed the pretty printer. The printing function is the subject of the controversy.
Neither, I think that the code mixes too many concerns. You need neither knot tying nor monads for efficient string concatenation, a simple difference list type DString = Data.DList String = String -> String will do. (There's a small difference list library Data.DList available on hackage). If ++ is too inefficient, then simply switch to a different String implementation with a faster ++. Introducing a difference list means to replace the output type (Int, String) -> (Int, String) of printing not by Int -> (String -> (Int, String)) -- state monad with state String but by Int -> (Int, String -> String) -- difference list Furthermore, I guess that this can probably be replaced by Int -> (String -> String) (Int -> Int, String -> String) or made entirely abstract type X = (Int, String) -> (Int, String) blanks :: Int -> X
blanks n (space, s) | n <= 0 = (space, s) | otherwise = blanks (n - 1) (space - 1, showChar ' ' s)
string :: String -> X string s (space,t) = (space - length s, s ++ t) or something like that. I don't know what your printer is supposed to do, so I can't say for sure.
module Pretty(Pretty, pr, blo, str, brk) where
data Pretty = Str !String | Brk !Int -- Int is the number of breakable spaces | Blo ![Pretty] !Int !Int -- First int is the indent, second int -- is the number of chars and spaces for strings and breaks in block
Drop those strictness annotations from !String and ![Pretty], they won't do any good. The !Int are only useful if they will be unboxed, but I wouldn't bother right now.
Indentation blocks
blo :: Int -> [Pretty] -> Pretty blo indent es = Blo es indent (sum es 0) where sum [] k = k sum (e:es) k = sum es (size e + k) size (Str s) = length s size (Brk n) = n size (Blo _ _ n) = n
size is of independent value, I'd make it a top-level function. Oh, and the sum won't be tail-recursive (until ghc's strictness analyzer figures it out). I'd like to point you to http://haskell.org/haskellwiki/Performance/Accumulating_parameter for an explanation of why, but the information there is rather inaccurate. For the moment, I could only find http://monad.nfshost.com/wordpress/?p=19 last section of http://blog.interlinked.org/tutorials/haskell_laziness.html but isn't there a short text that describes in detail why foldl' is different from foldl and why foldr is "better" in many cases? I thought this faq would have been cached already :) In any case, I'd simply write blo indent es = Blo es indent . sum . map size $ es ( sum is a function from the Prelude.) Regards, apfelmus