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

[Robert Dockins]

On Mar 8, 2006, at 12:08 PM, Jeff.Harper at 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell-cafe/attachments/20060308/821b26ce/attachment.htm