<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><BR><DIV><DIV>On Mar 8, 2006, at 12:08 PM, <A href="mailto:Jeff.Harper@handheld.com">Jeff.Harper@handheld.com</A> wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><BR><FONT size="2" face="sans-serif">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:</FONT> <BR> <BR><FONT size="2" face="sans-serif">*Main> dropTrailNulls [[1],[2,3],[],[]]</FONT> <BR><FONT size="2" face="sans-serif">[[1],[2,3]]</FONT> <BR> <BR><FONT size="2" face="sans-serif">My original implementation was terrible. It was recursive, overly bulky, and difficult to understand. It embarrasses me. I won't post it here.</FONT> <BR> <BR><FONT size="2" face="sans-serif">Today, it occurred to me this would do the trick:</FONT> <BR> <BR><FONT size="2" face="sans-serif">dropTrailNulls list = reverse (dropWhile null (reverse list))</FONT> <BR> <BR><FONT size="2" face="sans-serif">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.</FONT> <BR> <BR><FONT size="2" face="sans-serif">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.</FONT> <BR></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV>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.<BR><BR><BLOCKQUOTE type="cite"><FONT size="2" face="sans-serif">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?</FONT></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV>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. (<A href="http://www.eecs.tufts.edu/~rdocki01/edison.html">http://www.eecs.tufts.edu/~rdocki01/edison.html</A>)</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>As to lists in particular...</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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...</DIV><DIV><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><DIV><BR class="khtml-block-placeholder"></DIV><DIV>dropTailNulls = snd . foldr f (True,[])</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>f x (allNulls,y)</DIV><DIV> | null x && allNulls = (True, [])</DIV><DIV> | otherwise = (False, x : y)</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>That seems to work. Dunno if it's any more efficient though; it is certainly less beautiful.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>Rob Dockins</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>Speak softly and drive a Sherman tank.</DIV><DIV>Laugh hard; it's a long way to the bank.</DIV><DIV> -- TMBG</DIV><BR class="Apple-interchange-newline"></SPAN></SPAN> </DIV></BODY></HTML>