Перечисление всех пар, конструируемых из двух ленивых списков в OCaml - PullRequest
Новая
       11

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

1 голос
/ 19 октября 2010

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

Любая помощь будет очень признательна.

Большое спасибо, Surikator.

Ответы [ 2 ]

1 голос
/ 19 октября 2010

В Хаскеле вы можете написать: 

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

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

> 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)]
1 голос
/ 19 октября 2010

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

Спасибо, Surikator.

...