Почему моя функция поиска всегда выводит true? - PullRequest
Новая
       75

Почему моя функция поиска всегда выводит true?

0 голосов
/ 27 сентября 2019 
let rec contains (x: int list)(y: int) : bool =
begin match x with
| [] -> false
| [y] -> true
| hd::tail -> (hd = y) && (contains tail y)
end

Я не уверен, где я ошибаюсь при сопоставлении с образцом, но для любого непустого списка, который я ввожу, я продолжаю получать "true" в качестве возвращаемого типа, когда я хочу, чтобы он возвращал только trueесли входной int существует в списке.

1 Ответ

3 голосов
/ 27 сентября 2019

У вас есть несколько проблем.Во-первых, вы используете сопоставление с образцом, чтобы проверить, является ли список точно [y].Это не то, как это работает, это будет фактически соответствовать любому списку с ровно одним элементом.Если вы хотите указать такие равенства, вы можете использовать предложения when. 

let rec contains (l : int list) (y : int) : bool =
  begin match l with
  | [] -> false
  | [z] when z = y -> true
  | [z] -> false
  | hd :: tl -> hd = y && contains tl y
  end

Первые [z] when z = y сработают в списке, содержащем именно ваш y.Второе предложение [z] сработает по остальным.

Затем возникает проблема вашего последнего случая: y принадлежит hd :: tl, если это hd или если он принадлежит tl.Вы использовали и , так что это не могло быть правильно.Это дает нам: 

let rec contains (l : int list) (y : int) : bool =
  begin match l with
  | [] -> false
  | [z] when z = y -> true
  | [z] -> false
  | hd :: tl -> hd = y || contains tl y
  end

Конечно, это даже можно упростить. 

let rec contains (l : int list) (y : int) : bool =
  begin match l with
  | [] -> false
  | hd :: tl -> hd = y || contains tl y
  end

Действительно, нет необходимости создавать особый случай списка с одним элементом.[y] совпадает с y :: [].

Итак, если подвести итог, если элемент находится в голове, вы его получили, в противном случае вы идете смотреть в хвост и так далее, пока не достигнете пустогосписок, который означает, что вы не нашли его.

...