CODEWITHSUNDEEP
listrecursionf#tuples
Podo
Podo

Reputation: 709

Search list of tuples f#

Say that I have a self made dictionary made from a list of tuples
let menu = [("pizza",17);("hotdog",5);("burger", 12);("drink",3);("milkshake",4)]
I want to write a search function that takes both my dictionary and a key value as a parameter, then returns an option type with the value if key can be found in dict, and None if it can't.

I feel like this is a problem built around f# recursion, using and returning option types as well as obtaining individual values from a tuple, but I'm having a hell of a time putting them together and getting anything that comes even remotely close to accomplishing this task.

I've come up with some pseudo-code that I believe would solve the problem, but actual f# implementation is another story. In an imperative language this seems like a trivial problem, but trying to grasp functional has been really difficult. 

//create function `search` accepts dictionary and search key
//match searchkey with dictionary key 
//if searchkey = dictionary key, return option type w/ value
//if searchkey <> dictionary key, recurse call next dict values
//if end of dictionary, doesn't exist, return none 

//Here's a *very* rough sketch of what I think should be happening.

let rec search dict key =
match dict with 
//first check for an empty list, if empty return None
| [] -> None
//next check that there is a head and a tail for dict
//also check for match between first element of head and key
//if match, return hd
//still needs to return option type though, but how?
| hd :: tl when fst hd = key -> snd hd
//finally call search on the tail
| _ :: tl -> search tl key

The empty list condition and the wildcard pattern I'm fairly sure are correct, but it's the actual check and return that im stuck on. How might I go about that particular step?

Upvotes: 2

Views: 1265

Answers (2)

David Raab
David Raab

Reputation: 4488

They way to think about recursion, is to just get one example right. And leave the remaining list to the recursive function. And you must somehow accomplish that the "remaining" list gets smaller.

First, you deal with a list. One way to think about it is to just check one element at a time. So you extract the first element of a list, do something with it, then repeat the recursive function on the remaining list. So you could start with:

let search key lst =
    match lst with
    | head :: tail ->

Think of your example list, in this case. The first invocation of your example list your head would be ("pizza",17).

The next step you now need to-do is. Deconstruct the tuple into key and value and check them. You deconstruct it with

let (k, v) = head

Then you need to check if your k is equal to key. If it is equal, then you want to return the value.

if k = key 
then Some v

The else branch must handle the case where your k is not the key you search. This is the recursive step. You want to repeat the checking on the remaining list items.

else search key tail

Remember at this point tail is now your menu with the first element removed. Currently you have the following code.

let rec search key lst =
    match lst with
    | head :: tail ->
        let (k, v) = head
        if   k = key
        then Some v
        else search key tail

But this code does not handle the case when it cannot find your item. Think what would happen if the if k = key is never true! It will remove one-element at a time, then recursive on the remaining list until you end up with the empty list.

Empty list then means, you didn't find the key. To be successful you now need to add a case for the empty list. In that case your key is not in your list, and you must return "None". So you end up with:

let rec search key lst =
    match lst with
    | [] -> None
    | head :: tail ->
        let (k, v) = head
        if   k = key
        then Some v
        else search key tail

Upvotes: 1

TheQuickBrownFox
TheQuickBrownFox

Reputation: 10624

Patterns can be nested inside other patterns. The tuple pattern (a, b) can be nested inside the list head/tail pattern head :: tail like this: (a, b) :: tail

This means the second pattern match can look like this (k, v) :: _ when k = key.

You need to return an option from every branch, so either a Some x or a None. The second match branch was missing a Some wrapper.

The code with both changes:

let rec search dict key =
    match dict with       
    | [] -> None
    | (k, v) :: _ when k = key -> Some v
    | _ :: tl -> search tl key

Upvotes: 4

Related Questions