feature(slice_patterns)

A welcome stabilization
A snippet of source code using the new subslice matching feature. Ferris is peeking in from the top right corner and there is a Rust logo in the bottom right corner.

Weeee!

About a week ago, there was an item in This Week in Rust (issue 320) that caught my eye under the Tracking Issues & PRs heading:

[disposition: merge] Stabilize ~#![feature(slice_patterns)]~ in 1.42.0.

Aww, yeah! I've been waiting for this for literal years, so you better believe that was a good day! I mentioned this in my Rust 2020 post as one of the things I'm the most excited to see this year, so now that it's getting stabilized soon (2020-03-12), let's make sure we're prepared!

About slice patterns

  Most of the information contained in this section can also be found in the RFC on GitHub. The RFC is very thorough and gives lots of examples, so go give it a read if you want to know more about the feature!

We've had some form of slice matching on stable Rust for a while now, but without this feature, the form of matching you can do is rather limited. With an array of a known length, you can destructure and match as you please, but for slices of an unknown length, you must provide a fallback because there is no way to cover all the potential cases in a match expression. Also, quite importantly: there is no way to bind variables to subslices. This feature finally opens the gates to subslice and subarray matching, mitigating both the above issues, and making slice patterns immensely more powerful.

Two flavors

There are two syntactic flavors for the new subslice patterns: one for when you want to bind a subslice to a variable, and one for when you just want to denote that there are elided elements. Both flavors use the .. pattern (referred to as a rest pattern) to match a variable number of elements. The number of elements matched depend on the length of the array or slice and the number of matching elements before and after in the match.

Matching without binding

Looking at the first flavor, matching without binding, we get introduced to the .. pattern straight away:

      fn f<T>(xs: &[T])
      where
          T: std::fmt::Debug,
      {
          match xs {
              // the slice has at least two variables.
              // we bind the first and last items of
              // the slice to `x` and `y`, respectively
              [x, .., y] => {
                  println!("First and last: {:?} and {:?}.", x, y)
              }

              // the slice has a single item: `x`
              [x] => {
                println!("the slice has a single item: {:?}.", x)
              }

              // the slice is empty
              [] => {
                  println!("Got an empty slice.")
              }
          }
      }

Remember that .. can match any number of elements, including 0. This means that the first pattern matches anything that has at least two items. You can also use the pattern without 'delimiting' it on both ends, such as if you wanted to implement these two functions for getting the first and last element of a slice:

      fn first<T>(xs: &[T]) -> Option<&T> {
          match xs {
              [x, ..] => Some(x),
              [] => None,
          }
      }

      fn last<T>(xs: &[T]) -> Option<&T> {
          match xs {
              [.., x] => Some(x),
              [] => None,
          }
      }

Notice how both of these functions pick out a single element of the slice (first and last respectively) and ignore the rest. Because .. matches 0 or more elements, the first pattern in both functions matches slices with one or more elements.

Matching and binding a subslice

The other flavor lets you bind a subslice to a value, which takes slice patterns and cranks the power level up another notch or two. The binding is done using the @ operator.

Imagine for instance that we want to write a sum function. That could be done as such:

      fn sum(xs: &[i32]) -> i32 {
          match xs {
              [] => 0,
              [x, xs @ ..] => x + sum(xs),
          }
      }

In the example above, if the slice is not empty, we take the first element, x, and add it to the result of summing the rest of the list, xs. With Rust already having a sum method on iterators, this function is pretty redundant, but it makes a good example of how to bind and use subslices.

Another example would be to get the middle element of a slice if the slice has an odd number of elements. If the slice is empty or has an even number of elements, return None:

      fn middle<T>(xs: &[T]) -> Option<&T> {
          match xs {
              // ignore the first and last element.
              // recurse with what's in between.
              [_, inner @ .., _] => middle(inner),

              // one element! got it!
              [x] => Some(x),

              // oops! there's nothing here.
              [] => None,
          }
      }

Here we iterate through the slice from both sides, continuously picking off one element at the start and one element at the end. Whatever is left in the middle (if there are at least two elements) gets assigned to xs and used as input to another step through the function. Once we have either one or zero elements left, we have our answer.

Why this is a big deal

It might come across as somewhat strange that I'm so enthused about a feature that may seem rather small, but it's one of those quality of life things that I find myself running into all the time. Being used to Haskell and their pattern matching behavior, I always forget how cumbersome it is to match on an arbitrary slice in Rust. Up until now, we've had the ~split_first~ method (and split_at) on slices, which I can never remember the name of, which returns an Option, and which doesn't let you do arbitrary match-stuff (such as using match guards, for instance). The new slice_patterns feature is a major step up in that regard.

The other thing that I'm super jazzed about? Being able to match on the end of a slice. Not only can you pick off items from either end of the slice, but you can also make sure that the slice ends in a certain value or series of values.


