How to Pattern Match an Empty Vector in Haskell?

Question

Say I want to implement the length function for lists using pattern matching, then I could do something like this:

length' :: (Num b) => [a] -> b  
length' [] = 0  
length' (_:xs) = 1 + length' xs  

Can I do something similar with Vectors?

Ultimatum

You can use things like ViewPatterns and PatternSynonyms to pattern match on things which are abstract types, but if you want to write an inductive function like length on a Vector, why not just use foldl or foldr, or any of the other dozen or so variants of "fold" which vector provides? This has the advantage of generalizing to every Foldable if you use e.g. Data.Foldable.foldr instead of the specific versions in vector. – Infeasible

Maybe case splitAt 1 v of ... ? Possibly made into a ViewPattern, as suggested above. – Orelle

Be careful with pattern synonyms; they can break performance intuition if not designed well. – Overgrow

Rule of thumb: applying or matching on a pattern synonym should be amortized O(1) time even when the value is used persistently. I would never tolerate a pattern synonym with worse than polylogarithmic time. – Overgrow

Answer 1

The vector library's various Vector types are opaque types, which do not expose their data constructors, and as such you cannot pattern match on them.

There are ways around this, like ViewPatterns (as the comment by user2407038 mentions), but you certainly don't want to use these with vectors, because you'd probably throw away the advantage of using vectors.

The highlight of the vector library is that it's implemented on the basis of two concepts:

1. Vectors are materialized as fixed-size, contiguous memory arrays, which provide much better memory locality than single-linked lists or trees;
2. A large number of vector operations are implemented in terms of fusible streams whose operations compile down to loops that don't allocate memory for intermediate vectors.

(1) means that a vector doesn't have a natural "head" and "tail" like lists do—lists are literally a pair of a head and a tail. If you were to use some sort of view pattern to impose a head+tail structure on top of a vector, you'd be effectively creating a single-linked list of the vector's elements, which would likely trigger memory allocation for each node of the view type.

And if you were using ViewPatterns to view a vector as what is effectively a single linked list, why not just convert the vector into a list?

In any case, because of the design points mentioned above, with vector you really want to stick as much as possible to the operations provided by the library itself, because they will exploit the library's performance features.

I suspect that there's a good chance that testing the size of a vector might be a suboptimal idea in many contexts. For example, in code like this:

example :: Vector something -> Vector somethingElse
example as 
  | Vector.null as = ...
  | otherwise      = ...

...I would expect (but have not verified!) that this would force the vector as to be materialized so that we can test whether it's empty or not, where if the test could be eliminated or moved somewhere else it's possible that the operations in the "..." bit could be fused with the context in which example is used.

Breezy

Vector.empty :: Vector a actually returns an empty vector. You would want to use Vector.null :: Vector a -> Bool instead. – Coronet