[Haskell-cafe] The container problem
andrewcoppin at btinternet.com
Fri Sep 26 17:37:12 EDT 2008
Derek Elkins wrote:
> One aspect of it is a bit of a You Aren't Going To Need It.
Personally, I haven't had a huge problem with this in practice.
What it basically means is that if you write a library function, *you*
have to decide what containers you're going to use. It's not really
possible to let the user decide. You kind of have to hard-wire it
yourself. That's the only real problem with it. Sometimes it's
irritating to convert an array to a list, feed it to some function, and
then immediately convert it back to an array again, for example. (Not
only annoying, but presumably not that efficient.)
> Another reason is that often you can use an intermediate data structure,
> especially lists, for operations. Lists are the
> iterators/IEnumerable/generators of Haskell. So if I just need to
> traverse a data structure, I can just write an interface that accepts a
This is the other part of it. In Haskell, a list in some sense "is" a
control-flow loop. If the compiler's inlining is half as good as it's
supposed to be, converting an array to a list and then feeding it to
some function hopefully ends up being inlined so that you end up with
the function directly iterating over the array. Hopefully the function's
output ends up being similar. So it's not like you build a while list in
memory and then consume it. It's not even like the GC has to go round
and free all the list cells. The list itself never actually exists as
such at runtime.
Alternatively, I'm talking complete nonesense... o_O
> Of course, since Haskell isn't Java, I'm not subject to the choice of
> interfaces the data structure implementer decided to implement or not.
> When this happens in Java the "standard" solution is to use an adapter
> class. In Haskell, I can just write the instance. In particular, I can
> decide on whatever interface I need, write my code to that interface and
> just instantiate it for the relevant data types and users can
> instantiate it for their data types. If you want an OrderableCollection
> class, you can simply write one today. You don't need to ask anyone's
> permission or coordinate with anyone.
Haskell class membership is "open" in this way - a useful feature, IMHO.
> Finally, there -are- several more or less standard classes that capture
> different general operations on data structures (though there certainly
> could be more.) They, of course, have different names and different
> interfaces and different factorings from imperative equivalents. We
> have Functor, Applicative, Monad, MonadPlus, Monoid, Foldable,
> Traversable, IArray, MArray and others. Notice how the ridiculous
> proliferation of array types in Haskell has pressed the issue and led to
> the creation of IArray and MArray.
As already noted, Data.Set *should* be a Monad, but can't be. The type
system won't allow it. (And I know I'm not the first person to notice
this...) Similar fun and frolics with Functor, and presumably
Applicative and Foldable (I haven't actually heard of these until just now).
Frankly, the whole "array" thing is slightly crazy to me. There are
several things which the array libraries ought to support, but don't:
- Making "slices" of arrays. (I.e., generating a subarray in O(1) by
using transparent reindexing.)
- Linked lists of arrays that provide an array-like interface.
(ByteString.Lazy does this, but only for Word8 or Char.)
- It really ought to be possible to unbox *any* type. Technically this
is implementable now, but I can't find details of how...
- Performing "map" in-place for mutable arrays. (This must surely be a
very common operation.)
- Build-in functions for joining arrays together, and splitting at a
- Array sorting. [Arrays have O(1) indexing, which has big implications
for what sorting algorithm to choose.]
- Lists have about 5,000,000 functions for processing them. Arrays have,
like, a dozen. Just how efficient is it to convert an array to a list,
process it, and then convert it back?
> Ultimately, it would still be beneficial to have some more standard
> interfaces for this sort of thing. There just hasn't been enough of a
> fire under the community's rear. This again suggests that YAGNI.
I see... ;-)
More information about the Haskell-Cafe