Dropping trailing nulls from a list of list

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Dropping trailing nulls from a list of list

Jeff.Harper

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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Dropping trailing nulls from a list of list

Neil Mitchell
> 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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Dropping trailing nulls from a list of list

Bugzilla from robdockins@fastmail.fm
In reply to this post by Jeff.Harper

On Mar 8, 2006, at 12:08 PM, [hidden email] 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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Dropping trailing nulls from a list of list

Bulat Ziganshin-2
In reply to this post by Jeff.Harper

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                            [hidden email]


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Dropping trailing nulls from a list of list

Udo Stenzel
In reply to this post by Jeff.Harper
[hidden email] 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.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Dropping trailing nulls from a list of list

Henning Thielemann
In reply to this post by Jeff.Harper

On Wed, 8 Mar 2006 [hidden email] 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Dropping trailing nulls from a list of list

Aaron Denney
In reply to this post by Bulat Ziganshin-2
On 2006-03-08, Bulat Ziganshin <[hidden email]> wrote:
[a lot of HTML crap that was difficult to read]

If you actually want people to read and understand your mail, you might
want to make it easy for them to do so.

--
Aaron Denney
-><-

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe