6

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:...

  • 3
    By the way, repeat could be defined in an imperative language as def 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. – amon Dec 1 '15 at 18:31
  • 1
    Note that Haskell's equivalent of amon's construction is actually 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. – Reinstate Monica May 3 '17 at 15:08
21

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 : []
| improve this answer | |
  • 3
    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. – Giorgio Dec 1 '15 at 18:40
  • 1
    I have added, for each evaluation step, the equation being used. You just match and replace subexpressions until you are finished. – Giorgio Dec 1 '15 at 18:52
  • 1
    I would implement 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... – John Dvorak Dec 2 '15 at 2:51
  • 1
    @AndresF: If you type it in the ghci REPL you get: [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. – Giorgio Dec 2 '15 at 18:31
  • 1
    @AndresF.: "I'm sure you replied to me by mistake.": I have overlooked your other comments and answers about Haskell, so I did not need to give such a detailed explanation. Maybe we can meet in chat some time and discuss what a list actually is? I find the topic interesting. I would prefer to discuss it in chat so we can clean up the comments here. – Giorgio Dec 2 '15 at 20:15
7

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.

| improve this answer | |
  • Spot on, I didn't think of type inference! – Michael Dec 1 '15 at 22:35
  • @Michael It's worth remembering that Haskell always knows the type. That, more than its functional nature, is its distinguishing characteristic. – Ryan Reich Dec 1 '15 at 23:28
2

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.

| improve this answer | |
  • 2
    @Doval: In an eager language you can call a lazy list a stream. In Haskell there is no real difference. – Giorgio Dec 1 '15 at 18:21
  • 1
    @Giorgio What I'm trying to say is that finite lists and lazy/potentially-infinite lists/streams are two different things, and Haskell's terminology muddies the water needlessly by calling the latter by the name of the former. I'm really just splitting hairs here but sometimes this sort of thing does cause confusion. It's a bit misleading to say there's no real difference in Haskell because Haskell doesn't have a type for "definitely finite" lists. – Doval Dec 1 '15 at 18:29
  • 2
    @MasonWheeler It's not a stretch to think of an IO stream as a lazy list that produces bytes or strings through black magic. – Doval Dec 1 '15 at 18:45
  • 3
    @MasonWheeler An output stream is just the black magic that creates someone else's input stream I guess. – Doval Dec 1 '15 at 18:54
  • 2
    The word stream has had a well-defined meaning at least since the 1980s (SICP). Also, I do not think that the concept of a stream used for IO is very far from that. Only the way in which you access a stream of data varies. When you are calling getc() in C you are actually pulling the next byte from a potentially infinite list / stream. – Giorgio Dec 1 '15 at 19:01
0

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
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.