Czy możliwość wykrycia cyklicznych list w Haskell złamie jakiekolwiek właściwości tego języka?

Question

W Haskell, niektóre listy są cykliczne:

ones = 1 : ones 

Inni nie są:

nums = [1..] 

A potem są rzeczy tak:

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

To oznacza taką samą wartość jak ones , a na pewno ta wartość jest powtarzającą się sekwencją. Ale to, czy jest reprezentowane w pamięci jako cykliczna struktura danych, jest wątpliwe. (Implementacja mógłby to zrobić, ale this answer explains that "it's unlikely that this will happen in practice".)

Załóżmy bierzemy realizację Haskell i włamać się do niego wbudowaną funkcję isCycle :: [a] -> Bool który analizuje strukturę reprezentacji w pamięci argumentu. Zwraca True, jeśli lista jest fizycznie cykliczna i False, jeśli argument ma skończoną długość. W przeciwnym razie nie zakończy się. (Wyobrażam sobie "włamywanie go", ponieważ nie jest możliwe napisanie tej funkcji w Haskell.)

Czy istnienie tej funkcji mogłoby złamać interesujące właściwości języka?

Answer 1

Czy istnienie tej funkcji może złamać interesujące właściwości języka?

Tak, będzie to. Przerwałoby to referential transparency (patrz także the Wikipedia article). Wyrażenie Haskella można zawsze zastąpić jego wartością. Innymi słowy, zależy to tylko od przekazanych argumentów i niczego innego. Gdybyśmy mieli zaproponowane propozycje, wyrażenia używające go nie spełniałyby już tej właściwości. Mogłyby one polegać na wewnętrznej reprezentacji wartości pamięci. W konsekwencji naruszone zostaną inne prawa. Na przykład identity law dla Functor

fmap id === id 

nie będzie posiadać więcej: Byłbyś w stanie odróżnić ones i fmap id ones, jak ten ostatni byłby acykliczny. Optymalizacje kompilatora, takie jak zastosowanie powyższej ustawy, nie zachowałyby dłużej właściwości programu.

jednak inna kwestia byłaby posiadające funkcję

isCycleIO :: [a] -> IO Bool 

jak IO akcje są dopuszczone do badania i nic zmieniać.

Czysty rozwiązaniem byłoby mieć typ danych, który wewnętrznie wyróżnia dwa:

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 

Oczywiście, że nie będzie w stanie rozpoznać, czy lista rodzajowy jest cykliczny, czy nie, ale dla wielu operacji możliwe byłoby zachowanie wiedzy o wartościach Cyclic.

Answer 2

W ogólnym przypadku nie można zidentyfikować listy cyklicznej. Jednak jeśli lista jest generowana przez operację rozwijania, możesz. Data.List zawiera to:

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

Pierwszy argument to funkcja, która trwa „stan” argument typu „B” i może powrócić element listy i nowy stan. Drugim argumentem jest stan początkowy. "Nic" oznacza, że ​​lista się kończy.

Jeśli stan kiedykolwiek się powtarza, lista będzie powtarzana od punktu ostatniego stanu. Jeśli więc zamiast tego używamy innej funkcji rozwijania, która zwraca listę par (a, b), możemy sprawdzić stan odpowiadający każdemu elementowi. Jeśli ten sam stan zostanie wyświetlony dwukrotnie, lista jest cykliczna. Oczywiście zakłada to, że stan jest przykładem równania lub czegoś.