[Haskell-cafe] Dropping trailing nulls from a list of list

Jeff.Harper at handheld.com Jeff.Harper at handheld.com
Wed Mar 8 12:08:57 EST 2006


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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell-cafe/attachments/20060308/fda44a42/attachment.htm


More information about the Haskell-Cafe mailing list