Ошибка в коде, чтобы сгладить список в Ocaml

Question

Привет всем, я пытаюсь сгладить список в Ocaml.Я новичок, поэтому, пожалуйста, извините меня, если моя ошибка немая

Так, например, если ввод [[1]; [2; 3]; [4]], я должен закончить с [1; 2; 3; 4].

Идея, которую я пытаюсь использовать, заключается в следующем. Итерация по списку справа (с использованием fold_right) с accumaltor = [] Псевдокод выглядит следующим образом

func flatten(list,  accumalator) 
  For each item from right to left in list 
     If Item is a scalar then n :: accumalator
     Else fi Item is a list of form head :: tail then
               head :: flatten (tail, accumalator).

Я думаю, чтотеоретически алгоритм верен, но, пожалуйста, дайте мне знать, если вы не согласны.

Теперь к моему OCaml-коду для реализации этого алгоритма

let rec flatten acc x =
    match x with 
           n -> n :: acc
        | [x] -> x :: acc
        | head :: remainder -> 
            head :: ( my_flat acc remainder ) 
 and my_flat = List.fold_right flatten
 ;;

 my_flat [] [[1];[2;3];[4]]

Я получаю следующую ошибку: Это выражениеимеет тип «a, но ожидалось выражение типа» a list

Ошибка возникает в строке, которая читает head :: (my_flat acc remainder) в последнем шаблоне в выражении match

Любая помощь приветствуется.

Answer 1

В OCaml все элементы списка должны быть одного типа.Таким образом, значение [1; [2; 3]; 4] само по себе недопустимо.Он содержит два элемента типа int и один элемент типа int list.По сути, ваше изложение проблемы, которую нужно решить, невозможно.

$ ocaml312
        Objective Caml version 3.12.0

# [1; [2; 3]; 4];;
Characters 4-10:
  [1; [2; 3]; 4];;
      ^^^^^^
Error: This expression has type 'a list
       but an expression was expected of type int

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

Редактировать

ОК, теперь проблема может быть решена!

Суть сообщения об ошибке типа заключается в следующем.У вас есть накопленный результат acc (типа int list в примере).Вы хотите добавить в него список x (также типа int list).Вы разбили x на head (int) и remainder (int list).Как видите, remainder не подходит для вашей функции my_flat.Он хочет int list list, то есть список списков целых.Фактически, ваш рекурсивный вызов почти наверняка должен перейти к flatten, а не к my_flat.

Еще одна проблема, которую я вижу: аргументы List.fold_right: функция, список и начальное значение,При тестовом вызове my_flat последние два вы предоставляете в другом порядке.Пустой список [] - это ваше начальное значение.

Надеюсь, этого достаточно, чтобы вы начали.Поскольку вы только начинаете работать с OCaml, вероятно, перед его работой, вероятно, возникнет еще одна или две проблемы.

Edit 2

Вот еще пара комментариев, которые могутбудьте спойлерами, если вы все еще работаете над собственным решением ....

Более поздняя версия вашей функции my_flat находится в стандартной библиотеке OCaml под именем List.flatten.Интересно взглянуть на реализацию:

let rec flatten = function
    [] -> []
  | l::r -> l @ flatten r

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

Вот один из них, основанный на той же идее, с использованием стандартного трюка с аккумулятором FP ​​для получения рекурсивного поведения хвоста (какзамечено Томасом):

let flatten2 ll =
    let rec go acc = function
    | [] -> List.rev acc
    | l :: r -> go (List.rev_append l acc) r
in
    go [] ll

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

Answer 2

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

let flatten list =
  let rec aux acc list1 list2 =
    match list1 with
      | x :: tail -> aux (x :: acc) tail list2
      | [] ->
        match list2 with
          | [] -> List.rev acc
          | x :: tail -> aux acc x tail
  in
  aux [] [] list

Answer 3

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

let rec flatten = function
  | []          -> []
  | []     :: t -> flatten t
  | (x::y) :: t -> x :: (flatten (y::t))

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

let flatten list =
  let rec aux accu = function
    | []          -> accu
    | []     :: t -> aux accu t
    | (x::y) :: t -> aux (x::accu) (y::t) in
  List.rev (aux [] list)

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

Answer 4

Спасибо за вашу помощь. Вот код, который я использовал для решения этой проблемы

let flatten list  =
    let rec flatten_each acc x =
        match x with 
               [] -> acc
        |  head :: remainder -> head :: ( flatten_each acc remainder )
in
List.fold_right flatten_each ( List.rev list ) []
;;

Редактировать: как указал Томас, это решение не является хвостовым рекурсивным.Хвост рекурсивной версии ниже

let flatten list  =
    let rec flatten_each acc x =
        match x with 
               [] -> acc
            |  head :: remainder -> (flatten_each (acc @ [head]) remainder )
    in
     List.fold_right flatten_each list []
;;