Dropping trailing nulls from a list of list
Today, I reviewed a function I wrote a few months ago. The function, dropTrailNulls, takes a list of lists and drops trailing null lists. For instance: *Main> dropTrailNulls [[1],[2,3],[],[]] [[1],[2,3]] My original implementation was terrible. It was recursive, overly bulky, and difficult to understand. It embarrasses me. I won't post it here. Today, it occurred to me this would do the trick: dropTrailNulls list = reverse (dropWhile null (reverse list)) The problem is 20 years of experience writing efficient imperative programs says to me, "You don't drop things off the end of a structure by reversing the structure, dropping stuff from the beginning, then reversing again." I suspect this imperative bias prevented me from coming up with the simple solution when I first wrote my function. On the other hand, it is conceivable to me that my new implementation may actually be relatively efficient since Haskell uses lazy evaluation, and Haskell lists are constructed from the tail to the beginning. I'm sure there are many problems that are encountered in Haskell where it is necessary to operate on the end of a list. So, I'm wondering if the idiom, reverse, operate, then reverse is something I should add to my toolbox. Or, is there a more efficient idiom for addressing these problems?
dropTrailNulls list = reverse (dropWhile null (reverse list))
Or more succinctly: dropTrailNulls = reverse . dropWhile null . reverse
Or, is there a more efficient idiom for addressing these problems?
The "bad thing" about this definition is that it is tail strict. Consider ["hello","everyone","","","","",... <forever>] With your definition you will get nothing back (since reverse is tail strict). However, there is an alternative definition that will give the first two elements back: dropTrailNulls x = f 0 x where f n [] = [] f n ([]:xs) = f (n+1) xs f n (x:xs) = replicate n [] ++ (x : f 0 xs) -- note: untested, may not work The reason is because it is significantly more lazy. It is also more space efficient, and probably faster. However, despite all this, I love the reverse . something . reverse example, and I think its totally beautiful in terms of simplicity. The general programming advice holds here as for everywhere else - write beautifully, if performance demands, profile then write to obtain speed. Thanks Neil
On Mar 8, 2006, at 12:08 PM, Jeff.Harper@handheld.com wrote:
Today, I reviewed a function I wrote a few months ago. The function, dropTrailNulls, takes a list of lists and drops trailing null lists. For instance:
*Main> dropTrailNulls [[1],[2,3],[],[]] [[1],[2,3]]
My original implementation was terrible. It was recursive, overly bulky, and difficult to understand. It embarrasses me. I won't post it here.
Today, it occurred to me this would do the trick:
dropTrailNulls list = reverse (dropWhile null (reverse list))
The problem is 20 years of experience writing efficient imperative programs says to me, "You don't drop things off the end of a structure by reversing the structure, dropping stuff from the beginning, then reversing again." I suspect this imperative bias prevented me from coming up with the simple solution when I first wrote my function.
On the other hand, it is conceivable to me that my new implementation may actually be relatively efficient since Haskell uses lazy evaluation, and Haskell lists are constructed from the tail to the beginning.
Only if the list is spine strict (AND the compiler knows this AND it decides to strictify the call). Lazy evaluation actually builds lists from the front, unfolding thunks as they are demanded.
I'm sure there are many problems that are encountered in Haskell where it is necessary to operate on the end of a list. So, I'm wondering if the idiom, reverse, operate, then reverse is something I should add to my toolbox. Or, is there a more efficient idiom for addressing these problems?
Use a data structure which allows efficient access to the end of a sequence. (shameless plug) Check out Edison, it has a couple that would serve; I hope to prepare an updated release pretty soon. (http://www.eecs.tufts.edu/~rdocki01/edison.html) As to lists in particular... While I suppose its _possible_ that (reverse . dropWhile p . reverse) will be fused into something more efficient, I don't think you can count on it (any core wizards care to contradict me?). You might be able to do something more efficient with foldr. Humm, lets see... dropTailNulls = snd . foldr f (True,[]) f x (allNulls,y) | null x && allNulls = (True, []) | otherwise = (False, x : y) That seems to work. Dunno if it's any more efficient though; it is certainly less beautiful. Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
On 2006-03-08, Bulat Ziganshin
Jeff.Harper@handheld.com wrote:
Today, I reviewed a function I wrote a few months ago. The function, dropTrailNulls, takes a list of lists and drops trailing null lists. For instance:
*Main> dropTrailNulls [[1],[2,3],[],[]] [[1],[2,3]]
dropTrailNulls = foldr dtn [] where dtn [] [] = [] dtn x xs = x:xs
dropTrailNulls list = reverse (dropWhile null (reverse list))
As the other responses said, this is needlessly strict. Work on deforesting reverse exists, but you can't count on it happenig.
is there a more efficient idiom for addressing these problems?
Well, there's always the basic fold. I'm not sure there's any lesson to be learnt here other than "fold is your friend". Udo. -- F: Was ist ansteckend und kommutiert? A: Eine Abelsche Grippe.
On Wed, 8 Mar 2006 Jeff.Harper@handheld.com wrote:
Today, I reviewed a function I wrote a few months ago. The function, dropTrailNulls, takes a list of lists and drops trailing null lists. For instance:
*Main> dropTrailNulls [[1],[2,3],[],[]] [[1],[2,3]]
http://www.haskell.org/pipermail/libraries/2005-August/004217.html
participants (7)
-
Aaron Denney -
Bulat Ziganshin -
Henning Thielemann -
Jeff.Harper＠handheld.com -
Neil Mitchell -
Robert Dockins -
Udo Stenzel