Создание списка целых чисел в OCaml без рекурсии

Как я могу использовать одну из функций fold для создания списка целых чисел от 0 до значения n-1? Я не понимаю, как заставить fold_right возвращать список, а не возвращать только накопленное значение.

Это для вспомогательной функции, которую я пытаюсь определить для решения более крупной проблемы. Вот моя попытка:

-Я знаю, что в базовом случае должен быть список, содержащий только ноль, потому что я не хочу добавлять ничего меньше нуля.
-Я знаю, что мне нужно уменьшить значение n, чтобы я мог поставить числа из n- от 1 до 0 в списке.

let buildList n = 
  let ibuildList elem list =
    list@[n-1]
  in List.fold_right ibuildList n [0];;

Но я получаю сообщение об ошибке, подчеркивая «n» в последней строке, говоря, что выражение имеет тип int, но ожидалось выражение типа «список». Разве n не является целым числом, которое я превращаю в список через [n-1]? Где я ошибся?


list fold ocaml
person jonnyd42    schedule 17.04.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Складка предназначена для обхода коллекции. Поскольку вы хотите сгенерировать список, и у вас есть только n, а не коллекция, вы не можете использовать fold каким-либо разумным образом. На самом деле то, что вы хотите сделать, больше похоже на развертывание. То есть вы хотите развернуть свой n в список.

Эту функцию легко написать, но не так просто написать ее с помощью свертки.

Вот реализация развертывания в OCaml:

let rec unfold_right f init =
    match f init with
    | None -> []
    | Some (x, next) -> x :: unfold_right f next

Вот как использовать unfold_right для создания списка целых чисел:

let range n =
    let irange x = if x > n then None else Some (x, x + 1) in
    unfold_right irange 1

Вот как это выглядит при запуске range:

# range 0;;
- : int list = []
# range 8;; 
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]
# range 5;;
- : int list = [1; 2; 3; 4; 5]
person Jeffrey Scofield    schedule 17.04.2016
comment
Не могли бы вы опубликовать пару примеров накопленных значений, которые являются чем-то другим, кроме целого числа? - person jonnyd42; 17.04.2016
comment
Я добавил два примера; Надеюсь, хоть один из них окажется полезным :-) - person Jeffrey Scofield; 17.04.2016
comment
Хорошо, поигрался с кодом. Немного запутался. Я обновил свой первоначальный вопрос, указав в нем некоторый код и проблему, с которой я столкнулся. Спасибо! - person jonnyd42; 17.04.2016
comment
Извините, я не до конца продумала вашу проблему. Я прошу прощения. Я начал с лучшего ответа. - person Jeffrey Scofield; 17.04.2016
comment
Вы говорите, что эту функцию легко написать, и я могу сделать это с помощью рекурсии, но я готовлюсь к тесту и не смогу использовать на нем рекурсию. (пытаясь заставить нас использовать функции более высокого порядка.) - person jonnyd42; 18.04.2016
comment
Вы можете использовать разворачивание, я добавил пример кода. Не уверен, что это поможет вашему тесту. - person Jeffrey Scofield; 18.04.2016
comment
@jonnyd42: Другой пример, который не является просто целым числом: развертка, используемая для транспонирования матрицы - person Simon Shine; 18.04.2016
comment
@ jonnyd42 Если это просто тест, в котором вам необходимо использовать функции более высокого порядка, вы можете использовать функциональность Array, например. let makelist n = Array.init n (fun x -> x) |> Array.to_list. Для более практичных вариантов использования различные стандартные расширения библиотек (такие как батареи, контейнеры или ядра) имеют встроенную функцию List.init, которая отсутствует в обычном модуле List. - person Reimer Behrends; 18.04.2016

arrow_upward
1
arrow_downward

Альтернативная версия, использующая стандартный модуль Stream:

(* an infinite stream of natural numbers, starting from 0 *)
let nats =
  let rec nats_from n = [< 'n; nats_from (n + 1) >]  (* extra syntax *)
  in nats_from 0

(* the first n natural numbers: [0; n-1] *)
let range n = Stream.npeek n nats

Часть [< 'n; nats_from (n + 1) >] представляет собой ленивый список с n в начале и следующими натуральными числами в конце. Stream.npeek n stream использует первые n элементов stream и возвращает их в виде списка.

Тесты с utop:

utop # #load "dynlink.cma";; (* you need these to work with *) 
utop # #load "camlp4o.cma";; (* the Stream's syntactic extension *)

utop # range 1;;
- : int list = [0]    

utop # range 5;;
- : int list = [0; 1; 2; 3; 4]

utop # range 10;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

Если вы хотите скомпилировать его, используйте следующие команды (вам нужно использовать препроцессор camplp4o):

$ ocamlc -pp camlp4o <filename>.ml

or

$ ocamlopt -pp camlp4o <filename>.ml
person Anton Trunov    schedule 20.04.2016