Как исправить функцию zip для ленивого списка (он же «поток»)? - PullRequest
Новая
       6

Как исправить функцию zip для ленивого списка (он же «поток»)?

0 голосов
/ 04 декабря 2018

Я хочу сделать функцию zip, которая будет заключать два ленивых списка в один.Например, ленивый список, показанный как обычный список для большей читабельности, zip [1; 3; 5; 7; 9; 11] [2; 4; 6; 8], возвращает [1; 2; 3; 4; 5; 6; 7; 8; 9; 11].

Я делаю эту функцию: 

type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);;

let zip list1 list2 =
    let rec zipHelper listA listB count = match (list1, list2) with
        | (LCons(xA, xfA), LCons(xB, xfB)) -> 
            if (count mod 2 == 0)
            then LCons(xA, function() -> zipHelper (xfA()) (xfB()) (count + 1))
            else LCons(xB, function() -> zipHelper (xfA()) (xfB()) (count + 1))
        | (LCons(x, xf), LNil) -> LCons(x, function() -> zipHelper (xf()) LNil count)
        | (LNil, LCons(x, xf)) -> LCons(x, function() -> zipHelper (xf()) LNil count)
        | (LNil, LNil) -> LNil
    in zipHelper list1 list2 0
    ;;

let rec ltake = function
    | (0, _) -> []
    | (_, LNil) -> []
    | (n, LCons(x, xf)) -> x :: ltake(n - 1, xf())
    ;;

let a = (LCons(1, function() -> LCons(3, function() -> LCons(5, function() -> LCons(7, function() -> LCons(9, function() -> LCons(11, function() -> LNil)))))));;
let b = (LCons(2, function() -> LCons(4, function() -> LCons(6, function() -> LCons(8, function() -> LNil)))));;
ltake (12, zip a b);;

Функция ltake помогает в тестировании, она возвращает ленивый список в обычный список.Теперь моя функция zip возвращает меня [1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2].

Ответы [ 3 ]

0 голосов
/ 04 декабря 2018

Вот правильный код, который работает: 

let zip list1 list2 =
    let rec zipHelper listA listB count = match (listA, listB) with
        | (LCons(xA, xfA), LCons(xB, xfB)) -> 
            if (count mod 2 == 0)
            then LCons(xA, function() -> zipHelper (xfA()) listB (count + 1))
            else LCons(xB, function() -> zipHelper listA (xfB()) (count + 1))
        | (LCons(x, xf), LNil) -> LCons(x, function() -> zipHelper (xf()) LNil count)
        | (LNil, LCons(x, xf)) -> LCons(x, function() -> zipHelper (xf()) LNil count)
        | (LNil, LNil) -> LNil
    in zipHelper list1 list2 0
    ;;

Изменения:

После добавления элемента в список, который я буду возвращать, я должен вызвать функцию zipHelper с аргументами tailсписка, из которого я беру голову и второй список, а не только его хвост.

Просто пропустите присвоение имен спискам в совпадении, как это делал ранее комментатор.

0 голосов
/ 04 декабря 2018

Основываясь на ответе @Jorge Adriano, я быстро создал предложенную ими версию: 

let lnil = LNil
let lcons a l = LCons (a,l)

let rec zip = function
  | LCons (xA, xfA) as fA ->
    ( function
      | LCons(xB, xfB) ->
        lcons xA (fun () -> lcons xB (fun () -> zip (xfA ()) (xfB ())))
      | LNil -> fA
    )
  | LNil ->
    ( function
      | LCons (xB, xfB) as fB -> fB
      | LNil -> LNil
    )

Я также разделил ltake на преобразование дублей и списков (не реализовано с помощью рекурсивного алгоритма) и добавил повтор впроверить corecursive datastructures: 

let rec ltake n = function
    | LNil -> LNil
    | LCons(x, xf) ->
      if n == 0
      then LNil
      else lcons x (fun () -> ltake (n - 1) (xf ()))

let rec of_list = function
  | [] -> LNil
  | x :: xs -> LCons (x, fun () -> of_list xs)

let rec to_list = function
    | LNil -> []
    | LCons (x,xs) -> x :: (to_list (get xs))

let repeat n =
  let rec aux n () = LCons (n, aux n) in
  aux n ()

мы можем проверить его на исходном входе: 

utop # ltake 12 (zip a b) |> to_list ;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 11]

и с повторением: 

utop # ltake 12 (zip (repeat 1 ) (repeat 2)) |> to_list ;;
- : int list = [1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2]
0 голосов
/ 04 декабря 2018

Вы допустили ошибку в своем match утверждении. 

let zip list1 list2 =
    let rec zipHelper listA listB count = match (list1, list2) with

Вы не хотите совпадать с list1 и list2, но listA иlistB.

Вам также следует изучить эти вызовы, 

then LCons(xA, function() -> zipHelper (xfA()) (xfB()) (count + 1))
else LCons(xB, function() -> zipHelper (xfA()) (xfB()) (count + 1))

Вы действительно хотите передать в качестве аргумента оба хвоста?

...