[Haskell-cafe] Re: Knot tying vs monads

[apfelmus]

John D. Ramsdell wrote:
> Compared to that, I'm missing the specification part for your pretty
>> printer. How's it supposed to lay out?
> 
> The specification is in Paulson's book.  The pretty printer is used with
> S-Expressions, and the block layout generates compact, indented output that
> is good when there is much data to be displayed. ... The close
> connection between the Haskell and Standard ML versions is part of the
> reason I was able to quickly generate the code, and be confident in its
> correctness.

Unfortunately, I don't have Paulson's book (or any other ML book :) at 
home. I'm too lazy to figure out the specification from the source code, 
can you provide a link or an explanation? I'm asking because I'd be 
astonished if one couldn't write an elegant Haskell version that's 
clearly correct and efficient at the same time. And such things are 
easiest to produce from scratch.

> .... a simple difference list ... will do.
> 
> Hmm.  Doesn't the output type (Int, String) -> (Int, String) show the
> implementation is using the essence of a difference list?  Remember, the
> resulting function prepends something the string it is given in the second
> element of the pair, and returns that string.

Yes, of course. But the true virtue is to disentangle it from the rest, 
i.e. to use an abstract string type with fast concatenation.

>>   Int -> (Int, String -> String)   -- difference list
> 
> My first attempt at writing the printing function had a type similar to this
> one.  I found myself composing difference lists of type ShowS.  The
> performance was noticabily slow, specially as compared with the
> implementation displayed in my message.  Perhaps the use of Data.DList would
> repair this performance problem.
> 
> I don't mean to suggest that ShowS style difference lists cannot be used to
> make the function easier to understand--all I'm saying is my attempt to do
> so did not work out well.

Dlist a = [a] -> [a]  so this would be no different from ShowS.

> 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.
> 
> I thought that the annotations ensure the first element of the list is
> evaluated.  The Char and Pretty lists are generated with seqrev, so
> everything gets evaluated before constructor is applied to data.
> 
> -- A reverse that evaluates the list elements.
> seqrev :: [a] -> [a]
> seqrev = foldl (\xs x -> x `seq` xs `seq` (x:xs)) []
> 
> The trouble is the constructors are not exported directly, but instead
> through str, brk, and blo, functions which are not strict.  It's the best I
> could do, as near as I can tell.

O_O, everything strict? But why would you ever want that?

Well if it's for "performance" reasons, I'd have to point out that the 
pretty printer has an algorithmic flaw: there are two calls to 
(breakdist es after), one from the  Brk  case and one from the  Blo 
case. The former one is safe since  breakdist  doesn't look further than 
to the next  Brk  in  es . But the latter one will lead to a quadratic 
run-time in the worst case, for example on the following input

   replicate n (Blk [Brk _] _ _)
   = [Blk [Brk _] _ _, Blk [Brk _] _ _, ..]  -- n elements

(Fill in any numbers you like for the placeholders _ ). That's a bit 
degenerate but you can spice it up with as many  Str  as you like, just 
don't add any additional  Brk .

Of course, a memoization scheme will fix this but I'd rather develop a 
new algorithm from scratch.

> It seems rather hard to avoid lazyness in the current version of Haskell
> when it's not wanted.  I hope one of the proposals for deep strictness makes
> it into Haskell prime.  In my application, there is one datastructure, such
> that if every value tracable from an instance of the datastructure is
> evaluated, I am quite sure my program will be free from memory leaks due to
> dragging.  I wish I could tell compilers to make it so.

As Derek said, strict data types are probably the easiest way to go 
here. Or you can use custom strict constructors, like

   str s = s `deepSeq` Str s

or something. But again, I don't know why you would want that at all.


Regards,
apfelmus