Блог

Главная - Вопросы по программированию - Почему моя функция типа ‘a list * ‘ является списком -> ‘b list?

Почему моя функция типа ‘a list * ‘ является списком -> ‘b list?

#recursion #functional-programming #type-inference #sml #smlnj

#рекурсия #функциональное программирование #вывод типа #sml #smlnj

Вопрос:

Я думаю, я хочу, чтобы это было типа ‘список * ‘список -> ‘список .

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

  • пересечение ([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. Почему вы пометили это как matlab? Очевидно, что это какой-то вариант ML, а не matlab. Я предполагаю, что SML?

2. Извините, я не понимал, что есть какая-то разница. Я думаю, это SMLNJ.

3. @Nate: ML не имеет ничего общего с matlab. ML — это функциональный язык, MatLab является обязательным.

4. Я чувствую себя глупо… Я предположил, что ML — это MatLab. Извините за эту путаницу.

5. «ML» в качестве названия семейства языков происходит от «метаязыка». Первый вариант ML был изобретен Робином Милнером и другими, чтобы стать метаязыком среды проверки. По сей день несколько сред проверки написаны на каком-то варианте ML, а тактика для Coq может быть предоставлена в виде функций OCaml (я не знаю о других).

Ответ №1:

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

 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)

Комментарии:

1. В своем мнении о моем базовом варианте вы абсолютно правы. Я был сбит с толку этим в своей голове. Ваша функция go также лучше, чем моя. Первоначально я установил intersection_acc как функцию-накопитель вне пересечения с кортежем, содержащим три параметра (для работы независимо от пересечения), но не подумал избавиться от ненужного (и неизмененного) второго списка в моем кортеже. Большое спасибо!

Метки: