Как решить проблему с первым элементом ленивого списка? - PullRequest
Новая
       8

Как решить проблему с первым элементом ленивого списка?

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

Я хочу сделать функцию, которая принимает список отложенных операций int и возвращает отложенный список с увеличением числа элементов, каждый элемент x должен повторяться x раз.Например, я буду писать ленивые списки, как обычные, для большей читабельности я даю функцию [1;2;3], возвращает [1;2;2;3;3;3].

Я пишу код, который должен это сделать: 

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

let lhd = function
    | LNil -> failwith "lhd"
    | LCons (x, _) -> x
    ;;

let ltl = function
    | LNil -> failwith "ltl"
    | LCons (_, xf) -> xf()
    ;;

let increase llist = 
    let rec increaseHelper (count, lList) = match (count, lList) with
        | (0, LCons(_, xf)) -> increaseHelper((lhd (ltl llist)), (xf()))
        | (_, LCons(x, _)) -> LCons(x, function() -> increaseHelper(count - 1, lList))
        | (_, LNil) -> LNil
    in increaseHelper(lhd llist, llist)
    ;;

(* функция ltake возвращает n элементов lazy в обычном списке *) 

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

ltake (20,increase (LCons(4, function() -> LCons(3, function() -> LCons(1, function() -> LCons(4, function() -> LNil))))));;

Этот тест возвращает: -: int list = [4;4;4;4;3;3;3;1;1;1;4;4;4]

Итак, основная проблема в том, что функция увеличения отлично работает для первых двух элементов ленивого списка, но на 3-х элементах бесконечности сохраняет оператор из 2-х элементов, сколько раз повторяет элемент

1 Ответ

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

Во-первых, ваш код не компилируется.Я предполагаю, что там, где вы написали, 

| (0, LCons(_, xf)) -> increaseHelper((lhd xf), (xf()))

вы хотели написать 

| (0, LCons(_, xf)) -> increaseHelper((lhd (xf())), xf())

Это, однако, не удастся, потому что вы звоните lhd (xf()) когда xf() может быть LNil.На самом деле вы потерпите неудачу в самом начале, если список пуст.

in increaseHelper(lhd llist, llist)

Вы можете попробовать исправить свой код в соответствии с вашей первоначальной идеей, но отчасти усложняется то, что, когда вы достигнете 0, для сброса счетчика вам нужно посмотреть наголова хвоста (если это не ноль).

Так вот еще одна идея.Зачем увеличивать, а не уменьшать счетчик?Начните со счетчика в 0 и увеличивайте его, пока счетчик не совпадет с головой.Может показаться, что он немного другой, но это проще, поскольку для сброса счетчика не требуется просматривать список.

let rec increaseHelper(n,llist) = match llist with        
    | LNil -> LNil
    | LCons(x,xf) -> if n == x
                     then increaseHelper(0, xf())
                     else LCons(x, function() -> increaseHelper(n+1, llist))

И сделайте ваш начальный звонок, начиная с 0, 

in increaseHelper(0, llist)
...