[Haskell-cafe] Comments and suggestions on code

[Jonathan Cast]

On 11 Jan 2008, at 7:27 AM, Andre Nathan wrote:

> On Thu, 2008-01-10 at 20:37 -0800, Jonathan Cast wrote:
>> It might be faster; laziness usually has higher constants than direct
>> implementations.  But I doubt the difference is critical in this
>> case, and I would definitely time a re-writing and throw it away
>> unless it was significantly faster.  But I don't think this is a case
>> where laziness actually alters either the time or the space
>> asymptotics of the algorithm (you end up creating an ~ O(n) tree
>> anyway, so I'd figure O(n) space was OK for the loop, too).
>
> I was wondering if laziness would make it run as if it was a single  
> O(n)
> operation (get one directory entry "on demand", pass it to filter and
> then to insertInTree),

That should be the evaluation order, yes.  I think big-O notation is  
the wrong notation for this; you get a single loop with three  
sequenced operations, rather than three sequenced loops, but both are  
O(n).

> because only one entry is used at a time, so that
> only the "current" entry needs to be evaluated.
>
> I still find it hard to evaluate the effects of laziness on the
> complexity of programs...

jcc