Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
This is supposed to return an infinite list of x's. However a list is created using an element, then the operator ':' and then a list.
The recursive definition of repeat' x = x:repeat' x seems to never get to the point where an actual list is created as it seams to continuously add singular elements (where?), doing something like x:x:x:x:...
Probably your confusion comes from the fact that you are used to eager evaluation, whereas Haskell uses lazy evaluation.
For example, if you were to use the definition
repeat' x = x : repeat' x
to evaluate the expression repeat' 10 eagerly, then you would get
repeat' 10 ==>
10 : repeat' 10 ==>
10 : 10 : repeat' 10 ==>
10 : 10 : 10 : repeat' 10 ==>
...
and this would loop forever.
With lazy evaluation it is different. If you have the expression repeat' 10 in a certain context, this is not evaluated until the result of repeat' 10 is required.
As soon as you take values from the list, the above steps are executed, but only as many of them get executed as requested.
So, in Haskell applying your function to some value does not create an infinite data structure that is completely loaded in memory at some point in time: this is impossible because there is only a finite amount of memory and a computation that terminates can only take a finite amount of time. It rather creates a program from which you can pull any finite number of elements, i.e. any finite prefix of the infinite list.
Note that the finite prefix is not represented as a plain list
10 : 10 : 10 : []
but as a term like
10 : 10 : 10 : repeat' 10
So, suppose you want to compute with a finite list, e.g. take 2 [1, 2, 3]:
take 2 (1 : 2 : 3 : []) ==>
1 : take 1 (2 : 3 : []) ==>
1 : 2 : take 0 (3 : []) ==>
1 : 2 : []
Now, the same but with your infinite list:
take 2 (repeat' 10) ==> -- repeat' x = x : repeat' x
take 2 (10 : repeat' 10) ==> -- take n (x : xs) = x : take (n - 1) xs
10 : take 1 (repeat' 10) ==> -- repeat' x = x : repeat' x
10 : take 1 (10 : repeat' 10) ==> -- take n (x : xs) = x : take (n - 1) xs
10 : 10 : take 0 (repeat' 10) ==> -- take 0 _ = []
10 : 10 : []
repeat' will never give you that [], take will. Because take 0 _ = []. I.e. if you call take with the first argument 0, it does not look at the second argument (which contains the nasty infinite stuff) and returns []. And everything is nice again.
repeat' as repeat' x = rx where rx = x : rx. This turns an infinite data structure into a finite one. Any chance GHC does the same for you? I think it can...
Dec 2, 2015 at 2:51
[1,2,3*** Exception: Prelude.undefined. But if you type: take 3 (1 : 2 : 3 : undefined), lo and behold, you get [1,2,3]! Why? Because the term is evaluated lazily: once take has gotten 3 elements out of the term, it does not proceed to evaluate the undefined and so no exception is thrown.
You seem to have two confusions here: first, how does Haskell ever complete a recursive definition such as repeat x = x:repeat x, and second, how does it know that this does, in fact, define a list.
The first is answered, as the other responses have done, by saying "laziness". Writing repeat x = x:repeat x is actually a description of the value repeat x, to be consulted whenever individual entries in that value are needed.
The second is called "type inference" and goes like this. Haskell knows that the operator : has the following type:
(:) :: a -> [a] -> [a]
and therefore, in an expression x:y, y must be a list whose elements have the same type as x, and the expression itself is this kind of list as well. So in x:repeat x, we must have repeat x be a list of values with the same type as x, and then the result of this is also such a list. So it works out, at least for types, to declare that this list should equal repeat x itself.
It creates an infinite list.
Since Haskell is lazy, the next invocation of repeat is not executed until it is needed for other computation. If you only need the first element of x:xs, x will be computed but xs will not be.
This way you can get as much of your infinite list as you need, beginning from the first element. E.g. take 5 $ repeat 'A' will give you "AAAAA" without computing the infinite rest of As.
getc() in C you are actually pulling the next byte from a potentially infinite list / stream.
Expressed in pseudo-Java 8, this is how repeat works under the covers (and Haskell data types in general):
/**
* A "thunk" is a structure that wraps around a Supplier,
* computes its result when first requested, caches it and
* then uses that cached value afterwards.
*
* The Haskell runtime generally passes thunks around between
* object code routines and only computes the thunks's values when
* they're really needed. Exception: the compiler may optimize thunks
* away in cases where it's safe to do so.
*/
abstract class Thunk<A> implements Supplier<A> {
private Supplier<A> supplier;
private A value = null;
synchronized A get() {
if (value == null) {
value = supplier.get();
}
return value;
}
}
/**
* A single-linked list node, but the head and tail are
* stored as thunks, not as values directly.
*/
class Node<A> {
final Thunk<A> head;
final Thunk<Optional<Node<A>>> tail;
Node(Thunk<A> head, Thunk<Optional<Node<A>>> tail) {
this.head = head;
this.tail = tail;
}
}
/**
* The repeat function takes a thunk that produces an element value,
* and gives you back a thunk that, as you chase it down, will gradually
* produce an infinite list.
*
* The runtime structure for a Haskell-style list, in effect, is like
* the return type of this function: a `Thunk<Optional<Node<A>>>`.
*/
static <A> Thunk<Optional<Node<A>>> repeat(Thunk<A> elem) {
return new Thunk<>(() -> Optional.of(new Node<A>(elem, repeat elem)));
}
Of course, in Haskell laziness and thunks are implicit, so you just write this:
repeat :: a -> [a]
repeat x = x : repeat x
repeatcould be defined in an imperative language asdef repeat(x) = { let xs = new LinkedListNode(x); xs.next = xs; xs }, which models the recursion in the data rather than the control flow. Where does that linked list end? Nowhere, never, there is no end node.repeat' x = let xs = x : xs in xs. The subtle difference is that this implementation creates one self-referential node because the recursion is in the data, whereas the code in the question actually creates a (lazy) infinite list because the recursion is in the function call.