[Haskell-cafe] Re: On the verge of ... giving up!

[apfelmus]

Felipe Lessa wrote:
> apfelmus wrote:
>> Of course, the solution is to first drop  n  elements and then take
>> tails instead of dropping  n  elements every time.
>>
>>    map (drop n) . tails = tails . drop n
>>
>>         O(m*n)                 O(m)
> 
> Nice identity. I'll remember this one.

Oops, please don't because it's wrong :)

   Data.List> let xs = [1..3]
   Data.List> map (drop 2) . tails $ xs
   [[3],[],[],[]]
   Data.List> tails . drop 2 $ xs
   [[3],[]]

The first one produces some extra empty lists at the end. In other 
words, the left hand side and the right hand side have different lengths

   length . map (drop n) . tails = (+1) . length

but

   length . tails . drop n = (\k -> 1 + max 0 (k-n)) . length

But the wrong version looks much nicer :)

> Thanks for your great postings, apfelmus.
λ(^_^)λ

Regards,
apfelmus