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