25 May
2011
25 May
'11
4:15 a.m.
"Richard O'Keefe"
Then tell me, why does calculating the length of a (Haskell) list has O(n) complexity.
Because it is a rather rare operation and the cost of doing this would be far higher than you think.
I suspect that if you store the length non-strictly, it would build up thunks, causing a stack overflow when evaluated. If it is strict, it would make a lot of operations that are O(1) today into O(n) operations. -k -- If I haven't seen further, it is by standing in the footprints of giants