Listy różnic w programowaniu funkcjonalnym

Pytanie Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki? oraz epicka odpowiedź jbapple, wspomniana przy użyciu list różnic w programowaniu funkcjonalnym (w przeciwieństwie do programowania logicznego), co mnie ostatnio interesowało. To doprowadziło mnie do znalezienia implementacji listy różnic dla Haskell. Mam dwa pytania (wybacz mi / popraw, jeśli powiem im dwa różne pytania na StackExchange).

Proste pytanie brzmi: czy ktoś wie o akademickim rozważaniu list różnic w programowaniu funkcjonalnym i / lub implementacjach oprócz tej z biblioteki Haskell? Odpowiedź jbapple nie zawierała cytatu dla list różnic (listy różnic w programowaniu logicznym istnieją w tradycji i w kilku źródłach, które posiadam Around Here Somewhere (TM)). Przed znalezieniem implementacji Haskell nie wiedziałem, że pomysł przeszedł z logiki do programowania funkcjonalnego. To prawda, że ​​listy różnic Haskell są naturalnym zastosowaniem funkcji wyższego rzędu i działają zupełnie inaczej niż te w programowaniu logicznym, ale interfejs jest z pewnością podobny.

Bardziej interesująca (i o wiele bardziej niepewna) kwestia, o którą chciałem zapytać, to czy twierdzona asymptotyczna górna granica dla wspomnianej biblioteki list różnic Haskell wydaje się poprawna / wiarygodna. Moje zamieszanie może wynikać z tego, że brakuje mi czegoś oczywistego na temat rozumowania złożoności z lenistwem, ale zastrzegane granice mają dla mnie sens tylko wtedy, gdy podstawienie nad dużą strukturą danych (lub formowaniem zamknięcia, zmiennym wyszukiwaniem lub czymś innym ) zawsze zajmuje stały czas. Czy też „haczyk” polega po prostu na tym, że czas wykonania „głowy” i „ogona” nie jest ograniczony, właśnie dlatego, że operacje te mogą wymagać przejścia przez dowolny stos odroczonych obliczeń / zamian?

Czy też „haczyk” po prostu polega na tym, że czas wykonania „głowy” i „ogona” nie jest ograniczony, właśnie dlatego, że operacje te mogą wymagać przejścia przez dowolny stos odroczonych obliczeń / zamian?

$\Theta(m)$$m$

$O(1)$ fromList

{-# LANGUAGE NoMonomorphismRestriction #-}

data DL a = Id
          | Cons a
          | Compose (DL a) (DL a)

fromList [] = Id
fromList (x:xs) = Compose (Cons x) (fromList xs)

toList x = help x []
    where help Id r = r
          help (Cons a) r = a:r
          help (Compose f g) r = help f $ help g r

empty = Id

singleton = Cons

cons x = append (singleton x)

append = Compose

snoc xs x = append xs (singleton x)

$\Theta(n)$headtail[a] -> [a]toList

Tak, granice zależą od założenia, że ​​kompozycja funkcji wymaga stałego czasu. Zasadniczo, jeśli masz listę dołączeń:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

$O(n)$