Matching Patterns for list of tuples

Question

I'm trying to write a fcn that takes in a list of tuple and an expression (I am working on a postfix expression eval). This function should loop through the expression and find the same letter in the tuple. If it's a match then it returns the int value corresponding to that letter in the tuple. When I ran the code below, my program compiled and run but then it was hanging during execution. What did I do wrong?

    let rec getVar ls exp = 

        match ls with
       |head::tl when (fst head) = exp -> printfn "%d" (snd head)
       | _  -> getVar ls exp



    let ls = [("a",5);("b",2);("c",3)]

    let exp = "ab+"
    getVar ls exp

Answer 1

Your match expression has a final catch-all clause (the _ clause) that just calls getVar again with the same parameters. If the when (fst head) = exp condition fails, then code falls through to the catch-all clause, so getVar gets called again with the same parameters, so the first condition will fail, so code falls through to the catch-all clause, so getVar gets called again... It's an infinite loop.

What you probably meant to do was call getVar again on the tail of the list if your when condition failed:

match ls with
|head::tail when (fst head) = exp -> printfn "%d" (snd head)
|head::tail -> getVar tail exp

You also need to think about what you'll do if the list is empty (i.e., you need a match condition that matches against []). I'll leave that one up to you, since there are many things you could want to do with an empty list and it's not obvious which one you'd want.

Answer 2

Your match must handle three cases.

1. Empty list -> return some default value (or unit without side effects)
2. Match found -> return a value or trigger some side effect.
3. Match not yet found -> keep searching in tail of list.

In your first attempt, you accidentally kept searching in the whole list instead of merely the tail, resulting in an endless recursive loop. In your second attempt, you instead created an infinite loop in the empty case. Below is one example of how you might write the recursive function.

 let rec getVar ls exp =
     match ls with
     |[] -> None
     |head::tail when (fst head) = exp -> Some <| sprintf "%d" (snd head)
     |head::tail  -> getVar tail exp

 let ls = [("a",5);("b",2);("c",3)]

 let result1 = getVar ls "ab+"   // result = None
 let result2 = getVar ls "b"     // result = Some "2"

Answer 3

The signature of your getVar function in a wrong. The last parameter should be a letter of the expression, not the whole expression. The code calling the getVar function would go through the expression, for each character, check if it is a letter, if yes then call getVar, otherwise then do other things.

The reason why you code gets hanged is explained clearly in the other answers so I won’t repeat here. But as a good practice, please don’t use | _ -> ... unless you totally control the situation. Typically, we should explicitly write all the matching conditions, so that if we miss something, compiler will warn us. After that, when being aware all the conditions, we can use | _ -> ... if it really means “the rest conditions”.

Your getVar function can be rewritten as:

let rec getVar ls letter =
    match ls with
    | [] -> ()
    | head :: tail when fst head = letter -> printfn "%d" (snd head)
    | _ :: tail -> getVar tail letter

I suggest you learn the common built-in functions of F# core library. So you can use the List.tryFind function in your problem:

let getVar ls letter =
    ls |> List.tryFind (fun (key, value) ->
                 if key = letter then
                     printfn "%d" value
                     true
                 else false)

The more you can use bult-in functions, the less bugs you have.