In che modo "ripeti x = x: ripeti x" restituisci una lista in Haskell?

Probabilmente la tua confusione deriva dal fatto che sei abituato a una valutazione entusiasta, mentre Haskell usa la valutazione pigra.

Ad esempio, se si dovesse utilizzare la definizione

repeat' x = x : repeat' x

per valutare l'espressione repeat' 10 avidamente, allora otterresti

repeat' 10                ==>
10 : repeat' 10           ==>
10 : 10 : repeat' 10      ==>
10 : 10 : 10 : repeat' 10 ==>
...

e questo si fermerebbe per sempre.

Con la valutazione pigra è diverso. Se hai l'espressione repeat' 10 in un determinato contesto, questo non viene valutato finché non è richiesto il risultato di repeat' 10 .

Non appena prendi i valori dalla lista, i passaggi precedenti sono eseguiti, ma solo quanti di loro vengono eseguiti come richiesto.

Quindi, in Haskell applicare la tua funzione ad un certo valore non crea una struttura di dati infinita che è completamente caricata in memoria ad un certo punto nel tempo: questo è impossibile perché c'è solo una quantità limitata di memoria e un calcolo che termina può richiede solo una quantità limitata di tempo Crea piuttosto un programma dal quale puoi estrarre qualsiasi numero finito di elementi, ad esempio qualsiasi prefisso finito della lista infinita.

Si noti che il prefisso finito non è rappresentato come un elenco semplice

10 : 10 : 10 : []

ma come un termine come

10 : 10 : 10 : repeat' 10

Quindi, supponiamo di voler calcolare con un elenco finito, ad es. take 2 [1, 2, 3] :

take 2 (1 : 2 : 3 : []) ==>
1 : take 1 (2 : 3 : []) ==>
1 : 2 : take 0 (3 : []) ==>
1 : 2 : []

Ora, lo stesso ma con il tuo elenco infinito:

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 : []

Sembra che tu abbia due confusioni qui: in primo luogo, come Haskell ha mai completato una definizione ricorsiva come repeat x = x:repeat x , e in secondo luogo, come fa a sapere che questo, in effetti, definisce una lista.

Il primo risponde, come hanno fatto le altre risposte, dicendo "pigrizia". Scrivere repeat x = x:repeat x è in realtà una descrizione del valore repeat x , da consultare ogni volta che sono necessarie singole voci in quel valore.

Il secondo è chiamato "tipo inferenza" e va così. Haskell sa che l'operatore : ha il seguente tipo:

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

e quindi, in un'espressione x:y , y deve essere una lista i cui elementi hanno lo stesso tipo di x, e l'espressione stessa è anche questo tipo di lista. Quindi in x:repeat x , dobbiamo avere repeat x una lista di valori con lo stesso tipo di x, e quindi il risultato di questo è anche un elenco di questo tipo. Quindi funziona, almeno per i tipi, per dichiarare che questo elenco dovrebbe essere uguale a repeat x stesso.

Crea un infinito elenco.

Poiché Haskell è pigro, la successiva chiamata di repeat non viene eseguita finché non è necessaria per altri calcoli. Se hai solo bisogno del primo elemento di x:xs , x verrà calcolato ma xs non lo sarà.

In questo modo puoi ottenere tanto del tuo elenco infinito di cui hai bisogno, a partire dal primo elemento. Per esempio. take 5 $ repeat 'A' ti darà "AAAAA" senza calcolare il resto infinito di A s.

Espresso in pseudo-Java 8, questo è il modo in cui repeat funziona sotto le copertine (e in generale i tipi di dati Haskell):

/**
 * 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)));
}

Naturalmente, in Haskell la pigrizia e il thunk sono impliciti, quindi basta scrivere questo:

repeat :: a -> [a]
repeat x = x : repeat x