Listas de diferenças na programação funcional

A pergunta O que há de novo em estruturas de dados puramente funcionais desde Okasaki? , e a resposta épica do jbapple, mencionada usando listas de diferenças na programação funcional (em oposição à programação lógica), algo em que recentemente me interessei. Isso me levou a encontrar a lista de diferenças implementação da para Haskell. Tenho duas perguntas (perdoe / corrija-me se eu fizer duas perguntas diferentes no StackExchange).

A questão simples é: alguém está ciente da consideração acadêmica das listas de diferenças na programação funcional e / ou implementações além da que está na biblioteca Haskell? A resposta de jbapple não citou listas de diferenças (as listas de diferenças na programação lógica existem no folclore e em algumas fontes que eu tenho por aqui em algum lugar). Antes de encontrar a implementação de Haskell, eu não sabia que a idéia havia saltado da lógica para a programação funcional. É verdade que as listas de diferenças de Haskell são uma espécie de uso natural de funções de ordem superior e funcionam de maneira bem diferente das da programação lógica, mas a interface é certamente semelhante.

A coisa mais interessante (e muito confusa) que eu queria perguntar é se o alegado limite superior assintótico para a mencionada biblioteca de listas de diferenças de Haskell parece correto / plausível. Minha confusão pode ser porque estou perdendo algo óbvio sobre o raciocínio de complexidade com preguiça, mas os limites reivindicados só fazem sentido para mim se a substituição por uma grande estrutura de dados (ou formação de fechamento, pesquisa variável ou algo ) sempre leva tempo constante. Ou é o "problema" simplesmente que não há limite no tempo de execução para "cabeça" e "cauda" precisamente porque essas operações podem ter que atravessar uma pilha arbitrária de cálculos / substituições adiadas?

Ou é o "problema" simplesmente que não há limite no tempo de execução para "cabeça" e "cauda" precisamente porque essas operações podem ter que atravessar uma pilha arbitrária de cálculos / substituições adiadas?

Eu acho que isso é mais ou menos correto. As DLs realmente só têm operações de construção rápidas, portanto, o arado é$\Theta(m)$$m$

A seguinte versão defuncionalizada de algumas das operações essenciais requer preguiça de $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

Sim, os limites dependem da suposição de que a composição da função leva tempo constante. Basicamente, se você tiver uma lista de associação:

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

$O(n)$ transformar isso em uma lista de contras. Se você pensar na representação usual de fechamentos, poderá ver que essa é basicamente a mesma representação de ponteiro que a representação usual de tipos de dados. (Como alternativa, você pode visualizar esse tipo como uma lista de diferenças desfuncionalizada.)