I saw this patch come in recently:

    [Refactor English patch/patches in darcs get.
    Eric Kow <kowey@darcs.net>**20090413180400
     Ignore-this: 3762aa5af1a16467a2a1ce00db3fb946
    ] hunk ./src/Darcs/Commands/Get.lhs 71
    +import English ( englishNum, Noun(..) )
    hunk ./src/Darcs/Commands/Get.lhs 269
    -                   (patch_or_patches $ lengthFL ps)
    +                   (englishNum (lengthFL ps) (Noun "patch") "")
    hunk ./src/Darcs/Commands/Get.lhs 278
    -patch_or_patches :: Int -> String
    -patch_or_patches 1 = "patch."
    -patch_or_patches _ = "patches."

English countable nouns need to know if the length is exactly one --
once it gets to 2, it can stop traversing the list.

But because `englishNum` takes a number instead of a traversible
sequence (e.g. a list or a lazy bytestring), I guess that most usages
currently traverse the entire sequence.  I don't know if it's an issue
for the above example, but it wouldn't surprise me if there are cases
where this results in really slow O(n) performance instead of O(1).

If we need to print out the number of items anyway, aren't we stuck with O(n) no
matter what?  Please unset wont-fix if I've missed something.

On Tue, Aug 18, 2009 at 08:46:06PM +0000, Eric Kow wrote:
> If we need to print out the number of items anyway, aren't we stuck
> with O(n) no matter what?  Please unset wont-fix if I've missed
> something.

For English plurality, it need only distinguish between "one" and
"more than one".  That is, it only needs to look at the first two
elements in a list.  IIRC the current API takes an integer, meaning
that everything that calls it just does length() on the list.

I was assuming the API should be changed to take the list itself and
directly check if it's one element long, but I suppose you could
alternatively just make sure none of its callers use length().

On Wed, Aug 19, 2009 at 02:01:56 +0000, Trent W. Buck wrote:
> On Tue, Aug 18, 2009 at 08:46:06PM +0000, Eric Kow wrote:
> > If we need to print out the number of items anyway, aren't we stuck
> > with O(n) no matter what?  Please unset wont-fix if I've missed
> > something.
> 
> For English plurality, it need only distinguish between "one" and
> "more than one".  That is, it only needs to look at the first two
> elements in a list.  IIRC the current API takes an integer, meaning
> that everything that calls it just does length() on the list.

Well, the context is that one tends not to use this function
without also wanting to print out the number itself.  I don't
think I've ever seen a use of englishNum which wasn't preceded
by a number, for example

  42 patches

While we only need to know if there are one or more patch to
decide whether or not to say 'patch' or 'patches' it sounds
like we're stuck traversing the list anyway so that we can
say exactly '42'.

I suppose fixing this means that we do one traversal and not
two, and that we could have a use out there that doesn't
also involve printing out some number, but I don't think it's
worth trying to be smart about this.

Could be wrong though.

On Wed, Aug 19, 2009 at 05:27:55AM +0000, Eric Kow wrote:
> Well, the context is that one tends not to use this function
> without also wanting to print out the number itself.  I don't
> think I've ever seen a use of englishNum which wasn't preceded
> by a number, for example
>
>   42 patches

That's a reasonable position to take, so I'm happy to leave this as-is.
...assuming that length() automemoizes ;-)