In short, I think this is an amazing addition to stable Rust. Hats off to all the people that have made it possible. Now go read the RFC and look out for all the other cool stuff they're talking about (arbitrarily nested OR patterns? Oh, my!).


A whole chapter dedicated to folding lists? I thought it would be quick and easy, but it turns out there's a lot of things to uncover in regards to folding. In this post we'll be looking at what a fold is and how folding left differs from folding right.

A brief explanation of folding

Before we can talk about folding left or right, it's important to know what we're talking about. In short, a fold is a way to reduce a data structure (lists in our case) to some other type by working through the data structure. If that sounds unclear, a more concrete example could be a function that sums all the numbers in a list or a function which tells you whether any element of a list satisfies a predicate.

Let's look at foldr, short for 'fold right'. We'll talk about foldl (fold left) in a bit. The signature for foldr is as follows as taken from GHCi, version 8.6.5:

  class Foldable (t :: * -> *) where
    foldr :: (a -> b -> b) -> b -> t a -> b

We haven't talked about kinds yet (that's in the next chapter), but the t :: * -> * part means that t is a type that is parameterized by another type. In our instance, we can substitute it with a list instead:

    foldr :: (a -> b -> b) -> b -> [a] -> b

So foldr is a higher-order function that relies on two parametrically polymorphic types, a and b. It takes a function from a and b to b, an initial b value, a list (or Foldable) of a, and returns a b.

This snippet is taken from the Haskell Wiki article on folding (which I recommend you take a look at if you're not quite familiar with it), and shows the equations defining foldr:

  -- if the list is empty, the result is the initial value z; else
  -- apply f to the first element and the result of folding the rest
  foldr f z []     = z
  foldr f z (x:xs) = f x (foldr f z xs)

In the above snippet f is the (a -> b -> b), z is the b, and the [a] is either destructured into [] or (x:xs).

Folds are catamorphisms, a way of deconstructing data, reducing a structure to a completely different result.

Why direction matters: foldr vs foldl

Building on the basic definition of a fold, let's explore the differences between folding left and folding right and what impacts that has on your programs.

Let's revisit the definition of foldr, but this time put foldl just below it. Again, the snippet is taken from the Haskell Wiki article on folding, but I've added the function types for clarity.

  -- if the list is empty, the result is the initial value z; else
  -- apply f to the first element and the result of folding the rest
  foldr :: (a -> b -> b) -> b -> [a] -> b
  foldr f z []     = z
  foldr f z (x:xs) = f x (foldr f z xs)

  -- if the list is empty, the result is the initial value; else
  -- we recurse immediately, making the new initial value the result
  -- of combining the old initial value with the first element.
  foldl :: (b -> a -> b) -> b -> [a] -> b
  foldl f z []     = z
  foldl f z (x:xs) = foldl f (f z x) xs

These two functions are nearly identical, but they flip the order of the parameters of the first function and they behave quite differently. Notice how foldr applies f to x and then to the result of folding the rest of the list, while foldl immediately recurses before applying f to z and x. This may seem unimportant, but it has big ramifications in a lazy language like Haskell.

With foldr, if you have a function that lazily evaluates its arguments, you could potentially short-circuit the recursion long before reaching the end of the list, but with foldl, because the function recurses immediately, you force the evaluation of the entire list. This means that if you have an infinite list, foldl will never finish, while foldr might.

Let's see an example. If we want to use foldr to find whether any number in an infinite list is even, we could do it like this:

    foldr (\x b -> even x || b) False [ 1 .. ]
    -- returns True

Even if the list is infinite, the function we pass to foldr doesn't evaluate its second parameter (b) if even x evaluates to True. In the example above, the evaluation would work a little something like this:

    -- the list is not empty, so apply f to the head of the list
    -- and set up potential recursion
    even 1 || foldr (\x b -> even x || b) False [ 2 .. ]
    -- even 1 is False, so we take another step and recurse.

    even 2 || foldr (\x b -> even x || b) False [ 3 .. ]
    -- even 2 is True, so we don't need to evaluate anymore.
    -- we can happily return the result with only two steps.

In this example, the function can exit after only two steps through the list because our function (\x b -> even x || b) doesn't evaluate b unless even x is False. If we look at the same example with foldl, however, the result is quite different:

    -- note the flipped parameter order for f
    foldl (\b x -> even x || b) False [ 1 .. ]
    -- ... ... ... ...
    -- never terminates

Because foldl recurses unconditionally (foldl f (f z x) xs), the function will start to evaluate, but because it needs to get to the end of the list before it can evaluate the function and because the list is infinite, the function can never terminate.

foldr, on the other hand, doesn't recurse immediately, and flips back and forth between evaluating f and taking another step. This means that, because of lazy evaluation, foldr can stop recursing through the list after any number iterations, depending on the function.

Let's relate back to what we talked about last time and talk about spines. Folding happens in two stages: traversal and folding. Traversal is the stage in which the fold recurses over the spine. Folding is the evaluation of the folding function applied to the values. All folds recurse over the spine in the same direction. However, the difference lies in the association of the folding function and direction the folding proceeds. This sounds tricky, but we can demonstrate it by parenthesizing:

    foldr (+) 0 [ 1 .. 5 ]
    -- evaluates as the following
    -- (1+(2+(3+(4+(5+0)))))

    foldl (+) 0 [ 1 .. 5 ]
    -- evaluates as the following
    -- (((((0+1)+2)+3)+4)+5)

Notice how the order in which the expressions are evaluated is reversed, as is the end at which the zero element is applied. If we use a non-commutative operation instead of summing, we'll see the last point more clearly:

    foldr (++) "0" ["a", "b", "c"]
    -- evaluates to "abc0"

    foldl (++) "0" ["a", "b", "c"]
    -- evaluates to "0abc"

Notice how the 0 ends up at opposite ends of the result because of the evaluation order.

Folding summary

In short, the book recommends to always use foldr over foldl and provides a helpful summary:

~foldr~
  1. The recursive invocation of foldr is an argument to the folding function. It doesn't directly self-call as a tail call the way foldl does. In a way, you can think of foldr as alternating between applications of the folding function f and foldr, where the next invocation of foldr is dependent on f asking for it.
  2. Is right-associative.
  3. Works with infinite lists.
  4. Is a good default choice for transforming data structures.
~foldl~
  1. Self-calls (tail call) through the list, starts to produce values after reaching the very end.
  2. Is left-associative.
  3. Cannot be used with infinite lists.
  4. Is 'nearly useless' and should almost always be replaced with foldl'~. We haven't talked about ~foldl'~, but it works the same as ~foldl except it is strict, meaning it evaluates the values inside the cons-cells as it traverses the list, rather than leaving them as unevaluated expressions. We'll talk more about this when we get to the chapter on efficient code.

Definitions

Fold
A higher-order function that takes an accumulating function and a recursive data structure and returns the value that results from applying the function to the elements in the structure.
Catamorphism
A generalization of folds to arbitrary data types. A morphism is a transformation, and cata means 'down' or 'against', so a catamorphism is a transformation to a 'lower' form.
Tail call
A tail call is the final result of a function, i.e. the last function that gets called in a function. In the below example---assuming g and h are functions---~h~ is the tail call.
                  f x y = h (g x y)
Tail recursion
a function whose tail calls are recursive invocations of itself. In our definitions of foldr and foldl, we see that foldl is tail recursive, while foldr is not, as the latter alternates between calling f and foldr.

Summary

In addition to going deep on folding, this chapter also touches briefly on the scan functions scanl and scanr. In the interest of time I won't cover them here (unless we need them later), but if you're interested you can go check out Hackage for more information.

Next chapter is on Algebraic Data Types, and it's a big one, so stay tuned.


Ah, another data type deep dive! This time we're looking at lists and how they are created and evaluated. Not much more of an introduction needed here; let's just dive right in!

List creation

There's a number of ways to construct lists in Haskell. This chapter covers using ranges and list comprehensions, both of which are quite neat and something I get deep personal satisfaction out of (hey, I'm not weird!).

We covered ranges when looking at the Enum typeclass in Chapter 6, so let's just do a quick refresher: In Haskell you can create lists out of anything that implements the Enum typeclass (such as Int and Char and Bool) by using the syntactic range sugar:

     -- expression and what they evaluate to
     [ 1 .. 5 ] -- [1, 2, 3, 4, 5]
     [ 1 .. ] -- an infinite list of integers, each entry increasing by 1
     [ 1, 3 .. ] -- an infinite list of integers, each entry increasing by 2
     [ 1, 5 .. 10 ] -- [1, 5, 9] (step size is 5-1 = 4)

Neat, huh? Just keep in mind that the range must be in increasing order. If you try something like [5 .. 1], you'll get an empty list.

In addition to ranges, there's also this thing called list comprehension. List comprehensions are something I normally associate with Python, but I think Haskell's version is much cooler. The syntax looks a lot like set comprehension does in mathematics (which is also where the concept comes from). A list comprehension requires at least one list (called a generator) that provides an input for the comprehension. Here's a simple comprehension:

    [ x^2 | x <- [1 .. 5] ] -- [1, 4, 9, 16, 25]

The first bit before the pipe, x^2, is the expression that goes into every cell. The variable x is assigned from the generator [1 .. 5]. Indeed, what this list comprehension does is simply to square each number of the generator. The same result could be achieved by a simple map: map (^2) [1 .. 5].

