Ошибка типа при использовании списков накопления рекурсии

Question

Словарь представляет собой список пар. Задача состоит в том, чтобы взять словарь и вернуть пару списков: ключи и значения.

Я попытался сделать это, итерируя (используя рекурсию) по словарю и накапливая ключи и значения в двух списках, но я получаю ошибку типа, которая меня озадачивает.

Примечание: Я не знаю НЕ ищет альтернативное решение задачи. Я хочу понять ошибку и как ее исправить.

Вот код:

let lists_of_dict dict = 
    let rec separate dict keys values = 
    match dict with 
     [] -> (keys, values) 
    | (k, v)::t -> separate t k::keys v::values 
       (* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ *) 
    in 
    separate dict [] [] 

(подчеркнутая часть символов 19-47 из строки 5)

Вот сообщение об ошибке:

File "lod-problem.ml", line 5, characters 19-47: 
Error: This expression has type 'a list 
     but an expression was expected of type 'b * 'c 

Я могу» t понять, почему Ocaml выводит этот тип и как понять, что выражение имеет тип ('a list * 'b list) (если я не ошибаюсь).

Answer 1

separate t k::keys v::values анализирует как (separate t k) :: (keys v) :: values, а не separate t (k::keys) (v::values), как вы и предполагали.

Так OCaml видит, что вы строите результат с помощью :: и, таким образом, результатом будет список (не говоря уже о том, что аргументы в пользу :: также имеют неправильный тип - тип проверки никогда не получает, что далеко), но ожидаемым результатом является кортеж (потому что это то, что было сделано первым). Поэтому в этот момент ошибка проверки типов.