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

Question

Я пытаюсь перечислить набор всех пар из элементов из двух ленивых списков (первый элемент из первого списка, второй элемент из второго списка) в 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 

Тогда я определил функцию «Последовательность»

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) 

, который дает мне ленивым список пар (х, у) такой, что х + у = т. Это и есть диагональная идея. Начнем с перечисления всех пар, сумма которых 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» выше), который не требует конкатенации списка?

Любая помощь была бы действительно оценена.

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

Answer 1

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

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

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

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

Taking один из сегментов сжать его с обратной дает нам одну диагональ:

> (\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)] 

Answer 2

В то же время мне удалось куда-то добраться, но, хотя она решает проблему, решение не очень элегантно. После определения функций, определенных в моем первоначальном вопросе, я могу определить дополнительную функцию «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 ленивых списков, дайте мне знать!

Thanks, Surikator.