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

Question

Как мне составить ленивый список, представляющий последовательность удваивающихся чисел? Пример:

1 2 4 8 16 32

Answer 1

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

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

или

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)))

Answer 2

У замечательного блога есть прекрасная статья на эту тему:

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 существуют для отложенной обработки списка?

Answer 3

Кроме того, в моей среде сетевого приложения OCaml Core Foundation есть модуль отложенного списка Cf_seq. На самом деле я написал целый ряд функциональных структур данных. Это все доступно под лицензией BSD с 2 пунктами. Наслаждайтесь.

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

Answer 4

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

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

  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