[Haskell-beginners] About repeat function
daniel.is.fischer at googlemail.com
Fri Jun 24 11:08:40 CEST 2011
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.)
> Divyanshu Ranjan
More information about the Beginners