La capacità di rilevare elenchi ciclici in Haskell interromperà qualsiasi proprietà della lingua?

Question

In Haskell, alcune liste sono ciclici:

ones = 1 : ones 

Altri non sono:

nums = [1..] 

E poi ci sono cose come questa:

more_ones = f 1 where f x = x : f x 

Questo indica lo stesso valore di ones e certamente quel valore è una sequenza ripetitiva. Ma se è rappresentato in memoria come una struttura ciclica dei dati è dubbia. (Un'implementazione potrebbe farlo, ma this answer explains that "it's unlikely that this will happen in practice".)

Supponiamo prendiamo un'implementazione Haskell e incidere in esso una funzione isCycle :: [a] -> Bool incorporata che esamina la struttura della rappresentazione in memoria dell'argomento. Restituisce True se l'elenco è fisicamente ciclico e False se l'argomento è di lunghezza finita. Altrimenti, non riuscirà a terminare. (Immagino "hacking in" perché è impossibile scrivere quella funzione in Haskell.)

Sarebbe l'esistenza di questa funzione rompere le interessanti proprietà del linguaggio?

Answer 1

L'esistenza di questa funzione interromperà proprietà interessanti del linguaggio?

Sì sarebbe. Si romperebbe referential transparency (vedere anche the Wikipedia article). Un'espressione Haskell può sempre essere sostituita dal suo valore. In altre parole, dipende solo dagli argomenti passati e nient'altro. Se avessimo

isCycle :: [a] -> Bool 

come lei propone, espressioni utilizzando non sarebbe soddisfare questa proprietà più. Potrebbero dipendere dalla rappresentazione della memoria interna dei valori. Di conseguenza, altre leggi sarebbero violate. Ad esempio, il identity law per Functor

fmap id === id 

non avrebbe retto più: Sareste in grado di distinguere tra ones e fmap id ones, in quanto quest'ultimo sarebbe aciclico. E le ottimizzazioni del compilatore come l'applicazione della legge sopra non preserverebbero più le proprietà del programma.

Tuttavia un'altra domanda sarebbe avere funzione

isCycleIO :: [a] -> IO Bool 

come IO azioni sono autorizzati a esaminare e cambiare qualcosa.

Una soluzione pura potrebbe essere quella di avere un tipo di dati che distingue internamente i due:

import qualified Data.Foldable as F 

data SmartList a = Cyclic [a] | Acyclic [a] 

instance Functor SmartList where 
    fmap f (Cyclic xs) = Cyclic (map f xs) 
    fmap f (Acyclic xs) = Acyclic (map f xs) 

instance F.Foldable SmartList where 
    foldr f z (Acyclic xs) = F.foldr f z xs 
    foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r 

Naturalmente non sarebbe in grado di riconoscere se un elenco generico è ciclica o no, ma per molte operazioni sarebbe possibile conservare la conoscenza di avere valori Cyclic.

Answer 2

Nel caso generale, non è possibile identificare una lista ciclica. Tuttavia, se l'elenco viene generato da un'operazione di svolgimento, è possibile. Data.List contiene questo:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

Il primo argomento è una funzione che prende uno "stato" argomento di tipo "b" e può restituire un elemento della lista e un nuovo stato. Il secondo argomento è lo stato iniziale. "Niente" significa che la lista finisce.

Se lo stato si ripete, l'elenco si ripeterà dal punto dell'ultimo stato. Quindi, se invece usiamo una funzione di spiegatura diversa che restituisce una lista di coppie (a, b), possiamo esaminare lo stato corrispondente a ciascun elemento. Se lo stesso stato viene visto due volte, l'elenco è ciclico. Ovviamente questo presuppone che lo stato sia un'istanza di Eq o qualcosa del genere.