[Grace-core] [minigrace] Need more string functionality (#52)

[Kim Bruce]

Good point, though I suspect most implementations (of non-functional languages) wouldn't include that optimization.  I don't know what happens in practice in other languages (Java?).  I'd hate to teach students things that would be bad practice in other languages.

I assume minigrace does not do this optimization, though obviously efficiency was not a priority there.

Kim



On Aug 21, 2014, at 2:33 PM, Michael Homer <mwh at ecs.vuw.ac.nz> wrote:

> On Fri, Aug 22, 2014 at 9:25 AM, James Noble <kjx at ecs.vuw.ac.nz> wrote:
>> 
>> On 22/08/2014, at 06:56 am, Kim Bruce <kim at cs.pomona.edu> wrote:
>> 
>>> As for Andrew's question why we need the variant that starts at an arbitrary index, the reasons are purely efficiency.  If you are searching for all occurrences of a phrase in a large text (e.g., a book) then making all those substrings will be very inefficient.  We could argue that doesn't matter (efficiency has been a low priority for us), going from a linear to quadratic algorithm to find all occurrences of a substring grates a bit!
>> 
>> We've always said *absolute* speed isn't a priority,
>> but we've also said we don't want to mislead students or reward bad practice.
>> Going from linear to quadratic, or going slower with type declarations, are misleading.
> I can't see any reason at all that making (immutable!) substrings
> needs to be a linear-time operation, if that's really what you care
> about.
> -Michael