Re: [Haskell-cafe] Maintaining laziness
Hi,
Although it seems to be overkill for a single module - How about a cabalized version on Hackage and a darcs repository? It would simplify using and updating it.
I am not sure whether this would be a good idea. The original version makes a lot of suggestions which are not satisfiable but it is not at all trivial to decide which are satisfiable and which are not. I have rewritten StrictCheck from scratch to overcome this problem. But the current implementation is not presentable right now and I have no formal prove that the criterion that I am using is correct.
Your StrictCheck is really tough! I'm currently checking my routines from http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/ html/Data-List-HT.html which I designed especially with laziness in mind - and I found a lot of laziness breakers using StrictCheck!
However now I found an example where it probably proposes something inefficient:
So what it proposes is essentially that one should first check the length of the lists without looking at the contents. [undefined,undefined] can never be a prefix of [undefined]. However, first constructing the list spine seems to be inefficient.
I know about this problem. It is mentioned in the paper about StrictCheck. I haven't worked on this right now. With respect to least-strictness I would say the tool is right. But it is probably not the kind of advise one wants. When I am sure that I can handle the other problem I will take a look at this one. Cheers, Jan
On Mon, 12 Jan 2009, Jan Christiansen wrote:
Hi,
Although it seems to be overkill for a single module - How about a cabalized version on Hackage and a darcs repository? It would simplify using and updating it.
I am not sure whether this would be a good idea. The original version makes a lot of suggestions which are not satisfiable but it is not at all trivial to decide which are satisfiable and which are not. I have rewritten StrictCheck from scratch to overcome this problem. But the current implementation is not presentable right now and I have no formal prove that the criterion that I am using is correct.
As I said, the current version is already very useful. I have applied it to several basic functions and found a lot to improve.
Hi, Am 12.01.2009 um 14:37 schrieb Henning Thielemann:
On Mon, 12 Jan 2009, Jan Christiansen wrote:
I am not sure whether this would be a good idea. The original version makes a lot of suggestions which are not satisfiable but it is not at all trivial to decide which are satisfiable and which are not. I have rewritten StrictCheck from scratch to overcome this problem. But the current implementation is not presentable right now and I have no formal prove that the criterion that I am using is correct.
As I said, the current version is already very useful. I have applied it to several basic functions and found a lot to improve.
OK, I am sorry for my negative attitude. I just have had some negative experiences where the tool made suggestions, I implemented them and afterwards the tool made complains about another case. In fact it was not possible to fulfil both cases at all. But it was very difficult to detect these cases. I would be very interested in functions that can be improved with respect to non-strictness as test cases for my work. Cheers Jan
On Tue, 13 Jan 2009, Jan Christiansen wrote:
I would be very interested in functions that can be improved with respect to non-strictness as test cases for my work.
See the List functions in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utility-ht Version 0.0.1 was before applying StrictCheck, 0.0.2 after processing its suggestions. I have stopped when I saw that it repeatedly shows examples where I expect, that they are unresolvable.
Am 14.01.2009 um 15:26 schrieb Henning Thielemann:
See the List functions in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ utility-ht
Version 0.0.1 was before applying StrictCheck, 0.0.2 after processing its suggestions. I have stopped when I saw that it repeatedly shows examples where I expect, that they are unresolvable.
Thanks very much. Your library has provided me with an invaluable insight. The original example from the IFL paper that showed problems with lists is reverse. StrictCheck states the following You have to fulfil f _|_ = _|_ f (_|_ : _|_) = _|_ -> (_|_ : _|_) f (_|_ : []) = (_|_ : []) f (_|_ : (_|_ : _|_)) = _|_ -> (_|_ : (_|_ : _|_)) f (_|_ : (_|_ : [])) = (_|_ : (_|_ : [])) f (_|_ : (_|_ : (_|_ : _|_))) = _|_ -> (_|_ : (_|_ : (_|_ : _|_))) That is, if the argument of reverse is known to have at least 2 elements the result should have at least two elements. The only implementation I could imagine that fulfilled these requirements had a quadratic complexity. But your shorterList inspired me to an implementation that is not as efficient as the original one but which is linear. That is, there is a least strict implementation of reverse that is nearly as efficient as the standard implementation. withSpineOf :: [a] -> [a] -> [a] _ `withSpineOf` [] = [] l `withSpineOf` (_:ys) = x:xs `withSpineOf` ys where x:xs = l rev xs = reverse xs `withSpineOf` xs If anybody knows a prettier implementation of reverse that is least- strict I would be delighted to hear about it. By the way, I was wrong that your example is similar to the reverse example. My new implementation of StrictCheck states that maybePrefixOf is least strict. Cheers, Jan
participants (2)
-
Henning Thielemann -
Jan Christiansen