Ocaml - тип параметра при проверке дубликатов в списке - PullRequest
Новая
       36

Ocaml - тип параметра при проверке дубликатов в списке

5 голосов
/ 07 апреля 2011

У меня есть базовая функция, которая проверяет список на наличие дубликатов и возвращает true, если они найдены, в противном случае - false. 

    # let rec check_dup l = match l with
        [] -> false
      | (h::t) ->
        let x = (List.filter h t) in
        if (x == []) then
           check_dup t
        else
           true
    ;;

Тем не менее, когда я пытаюсь использовать этот код, я получаю ошибку 

    Characters 92-93:
          let x = (List.filter h t) in
                                 ^
    Error: This expression has type ('a -> bool) list
           but an expression was expected of type 'a list

Я не совсем понимаю, почему это происходит, откуда берется тип списка a-> bool?

Ответы [ 2 ]

8 голосов
/ 07 апреля 2011

Тип ('a -> bool) list происходит от типа filter и от сочетания с шаблоном h::t в комбинации. Вы просите использовать один элемент списка h в качестве предиката , который будет применяться к каждому элементу списка t. Система типов ML не может выразить эту ситуацию. filter ожидает два аргумента, один из которых имеет тип 'a -> bool, где 'a неизвестен, и второй аргумент типа 'a list, где 'a - это такой же неизвестный тип, как в первом аргумент. Поэтому h должен иметь тип 'a -> bool, а t должен иметь тип 'a list.

Но вы также написали h::t, что означает, что существует другой неизвестный тип 'b такой, что h имеет тип 'b, а t имеет тип 'b list. Сложите это вместе, и вы получите этот набор уравнений: 

'a -> bool == 'b
'a list == 'b list

Средство проверки типов смотрит на это и решает, может быть, 'a == 'b, что приводит к более простой проблеме 

'a -> bool == 'a

и он не может найти никакого решения, поэтому он блеет.

Ни простая форма, ни исходное уравнение не имеют решения.

Вы, вероятно, ищете List.filter (fun x -> x = h) t, и вам, вероятно, было бы еще лучше использовать List.exists.

0 голосов
/ 14 декабря 2015

Для завершения этого ответа я выкладываю последнюю функцию для поиска повторяющегося значения в массиве: 

let lstOne = [1;5;4;3;10;9;5;5;4];;

let lstTwo = [1;5;4;3;10];;

let rec check_dup l = match l with
    [] -> false
    | (h::t) ->
       let x = (List.filter (fun x -> x = h) t) in
         if (x == []) then
            check_dup t
         else
       true;;

и при запуске функции: 

# check_dup lstOne

- : bool = true

# check_dup lstTwo

- : bool = false

#
...