-
Notifications
You must be signed in to change notification settings - Fork 6
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[question] regarding disjunction #19
Comments
Hi Jean-Philippe, We met briefly at ICFP 2017. I'm also a fan of your approach! I think it's the only feasible way to do vertical concatenation / alignment, and I implemented it (or something like it) once. I have a guess as to what the exponential blowup is, and what a solution looks like. My guess is that the choice operator makes it easy to construct Docs of exponential size. For example, say you want to implement word wrap. Like format "aa, b, c, dddd, e, f" with width 5 as
So you write a combinator for it (which annoyingly needs to recurse starting at the end of the list):
This is a fairly natural thing to write, but it constructs a Doc of exponential size due to the repetition of Is that right? If so, one solution is to, instead of having a function That's pretty heavy-weight though. Maybe a lighter approach would be to introduce a new
|
FWIW, memoization is the approach that I am taking at https://github.com/sorawee/pprint-compact/blob/a685ccc315268682256a1b96e3829db7b076ec97/main.rkt#L77. The memoization table lookup could either use a hash table based on structural equality or reference equality. For the latter, the lookup cost is very cheap, but it necessitates that users must share reference instead of constructing new docs all over the place. So for now, I opt for the former. |
I read the paper. It is very clear, and I want to try it out. Unfortunately, this repository, which seems to be the canonical implementation of the algorithm described in the paper, doesn't seem to support the disjunction operator.
From #10, it looks like disjunction is removed because
Could you give me an example where the exponential behavior is triggered? As far as I can tell, it is a polynomial algorithm.
In section 9 of the paper, you said that:
Actually, I will argue that Pareto frontier + valid filtering should always give you the same O(n w^4) algorithm, same as the one in Podkopaev and Boulytchev [2014]. This is because for any (maxWidth, lastWidth), there can be only one height in the Pareto frontier. Another different value of height will either dominate or be dominated. Therefore, there are only O(w^2) configurations to consider, and therefore, in the concatenate operation, you need to consider O(w^2 * w^2) = O(w^4) combinations.
Nit: in section 4.3, the
visible
function, I thinkwhere
is missing in front ofpageWidth = 80
(sorry if this is incorrect, I haven't really used Haskell).Thanks again for the illuminating paper.
The text was updated successfully, but these errors were encountered: