Почему моя функция типа 'список *' список -> 'список б? - PullRequest
Новая
       47

Почему моя функция типа 'список *' список -> 'список б?

2 голосов
/ 30 октября 2011

Мне кажется, я хочу, чтобы это был тип 'список *' список -> 'список.

пересечение должно возвращать пересечение двух списков пример ввода и вывода:

  • пересечение ([1], [1]);
    • [1]
  • пересечение ([1,2,3], [1,2]);
    • [1,2]
  • пересечение ([[2,3], [1,2], [2,3]], [[1], [2,3]]);
    • [[2,3]]

моя функция: 

fun intersection (l1, l2) = let
    fun intersection_acc (acc, [], h::t) = []
        | intersection_acc (acc, h::t, []) = []
        | intersection_acc (acc, h::t, h2::t2) = if in_list (h, l2)
            then intersection_acc (h::acc, t, l2)    
        else intersection_acc (acc, t, l2)
    in intersection_acc ([], l1, l2)
end

Я не думаю, что проблема в in_list, но это выглядит так: 

 fun in_list (x, []) = false
    | in_list (x, y::r) = if x = y 
    then true 
    else in_list (x, r);

1 Ответ

3 голосов
/ 30 октября 2011

Я предполагаю, что вы запустили базовый случай в своей функции накопителя 

intersection_acc (acc, h::t, []) = []

она, вероятно, должна возвращать что-то в зависимости от acc: 

intersection_acc (acc, h::t, []) = acc

Причина 'b list появляется потому, что пересечение всегда будет возвращать пустой список [].Поскольку вы не используете этот пустой список, компилятор должен быть консервативным и утверждать, что список может быть любого типа.

В любом случае ваша функция выглядит более запутанной.Вы действительно хотите сделать что-то вроде 

result = []
for each item in list1:
    if item in list2:
        add item to result
return result

Перевод этого императивного кода в рекурсивную функцию с параметром аккумулятора: 

fun go(acc, []) = acc
  | go(acc, x::xs) =
        if x in list2 then
            go(x::acc, xs)
        else
            go(acc, xs)

Для полной функции: 

fun intersect(list1, list2) = let
    fun go(acc, []) = acc
      | go(acc, x::xs) =
            if x in list2 then
                go(x::acc, xs)
            else
                go(acc, xs)
    in go([], list1)
...