Перечисление всех пар, которые можно построить из двух ленивых списков в OCaml

Я пытаюсь перечислить набор всех пар, состоящих из элементов из двух ленивых списков (первый элемент из первого списка, второй элемент из второго списка) в OCaml, используя обычную идею диагонализации. Идея, строго говоря, выглядит примерно так:

enum [0;1;2;...] [0;1;2;...] = [(0,0);(0,1);(1;0);(0;2);(1;1);(2;2);...]

У меня вопрос: как это определить «лениво»?

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

Я определил ленивые списки как

type 'a node_t =
   | Nil
   | Cons of 'a *'a t
and 'a t = ('a node_t) Lazy.t

Затем я определил функцию seq

let seq m =
   let rec seq_ n m max acc =
           if n=max+1
               then acc
               else (seq_ (n+1) (m-1) max (lazy (Cons((n,m),acc))))
in seq_ 0 m m (lazy Nil)

что дает мне ленивый список пар (x, y) таких, что x + y = m. В этом суть диагональной идеи. Мы начинаем с перечисления всех пар с суммой 0, затем всех пар с суммой 1, затем пар с суммой 2 и т. Д.

Затем я определил функцию enum_pair

let enum_pair () = 
  let rec enum_pair_ n = lazy (Cons(seq n,enum_pair_ (n+1)))
in enum_pair_ 0

который генерирует бесконечный ленивый список, состоящий из: ленивого списка пар с суммой 0, конкатенированных с ленивыми списками пар с суммой 1 и т. д.

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

Мне кажется, что мне пришлось бы использовать некую форму конкатенации списков (ленивый эквивалент @). Но это неэффективно, потому что в моем представлении ленивых списков объединение двух списков имеет сложность O (n ^ 2), где n - размер первого списка. Стоит ли мне использовать другое представление ленивых списков? Или есть другой способ (без использования seq и enum_pair выше), который не требует конкатенации списков?

Любая помощь могла бы быть полезна.

Большое спасибо, Сурикатор.


list lazy-evaluation ocaml
person Surikator    schedule 19.10.2010    source источник

Ответы (2)


arrow_upward
1
arrow_downward

В Haskell вы можете написать:

concatMap (\l -> zip l (reverse l)) $ inits [0..]

Сначала мы генерируем все начальные сегменты [0..]:

> take 5 $ inits [0..]
[[],[0],[0,1],[0,1,2],[0,1,2,3]]

Если взять один из сегментов и закрепить его обратной стороной, получится одна диагональ:

> (\l -> zip l (reverse l)) [0..4]
[(0,4),(1,3),(2,2),(3,1),(4,0)]

Таким образом, отображение zip даст все диагонали:

> take 10 $ concatMap (\l -> zip l (reverse l)) $ zipWith take [1..] (repeat [0..])
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]
person Daniel    schedule 19.10.2010
comment
Спасибо, Даниэль, это очень полезно. Можете ли вы обобщить это, чтобы заставить его работать с n ленивыми списками (т.е. выбрать все n-кортежи, которые можно выбрать из n списков)? Спасибо! - person Surikator; 19.10.2010
comment
Генерация k-кортежей для k ›2 не так-то просто. Я думаю, что это сводится к созданию комбинаций с повторением k элементов из n возможных, когда вам нужна k-мерная диагональ с элементами, сумма которых равна n. - person Daniel; 19.10.2010

arrow_upward
1
arrow_downward

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

let rec enum_pair_cat ls =
lazy(
    match Lazy.force ls with
        | Nil             -> Nil
        | Cons(h,t) -> match Lazy.force h with
                                        | Nil -> Lazy.force (enum_pair_cat t)
                                        | Cons (h2,t2) -> Cons (h2,enum_pair_cat (lazy (Cons (t2,t))))
)

Эта новая функция обеспечивает желаемое поведение. При выполнении

enum_pair_cat (enum_pair ())

мы получаем ленивый список, в котором пары пронумерованы, как описано. Итак, это решает проблему.

Однако меня это не совсем устраивает, потому что это решение не масштабируется до более высоких перечислений (скажем, трех ленивых списков). Если у вас есть идеи, как решить общую проблему перечисления всех n-кортежей, взятых из n ленивых списков, дайте мне знать!

Спасибо, Сурикатор.

person Surikator    schedule 19.10.2010