Ocaml: Ленивые списки

Использование потоков:

let f x = Stream.from (fun n -> Some (x * int_of_float (2.0 ** float_of_int n)))

or

let f x =
  let next = ref x in
    Stream.from (fun _ -> let y = !next in next := 2 * y ; Some y)

Используя собственный тип lazy_list:

type 'a lazy_list =
  | Nil
  | Cons of 'a * 'a lazy_list lazy_t
let rec f x = lazy (Cons (x, f (2*x)))

В великом блоге с неограниченным умом есть отличная статья на эту тему:

http://enfranchisedmind.com/blog/posts/ocaml-lazy-lists-an-introduction/

Вы также можете проверить http://batteries.forge.ocamlcore.org/doc.preview%3Abatteries-beta1/html/api/Lazy%5Flist.html

которая является стандартной библиотекой для решения этой проблемы.

Этот вопрос также очень похож на этот вопрос:

Какие библиотеки OCaml существуют для ленивой обработки списков?

Кроме того, в моем OCaml Network Application Environment Core Foundation есть модуль отложенного списка под названием Cf_seq. Фактически, я написал целый ряд функциональных структур данных. Все это доступно по лицензии BSD с двумя пунктами. Наслаждаться.

Обновление: код был переименован в "Oni" и теперь размещен на BitBucket. Вы также можете использовать для этого пакет GODI.

Если вы хотите сделать это вручную, я бы сказал, что у вас есть основные варианты:

• Используйте собственный тип lazy_list, как сказал ephemient (за исключением того, что его решение немного не работает):

  type 'a lazy_list =
      | Nil
      | Cons of 'a * 'a lazy_list
  
  let head = function
      | Nil -> failwith "Cannot extract head of empty list"
      | Cons (h, _) -> h
  
  let tail = function
      | Nil -> failwith "Cannot extract tail of empty list"
      | Cons (_, t) -> t
  

• Используйте своего рода преобразователь (например, то, что используется для реализации ленивых вычислений на языке, который его не поддерживает). Вы определяете свой список как функцию unit -> 'a, которая говорит, как получить следующий элемент из текущего (нет необходимости использовать для этого потоки). Например, чтобы определить список всех натуральных целых чисел, вы можете сделать

  let make_lazy_list initial next =
      let lazy_list current () =
          let result = !current in
          current := (next !current); result
      in lazy_list (ref initial)
  
  let naturals = make_lazy_list 0 (function i -> i + 1)
  

  Если вы это сделаете

  print_int (naturals ());
  print_int (naturals ());
  print_int (naturals ())
  

  вы получите следующий результат:

  0
  1
  2