Recursion in F# | What's happening?

Question

I've found a basic example of an f# recursive function that takes a list and returns a list of only even integers. I understand it for the most part, but there's a little i'm confused about.

let numbers = [1..4]
let rec even ls =
   match ls with
   | [] -> []  
   |head :: tail when head % 2 = 0 -> head :: even tail
   |_::tail -> even tail 

The line that matches head confuses me. This is how I read it. Append head to tail when head is even, then call even tail again. Because we appended head to tail, wouldn't that just get caught in a loop of adding head over and over again?
Also, the final line _::tail I assume means "do nothing, recurse again", but I looked up the operator _ in f# and it says it's a wildcard pattern. Does that essentially mean if not covered by either of my first two matches, do this thing?

Hoping someone can clarify! f# looks like a lot of fun, but coming from an imperative background it's difficult to understand.

Answer 1

This is a pattern matching expression. The way to read each line is this: to the left of the arrow -> is the instruction of how to inspect the data, and to the right of the arrow is the instruction of what to do with the results of inspection.

Applying this to your case, follow the comments (I've inserted some newlines for clarity):

match ls with    // Look at `ls`

| [] ->        // when `ls` is an empty list,
    []         // return an empty list

| head :: tail            // when `ls` is a `head` attached to a `tail`, 
    when head % 2 = 0 ->  // AND `head` is an even number,
    head :: even tail     // call `even tail`, attach `head` to it, and return that result

| _::tail ->     // when `ls` is "something" attached to a `tail`,
    even tail    // call `even tail` and return that result

Note that the very last case will apply in all situations in which the second case applies. This ambiguity is resolved by the order of the cases: the program will attempt to match ("look at", "inspect") the datum according to each case in turn, and will execute code for the first case that matches.

Another subtle point that you seem to be missing: immutability. The list is immutable. You cannot "update" ("change", "alter") the list in place. If you have a list, it will always stay that way, the compiler guarantees it. Instead, the way data evolves through the program is by creating new data based on the old ones. In particular, if you say a :: b, this does not modify the list b, but instead creates a new list, in which a is head and b is tail.

These are pretty basic concepts in F#, and the fact that you're missing them suggests to me that you've only just started looking at the language (and perhaps at functional programming in general). If this is true, I recommend first reading some introductory material to familiarize yourself with basic concepts. My favourite is fsharpforfunandprofit.com, I can't recommend it enough.

Answer 2

Append head to tail when head is even, then call even tail again. Because we appended head to tail, wouldn't that just get caught in a loop of adding head over and over again?

Close but not quite. It's prepending head onto the list returned by recursing even tail. With each recursion the tail value in this pattern matching expression has one less item in it.

Also, the final line _::tail I assume means "do nothing, recurse again", but I looked up the operator _ in F# and it says it's a wildcard pattern. Does that essentially mean if not covered by either of my first two matches, do this thing?

_ can be a wildcard pattern, but in this pattern matching example it simply indicates we don't care about the head value when we destructure the list; we only care about the tail. This clause (because it comes after the clause that tests for evenness) causes non-even head values to be discarded.

Answer 3

You are dealing with immutable data-types (immutable list) here. This means lists are not changed, every operations creates and returns a new list.

Pattern Matching is a way to deconstruct data into multiple pieces. As an example. If you have the list [1;2;3;4] and you write.

let list = [1;2;3;4]
let (head :: tail) = list

Then head is the value 1. tail is the list [2;3;4] and list is still [1;2;3;4].

Let's go through your example step-by-step.

even [1;2;3;4] is called. Then there are three cases with Pattern Matching. The first one checks if [1;2;3;4] is an empty list. Its not so it checks the next one. head :: tail extracts the list into two pieces like above. So head is 1 and tail represents [2;3;4], but when head % 2 = 0 adds a conditional. It checks if head (currently 1) is dividable by two. It isn't, so it goes to the last Pattern Matching.

The last one is _::tail. First it does the exact same as head::tail. It extracts the first value 1 and stores it in the variable _. The reason to use _ as a variable name is to clarify that the first name is never used. You also could change _ to head and the code works the same.

The last Pattern Match matches, and now you have 1 stored in _ and [2;3;4] stored in tail. And all you do is call even tail. Or in that case, you call even [2;3;4] and return the result of this function call as your result.

When even [2;3;4] is called it does the same above.

It checks if its an empty list. It's not. Then it extract the first value 2 in head and [3;4] into tail. It checks the when condition. This time it is true. So now it executes head :: even tail

Or if we replace the values we get 2 :: even [3;4]

:: is a concatenation of a list, but before we can concatenate a list, first the function call even [3;4] needs to return a list. So even [3;4] is called.

This then checks again.

1. Is [3;4] an empty list. Nope.
2. Is the head the value 3 dividable by 2. Nope.
3. Extract 3 into _ and [4] into tail, and call even [4].

even [4] then does the same:

1. Is [4] an empty list. Nope.
2. Is the value 4 assigned to head an even number? Yes it is. So 4 :: even [] is called.

even [] then does the same:

1. Is [] an empty list. Yes it is. So return the empty list. []

Then it goes backwards.

-> means "returns"

even []         -> []
4 :: even []    -> [4]
even [3;4]      -> [4]
2 :: even [3;4] -> [2;4]
even [2;3;4]    -> [2;4]
even [1;2;3;4]  -> [2;4]