Re: [Haskell-cafe] Dropping trailing nulls from a list of list
On Wed, 8 Mar 2006 [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Dropping trailing nulls from a list of list
Hello Jeff, Wednesday, March 8, 2006, 8:08:57 PM, you wrote: > dropTrailNulls list = reverse (dropWhile null (reverse list)) dropTrailNulls [] = [] dropTrailNulls ([]:xs) = case dropTrailNulls xs of [] -> [] list -> []:list dropTrailNulls (x:xs) = x : dropTrailNulls xs should work faster. but in most cases speed is just not critical and Haskell allows to implement such parts of program faster and easier (and easier to understand) -- Best regards, Bulat mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Dropping trailing nulls from a list of list
[EMAIL PROTECTED] 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. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Dropping trailing nulls from a list of list
On Mar 8, 2006, at 12:08 PM, [EMAIL PROTECTED] 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 DockinsSpeak softly and drive a Sherman tank.Laugh hard; it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Dropping trailing nulls from a list of list
> 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","","","","",... ] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] 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?___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
