Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to Pattern Match an Empty Vector in Haskell?

Tags:

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?

like image 788
frmsaul Avatar asked Apr 14 '16 15:04

frmsaul


People also ask

How is pattern matching done in Haskell?

Overview. We use pattern matching in Haskell to simplify our codes by identifying specific types of expression. We can also use if-else as an alternative to pattern matching. Pattern matching can also be seen as a kind of dynamic polymorphism where, based on the parameter list, different methods can be executed.

What is pattern matching in Haskell explain with example?

In a functional language, pattern matching involves checking an argument against different forms. A simple example involves recursively defined operations on lists. I will use OCaml to explain pattern matching since it's my functional language of choice, but the concepts are the same in F# and Haskell, AFAIK.

Can you pattern match in guards Haskell?

The PatternGuards extension, now officially incorporated into the Haskell 2010 language, expands guards to allow arbitrary pattern matching and condition chaining. The existing syntax for guards then becomes a special case of the new, much more general form. You start a guard in the same way as always, with a | .

What is a vector in Haskell?

Vector is a Haskell library for working with arrays. It has an emphasis on very high performance through loop fusion, whilst retaining a rich interface. The main data types are boxed and unboxed arrays, and arrays may be immutable (pure), or mutable.


1 Answers

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.

like image 135
Luis Casillas Avatar answered Sep 28 '22 02:09

Luis Casillas