[Haskell-beginners] About repeat function

[Daniel Fischer]

On Friday 24 June 2011, 10:31:26, divyanshu ranjan wrote:
> As i was going through Learn You a Haskell for Great Good , i came
> across following repeat function implementation :
>    repeat' ::  x - > [x]
>    repeat' x = x : repeat' x
> My question is why it produces list in first place. 1:2:3 is not a list
> but 1:2:3:[] is. How comes haskell know that the things which we are
> adding will eventually added to the beginning of  empty list given
> things are infinite

Well, since things are infinite here, nothing will ever be consed to an 
empty list. In this case, everything is consed to a nonempty list.
In general, a list needs not end with [], it could also end with _|_ 
(bottom, undefined), 1:2:3:_|_ is a valid list, it will lead to an 
error/nontermination if you ever ask what comes after the 3, but if you 
never do that, it will work (e.g. (1:2:3:_|_) !! 2 ~> 3).

The construction of repeat' goes

repeat' x = x : something

(where something = repeat' x, but all we need of that for the moment is 
that is has the correct type), so by

(:) :: a -> [a] -> [a],

repeat' x produces a list (if the something is a list, but something is 
repeat' x, which is a list, provided that something is a list, which ...
So the type checker can't prove that it is a list in a finite number of 
deduction steps; however, it can prove that it can't be anything other than 
a list, and the assumption that it is a list is consistent, so it is 
accepted.), the first element of which is x.

As long as you don't check whether the resulting list contains more than 
one element, nothing further is done. If you ask for further elements, the 
definition is entered again, each time delivering a further list element.

You might look at it as a limit process,
step 0: unknown
step 1: x:unknown
step 2: x:x:unknown
step 3: x:x:x:unknown
...

An equivalent (but possibly more efficient) definition is

repeat'' x = let result = x : result in result

> so you can specify the end which is [] .

It is not for infinite lists, you could say that infinite lists end in _|_ 
or that they have no end, whichever you prefer (but if you say they end in 
_|_, be aware that you can never reach that end).

> Then why doing 1:3:4 is not acceptable ?

Because it's finite, so it has a reachable end.
The end is 4, which (in general) is not a list, but a number.
(If you have e.g. an instance Num [Int] where ... in scope, the 4 at the 
end is a valid list, whatever fromInteger does for that instance.)

> 
> Thanks
> Divyanshu Ranjan