Блог

пожалуйста, помогите. Я пытаюсь написать две нерекурсивные функции в OCaml (список списков содержит элементы, которые сами являются списками).

1. clear l который принимает список списков в качестве аргумента и возвращает список списков без пустых списков, если таковые имеются. Пример: clear [[2];[];[];[3;4;6];[6;5];[]] возврат воли [[2];[3;4;6];[6;5]]
2. sort_length l это сортирует элементы этого списка l в соответствии с их длиной. Например sort_length [[2];[];[3];[6;5]] , возвращает [[];[2];[3];[6;5]]

Мне разрешено использовать только эти предопределенные функции: Список.фильтр, Список.сортировка, Список.hd, List.tl, Список.длина и никаких других. Спасибо

Для второй функции я пробовал это до сих пор, но использовал map то, что запрещено

 let rec insert cmp e = function
  | [] -> [e]
  | h :: t as l -> if cmp e h <= 0 then e :: l else h :: insert cmp e t
  
let rec sort cmp = function
  | [] -> []
  | h :: t -> insert cmp h (sort cmp t)

let sort_length l =
  let l = List.map (fun list -> List.length list, list) l in
  let l = sort (fun a b -> compare (fst a) (fst b)) l in
  List.map snd l;; 
 

Спасибо

Как уже упоминалось здесь: https://ocaml.org/api/List.html#VALfilter, List.filter возвращает все элементы списка, удовлетворяющие заданному предикату. Поэтому вы должны написать предикат, описывающий список, который не является пустым. Другой способ сказать, что список не пуст, — это сказать, что «его размер больше нуля». Так что можно было бы сформулировать clear таким образом:

 let clear list = 
  let is_not_empty l = (List.length l) > 0 in
  List.filter is_not_empty list
 

Небольшое редактирование

Как упоминал Крис Даттон, использование List.length может быть неэффективным. Другой подход состоял бы в том, чтобы выразить is_not_empty это таким образом:

  let is_not_empty = function 
 | [] -> false 
 | _  -> true
 

Этот подход «лучше», потому что он не требует просмотра всего списка, чтобы увидеть, пуст он или нет.

Во втором пункте List.sort функция принимает функцию сравнения между двумя элементами ( 'a -> 'a -> int ), здесь сравнение должно действовать на размер списков.

Другими словами, необходимо сравнить размер двух наблюдаемых списков. Один из способов сделать это-использовать Int.compare (https://ocaml.org/api/Int.html#VALcompare) по размеру двух наблюдаемых списков. Например:

 let sort_length list = 
  let compare_length a b = 
     let la = List.length a in 
     let lb = List.length b in 
     Int.compare la lb
   in 
   List.sort compare_length list
 

Существуют более лаконичные способы написания этих двух функций, но эти реализации должны быть достаточно ясными.