CODEWITHSUNDEEP
listrecursionf#booleancontains
Denis
Denis

Reputation: 47

F# List contains

I need help in F#. I need to verify if a number exist in the list, using a recursive function and without using List.contains or something similar. The program should only tell me if it's true or false. for example:

contains(8N, [3N; 8N; 2N]) = true
contains(7N, [3N; 8N; 2N]) = false

What I have until now:

let rec contains(x: Nat, list: Nat list): bool =
    match list with 
    | [] -> false
    | x::xs when x =

Upvotes: 2

Views: 1795

Answers (2)

dumetrulo
dumetrulo

Reputation: 1991

The idea is very simple: traverse a list and check whether its first element is equal to the one you are looking for. If it is, return true, otherwise move on to search the remainder of the list. If the (original or remainder) list is empty, no element satisfied the condition, and so the result is false.

This can be modeled very compactly as a small recursive function:

let rec contains n = function
    | [] -> false
    | x :: xs -> (n = x) || contains n xs

By the way, this function will not only work with lists of integers; it will be automatically generalized to work with lists of any type that supports an equality comparison.

Upvotes: 2

Tomas Petricek
Tomas Petricek

Reputation: 243051

The code you have so far is a good starting point. I'll replace Nat with int which is the type name that F# uses and replace the tupled parameter with a space separated one, which is a more common notation.

One thing you need to do first is to avoid using the name x twice - right now, you have x as the name of the number you're looking for and as the name for the first element of the list. Once you rename them, you can specify the condition in when:

let rec contains (lookingFor:int) (list:int list) : bool =
    match list with 
    | [] -> false
    | firstInList::restOfList when firstInList = lookingFor -> (...)
    | firstInList::restOfList -> (...)

Now, there are two things you need to handle:

  • When firstInList = lookingFor, you want to return true.
  • Otherwise (the last case I added), you need to make the recursive call. You know that firstInList is not the number you're looking for and you need to check if restOfList contains the number - which is a single recursive call to your contains function.

Upvotes: 4

Related Questions