How to fix problem taking first element of lazy list?

Question

I want to make function that take lazy list of int and returns lazy list with increase number of elements, each element x have to be repeated x times. For example, I will be writing lazy lists like regular, for more readability, I give to function [1; 2; 3], it returns [1; 2; 2; 3; 3; 3].

I write some code, that have to do it:

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 function return n elements of lazy in regular list *)

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

This test return: - : int list = [4; 4; 4; 4; 3; 3; 3; 1; 1; 1; 4; 4; 4]

So main problem is that increase function works fine for first two elements of lazy list, but at 3 - infinity elements it save statement from 2 element, how many times repeat element

Jorge Adriano Jorge Adriano · Accepted Answer · 2018-12-03T10:38:05

Firstly, your code does not compile. I suppose that where you wrote,

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

you meant to write

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

This however will fail because you call lhd (xf()) when xf() may be LNil. In fact you would fail right in the beginning if the list is empty.

in increaseHelper(lhd llist, llist)

You could try fixing your code according to your original idea, but part of what makes it complicated is that when you reach 0, to reset the counter you need to look into the head of the tail (if it's not nil).

So here is another idea. Why increase rather than decrease the counter? Start with the counter at 0, and increase it until the counter matches the head. It may not seem much different, but it's easier since resetting the counter doesn't require you to look into the list.

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

And make your initial call starting at 0,

in increaseHelper(0, llist)

How to fix problem taking first element of lazy list?

1 Answers