Owen Smith wrote:
Hi all,
Thanks for your welcome and helpful comments. I've banged out a first
attempt at a Haskell library and was curious if anybody would have
time or interest in looking it over it for style, design, stuff that's
just wrong, or (most likely) stuff that's been done better elsewhere.
I'm willing to trade some labor in kind, if there's any odd jobs that
can be done by a relative newbie (e.g. maybe setting up a Windows box
for OpenGL build testing with GHC 6.10??).
The library, slice, is an emulation of Python's list slicing mechanism:
http://www.owendsmith.com/slice-1.0.0.tar.gz
It uses a triple of Maybes to specify the range, so it's unwieldly in
terms of syntax, but the functionality should be there.
This begs the question, why not use Haskell's enumeration syntax
directly? That is, is there a specific reason you're using SliceParams
instead of taking a list of indices as input? If you do the latter then
Haskell already provides the [1,3..42] syntactic sugar (albeit, the
second argument is the second element of the list with the step size
inferred, rather than giving the step size explicitly).
Upsides of lists of indices:
* You can do Perl-style slicing where you can take the elements in
whatever order you like, not just regular stepping orders. This is a
two-edged sword, but it does make things much more concise than needing
to manually stitch together a bunch of regular-step slices.
* You can allow a step size of 0 in order to get an infinite list of the
element at that index. (Of course, you can do this with the current
implementation by just allowing it.)
* You can piggyback on Haskell's syntactic sugar for regular step sequences.
* Negative indices are easy: let l = length xs in xs `slice` map (\i ->
if i < 0 then l+i else i) indices -- with some extra polish for
boundary conditions.
* It can potentially be generalized to operate over any indexable
collection. (Maybe more tricky than it's worth, if you want to guarantee
efficiency.)
Downsides:
* Handling Perlish slicing is trickier since you may need to jump
arbitrarily far back into the part of the list you've already seen. It's
especially tricky if you don't want to hold onto the whole list when you
don't need it.
* Constructing a list of indices from the [x,y..z] expression adds
memory overhead if you don't do list fusion. (FWIW, using list fusion
isn't too hard, heck you've basically rewritten a specialized case of it.)
Implementation-wise, you should use Data.List.Extras.LazyLength[1] for
dealing with those guards. When you just want to guarantee a list's
length is above or below some bound, getting the actual full length
always wastes time and generally wastes space as well (by not being
least-strict).
Similarly, if you do in fact need to get the full length of a list, you
should bind it to a local variable so you needn't calculate it over and
over. Also you can use case expressions (with a function like `compare`)
to replace many of the guards more efficiently.
In the same vein, the `slices` function can be made much more efficient
if you actually do a round-robin, instead of traversing the list
repeatedly for each slice. Round-robining is much easier than doing
slicing right anyways.
Finally, you may want to use Data.DList[2] in sliceRec, instead of
constructing the list backwards and then reversing it. Difference lists
have a constant-time append function, so you can eliminate the reversal
thus saving O(m) time where m is the length of the list returned.
[1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/list-extras
[2] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist
Mostly,
besides gaining experience with writing a library, I wanted to have
functionality that skips through a list the way Python slices can, and
didn't see a particularly clean way of doing that particular kind of
list dicing in Data.List or elsewhere.
A naive implementation of the arbitrary-indexing Perlish slicer:
> xs `slice` indices = map (xs !!) indices
Of course, this implementation is quite slow since it traverses the list
from the beginning for each index. A smarter version would use something
like a list zipper[3] so that the traversal time is bounded by the step
size. In fact, difference lists can be thought of as a special case of
zippers for lists.[4]
[3] http://en.wikibooks.org/wiki/Haskell/Zippers
[4] Where "special" means you only ever expand it down, and never move
backwards. Difference lists can be generalized to other datastructures
in the same way zippers can, though it seems much less common to do so.
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe