What to do if you have a Non Exhaustive pattern match

Learn
1

Hi, I tried to implement some sort of balancing search tree. For this I need some sort of rotation operation, these need to look a bit deeper (two nodes) into the tree, but I only call them if I already now that these exists (aka are none leafs). But to look into the tree I need to pattern match on their constructor. As Elm requires me to do this exhaustively I don’t know what to do in the Leave case of that pattern match (that can never occur).

I see the following options:

  1. I return something of the required type (that would be bad, and sends me (in case of a bug that exercise this codebranch) into debug hell.
  2. I wrap everything in Maybe (that is also terrible as this would propagate to the library api, and it is kind of stupid to have functions there that are Maybe, but never return Nothing) (aka the library will get unnecissary unusable)
  3. I write a pice of nonterminating code that will inhabit every type and send the programm into an infinite recursion. (I hope I don’t need to justify, why I don’t like this option)

So what is the right thing todo? (Is there maybe another way that is better?)

2

Probably just do nothing. If you get two nodes, rotate them and return the rotated nodes. If you get anything else just return it as is - the identity function.

Maybe need to see some code to give a better recomendation.

2 Likes
3

First some code (there are 4 rotations (two double rotations and two single rotations) here a single
rotation (the double rotations have to look one deeper and have one patternmatch more):

single_L : a -> Tree a -> Tree a -> Tree a
single_L el lst rst =
  case rst of
    E -> undefined
    T el2 _ rlst rrst -> t1 el2 (t1 el lst rlst) rrst

some context E and T are constructors for the Tree a datatype. E : Tree a is for leaves and T : a -> Int -> Tree a -> Tree a -> Tree a for nodes. The Int is stores is the sized of the tree (that is used for balancing)

t1 : a -> Tree a -> Tree a is a ‘smart’ constructor computing the right size, so there will be never accedentily the wrong one. The module will only export safe operations that can’t produce trees with wrong size information (so it won’t export T for example (and also not t1 as it can produce non-search trees but this is not the point here)).

single_L already takes the outermost Tree node in a patternmatched form (as the parent has to do this match anyway and we have one less pattern match we need to do then).

Why do I know that the patternmatching can’t fail. I read the size information (of the parent) before and know that the tree must be balanced (to some degree) and this already tells me that there has to be a non-leave there. If there is, this module already contains a bug! It should only give the user functions that produce correct trees!

What I realy dislike about the identity (it would work of course (in theory everything that is of the correct type wouldd work)), is that it can hide bugs. I as a developer want to know when this code branch gets exercised (as something is clearly wrong then). If I put the identity there it would not only return some value that type checks, but also produce a correct search tree. So from the outside and in
functional tests it will look like everything works, even if there is a bug and the tree is not rebalancing correctly, and I want to catch that error and fix it. In other words writing the Identity there makes it harder to catch a potential bug! That sounds not good.

4

I would be interested in seeing the code that calls single_L as well. Since it’s already doing the pattern matching, can it pass in el, rlst, and rrst instead of rst?

3 Likes
5

“No runtime errors” is a very high priority for Elm. This means that you are not allowed to create functions that can fail. (Unless you’re implementing a core function like modBy 0.) The unsatisfying the solution of choosing a default value is probably your best choice. What I would do is:

  1. Use Debug.todo in your code while developing to mark the impossible branches.
  2. Write exhaustive tests and make sure you never run into those errors.
  3. Replace Debug.todo by a default value.

(You might consider writing a custom wrapper around Debug.todo that already takes a value of the correct type so that you only need to change the definition of your custom wrapper before finalizing the module instead of replacing every occurrence of Debug.todo.)

Unfortunately, there are still two problems:

  1. Having to use different code for development and production builds is annoying.
  2. If you are tasked with producing a value of an unknown type (say you have a function MyTree a -> a and you know that the tree will always contain a value to return but you can’t prove it to the compiler), you’re out of luck and your “infinite recursion” solution is basically your only choice.
6

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.