Riesci a riconoscere una lista infinita in un programma Haskell?

Question

Eventuali duplicati:
How to tell if a list is infinite?

In Haskell, è possibile definire una lista infinita, per esempio [1..]. Esiste una funzione incorporata in Haskell per riconoscere se una lista ha una lunghezza finita? Non immagino che sia possibile scrivere una funzione fornita dall'utente per farlo, ma la rappresentazione interna degli elenchi di Haskell potrebbe essere in grado di supportarla. Se non in Haskell standard, esiste un'estensione che fornisce tale funzionalità?

Answer 1

No, questo non è possibile. Sarebbe impossibile scrivere una funzione del genere, perché si possono avere liste la cui finitezza potrebbe essere sconosciuta: si consideri un ciclo ricorsivo che genera un elenco di tutti gli twin primes che può trovare. Oppure, per dare un seguito a ciò che Daniel Pratt ha menzionato nei commenti, si può avere un elenco di tutti i passaggi che uno universal Turing machine prende durante l'esecuzione, terminando l'elenco quando la macchina si ferma. Quindi, puoi semplicemente controllare se un elenco di questo tipo è infinito e risolvere lo Halting problem!

L'unica domanda un'implementazione potrebbe essere risposta è se un elenco è ciclico: se uno dei suoi puntatori di coda punta indietro a una cella precedente della lista. Tuttavia, questo è specifico dell'implementazione (Haskell non specifica nulla su come le implementazioni devono rappresentare i valori), impuro (diversi modi di scrivere la stessa lista darebbe risposte diverse), e anche dipendente da cose come se la lista che si passa a tale funzione è stata ancora valutata. Anche allora, non sarebbe ancora in grado di distinguere le liste finite da liste infinite nel caso generale!

(Dico questo perché, in molte lingue (come membri della famiglia Lisp), liste ciclici sono il unico tipo di liste infinite, non c'è modo per esprimere qualcosa di simile a "un elenco di tutti i numeri interi". così, in tali lingue, si può verificare se una lista è finita o meno.)

Answer 2

non c'è alcun modo per testare per la finitezza delle liste diverse da iterare su l'elenco per cercare la finale [] in qualsiasi implementazione di cui sono a conoscenza. E in generale, è impossibile dire se una lista è finita o infinita senza effettivamente andare a cercare la fine (che ovviamente significa che ogni volta che si ottiene una risposta, che dice finito).

Answer 3

si potrebbe scrivere un tipo di wrapper lista che tiene traccia delle infinitezza, e ci si limita alle operazioni di "decidibili" solo (in qualche modo simili a NonEmpty, che evita liste vuote):

import Control.Applicative 

data List a = List (Maybe Int) [a] 

infiniteList (List Nothing _) = true 
infiniteList _ = false 

emptyList = List (Just 0) [] 
singletonList x = List (Just 1) [x] 
cycleList xs = List Nothing (cycle xs) 
numbersFromList n = List Nothing [n..] 
appendList (List sx xs) (List sy ys) = List ((+) <$> sx <*> sy) (xs ++ ys) 
tailList (List s xs) = List (fmap pred s) (tail xs) 
... 

Answer 4

Come ehird ha scritto, la tua unica speranza è scoprire se una lista è ciclica. Un modo per farlo è usare un'estensione di Haskell chiamata "condivisione osservabile". Si veda ad esempio: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053

Answer 5

Quando si parla di "rappresentazione interna delle liste", dal punto di vista dell'implementazione di Haskell, non ci sono liste infinite. La "lista" che chiedi è in realtà una descrizione del processo computazionale, non un oggetto dati. Nessun oggetto dati è infinito all'interno di un computer. Una cosa del genere semplicemente non esiste.

Come altri hanno già detto, i dati interni dell'elenco potrebbero essere ciclici e l'implementazione di solito sarebbe in grado di rilevare questo, avendo un concetto di uguaglianza dei puntatori. Ma Haskell non ha questo concetto.

Ecco una funzione Common Lisp per rilevare la ciclicità di un elenco. cdr anticipi lungo una lista di una tacca e cddr - di due. eq è un predicato di uguaglianza puntatore.

(defun is-cyclical (p) 
    (labels ((go (p q) 
      (if (not (null q)) 
       (if (eq p q) t 
       (go (cdr p) (cddr q)))))) 
    (go p (cdr p))))