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?

— Rob Simmons
źródło

Na początku byłem zdezorientowany „funkcjonalnymi językami programowania (w przeciwieństwie do funkcjonalnych języków programowania)”, ale czy chciałeś napisać „(w przeciwieństwie do logicznych języków programowania)”?

— Tsuyoshi Ito

Ojej - tak, o to mi chodziło, teraz jest naprawione.

— Rob Simmons

Drugie pytanie wydaje mi się bardziej odpowiednie w przypadku Przepełnienia stosu, ale teraz, kiedy już je zadałeś, może lepiej poczekać, czy ktoś może tutaj odpowiedzieć. Osobiście nie mogę znaleźć żadnego powodu, by wątpić w twierdzone granice czytania kodu źródłowego, ale nie podążyłem za twoim rozumowaniem, aby w to wątpić, a także mogę coś przeoczyć.

— Tsuyoshi Ito

Odpowiedzi:

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

— jbapple
źródło

To, co dostajesz od lenistwa, polega na tym, że dwukrotne żądanie ogona listy nie wykona drogiej operacji dwa razy, co jest miłe.

— Rob Simmons

@ Rob, nie rozumiem, co masz na myśli.

— jbapple

Myślę, że punkt, który starałem się (źle) zilustrować za pomocą tego przykładu: mam wyjątkowo długą listę różnic „xs”, którą podniosłem, powtarzając „snoc” rzeczy na oryginalnej liście. Przy pierwszym wywołaniu „head xs” spodziewam się, że O (n) zajmie wykonanie odroczonego obliczenia; jednak ponieważ obliczenia te powinny zostać zapamiętane, drugie wywołanie „head xs” (dla tych samych „xs”) powinno zająć czas O (1).

— Rob Simmons

Cóż, zgadzam się z tym, ale lenistwo, o którym wspomniałem w mojej odpowiedzi, dotyczyło fromList, który nie jest używany w snoc lub head. Więc, choć pedantyczne, byłem zdezorientowany „co” w twoim oświadczeniu „co dostajesz z lenistwa”. Powiedziałbym, że twój przykład i moje to dwie rzeczy, które odczuwasz z lenistwa.

— jbapple

Ok - i to wyjaśnienie pomaga mi również lepiej zrozumieć twój poprzedni punkt.

— Rob Simmons

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)$

— Neel Krishnaswami
źródło