How do i find a base case for this function?-CodePudding

So i'am working around an exercise that should be a very basic and easy function

Whish takes as argument a string and a list and should return None if there string is not in the list and return some list where the string has been removed from the list. This is an 2015 exam set i am practising and using List. functions is not allowed

So far i've managed to come up with this

let rec fromShelf bs ls = 
   match ls with
      |[] -> None
      |h::tl when h=bs -> Some tl
      |h::tl -> Some (h::Option.get(fromShelf bs tl))

However this loop will run forever in case the string is not in the list and i'am suppose to preserve the list while iterating so i am really stuck.. would appreciate any help or hints.

CodePudding user response：

If the head does not equal the item we're looking to exclude, we should run the function on the tail. It that returns None, our function returns None. Otherwise we can use pattern-matching (without Option.get) to extract the list returned, prepend the head onto it, and wrap that all back up with Some.

let rec fromShelf bs ls = 
  match ls with
  | [] -> None
  | h::tl when h = bs -> Some tl
  | h::tl -> 
    match fromShelf bs tl with
    | None -> None
    | Some lst -> Some (h :: lst)

If we evaluate a simple example:

fromShelf "a" ["b"; "c"; "a"; "d"]

The result is:

Some ["b"; "c"; "d"]

CodePudding user response：

Actually I think its a bit of a trick question. Chris's answer only removes the 1st instance of the string (I think), if that's good enough, then I'd go with that, if it isn't, then its asking for something that isn't directly recursive in a nice simple way.

The issue being that in order to recursively return None or Some in the base case, you need to know if there was a match in any non base case.

If you want to do it directly then you need to track whether there was a match in the non base cases

let weirdFilter bs ls =
    let rec weirdFilterInner bs ls isFound =
        match ls with
        | [] when isFound = true -> 
            Some []
        | [] -> 
            None
        | h :: tl when h = bs -> 
            weirdFilterInner bs tl true
        | h :: tl -> 
            match weirdFilterInner bs tl isFound with
            | None -> 
                None
            | Some xs -> 
                Some (h :: xs)
    weirdFilterInner bs ls false

so there are 2 base cases, an empty list and a non base case found a match, and an empty list and a non base case didnt find a match.