-----------------------------------

wtd

Sun Nov 22, 2009 1:56 am


[TYS] Summarize a list of numbers

-----------------------------------

So, let's say we have a list of numbers like so:

[code][1, 3, 4, 5, 7, 8, 10, 11, 13, 15][/code]

We want to summarize this by getting a list of start and end points.

[code][(1, 1), (3, 5), (7, 8), (10, 11), (13, 13), (15, 15)][/code]

Implement this behavior recursively using a left fold.  You may either implement your own left fold, or use one from a programming language's standard library.  For those implementing in a language which does not support tail-call elimination, don't worry about stack overflows.  However, the code should be written such that tail-call elimination would be at least possible.  You may also assume the list is sorted in ascending order.


-----------------------------------

Prabhakar Ragde

Sun Nov 22, 2009 3:44 pm


Re: [TYS] Summarize a list of numbers

-----------------------------------

It's more natural to use a right fold, and to produce the flat list, which you can easily bundle up into pairs afterwards.

If you use a right fold, in a lazy language you can produce the list lazily, and it will work on infinite lists. --PR


-----------------------------------

wtd

Sun Nov 22, 2009 4:05 pm


RE:[TYS] Summarize a list of numbers

-----------------------------------

I think you're right.  That'll teach me to post when I'm tired.