[Haskell-cafe] Re: On the verge of ... giving up!
apfelmus at quantentunnel.de
Mon Oct 15 08:51:32 EDT 2007
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
Data.List> tails . drop 2 $ xs
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
length . tails . drop n = (\k -> 1 + max 0 (k-n)) . length
But the wrong version looks much nicer :)
> Thanks for your great postings, apfelmus.
More information about the Haskell-Cafe