Where list comprehensions really shine, however, is when you start to add more variables and optional filters. When adding more variables, the comprehension will create a list with every possible permutation of those values. For instance: say you want to create a list of all the positions in a 3x3 grid around an origin ((-1, -1) to (1, 1)). Using list comprehensions, that's trivial:

  [ (x, y) | x <- [-1 .. 1], y <- [-1 .. 1] ]

In addition to variables, you can also add filters after the variables. Say you want the same list as above, but you don't want to include the origin ((0, 0)):

  [ (x, y) | x <- [-1 .. 1], y <- [-1 .. 1], (x, y) /= (0, 0) ]

And not just one filter; you can add multiple! What if we want a bigger list, but only want the tiles where the Manhattan distance to the origin is divisible by 7 (and excluding the origin itself)?

  [ (x, y) | x <- [-4 .. 4], y <- [-4 .. 4], (x, y) /= (0, 0), (abs x + abs y) `mod` 7 == 0 ]

It may be a farfetched example, but I think it adequately shows just how cool list comprehensions can be in Haskell.

Spines and non-strict evaluation

To talk about list evaluation, we need to talk about how lists are represented. To talk about how lists are represented, we need to talk about spines. But let's take a step back. It's not all that scary.

The list data type is defined as such:

  data [] a = [] | a : [a]

It's a recursive data structure. It's either an empty list, or an element prepended to another list. Syntactically, when we write lists or print them, they're usually presented like this: [1, 2, 3], but can also be thought of as 1 : 2 : 3 : []---that is 1 before 2 before 3 before the empty list.

The : operator is known as cons. The list construction in the last paragraph can be thought of as a series of cons cells (a value consed onto a list). It could also be written like this, which may make the relation to the list data constructor clearer: 1 : (2 : (3 : [])).

One problem with this representation, though, is that it makes it seem like 1 exists 'outside' of the list, when it is actually contained by it (and by its cons cell). Because of how lists are evaluated in Haskell, we'll see that because the value is contained, we can evaluate cons cells without evaluating their contents.

Let's talk about spines. You see, the list above can also be represented---conceptually---like this:

    :
   / \
  1   :
     / \
    2   :
       / \
      3  []

In this representation, the cons operators line up to form what is known as the spine, which is a fancy word for the connective structure that makes up a data structure such as a list or a tree. In the case of lists, it's just a series of cons operators.

Crucially, spines are evaluated independently of values. What does this mean? Well, functions that only require evaluating the spine and not the values, such as length, can walk down a list without evaluating the contents. So, returning to our list from before, if we were to apply the length function on it (and the values hadn't already been evaluated), you could think of it like this, where the underscores represent values that haven't been evaluated.

    :
   / \
  _   :
     / \
    _   :
       / \
      _  []

Another way to get this point across is to look at what happens when we add bottom values to a list. Run this in the REPL to try it out.

    let xs = [1, undefined, 3]
    length xs -- 3
    take 1 xs -- [1]
    take 2 xs -- Exception: Prelude.undefined

Taking the length of the list works just fine because we don't need to evaluate the items in the list. Taking the first element is no problem because it's a regular value and the rest of the list has not been evaluated. When we take two values, however, this forces the evaluation of the second item in the list, undefined, which causes the program to crash.


There is loads more to be said about list evaluation and the impacts it has on what we can and can't do in code, but these are the most important things covered in this chapter.

Chapter definitions

Product type
A product type is a type that contains several other types at the same time. The canonical example is a tuple: You can have a tuple of a Bool and an Int, and for every instance you have of that type, you will have both a Bool and an Int. The reason its called a product type is that the number of possible permutations is the product of the number of possible values for each type.

Say you have a data type: data Direction = Up | Down | Left | Right. If you have a (Bool, Direction) tuple, you now have $8$ ($4 \cdot 2$) different possible permutations of that tuple.

Sum type
A sum type is a type that is only one of a set number of types at any time. Relating this back to the example above with Bool and Int: If you have a data type that is either a Bool or an Int (such as Either Bool Int), then that's a sum type. The number of possible permutations is the sum of the number of possible values for each type.

Using the Direction type from above, Either Bool Direction has $6$ ($4 + 2$) possible values.

Cons
The : operator. Used to prepend a value onto a list. Can also be used as a verb (e.g. consing a value onto a list).
Cons cell
A data constructor and a product of the types a and [a] as defined in the list data type definition.
Spine
A structure that strings a collection of values together, the scaffolding of a data structure. For the list datatype, it's formed by the recursive nesting of cons cells.

Other topics

In addition to what we have covered here, the chapter also contains more information about pattern matching on lists, and some common list operations: map, filter, and zip. However, to keep things nice and brief, I've decided to leave them out for now. For more information on those topics, please consult your search engine of choice or nearest message board.