Perché i tipi di dati induttivi proibiscono i tipi come `dati BAD A= C (BAD A -> A)` Dove si verifica la ricorsione di tipo davanti a ->?

Question

AGDA Manuale su tipi di dati induttivi e corrispondenza del modello afferma:

.

.

Per garantire la normalizzazione, le occorrenze induttive devono apparire in posizioni rigorosamente positive.Ad esempio, il seguente tipo di dati non è consentito:

data Bad : Set where
  bad : (Bad → Bad) → Bad

.

Poiché c'è un verificarsi negativo di cattivi nell'argomento al costruttore.

Perché questo requisito è necessario per i tipi di dati induttivi?

Answer 1

Il tipo di dati che hai dato è speciale in quanto è un'incrafting dei non adipendente calcolo lambda.

data Bad : Set where
  bad : (Bad → Bad) → Bad

unbad : Bad → (Bad → Bad)
unbad (bad f) = f

.

Vediamo come.Richiamare, il calcolo Lambda non aderente ha questi termini:

 e := x | \x. e | e e'

.

Possiamo definire una traduzione [[e]] da Lambda non aderente Calculus Termini a AGDA Condizioni di tipo Bad (anche se non in AGDA):

[[x]]     = x
[[\x. e]] = bad (\x -> [[e]])
[[e e']]  = unbad [[e]] [[e']]

.

Ora è possibile utilizzare il termine Lambda non adirizzante senza terminazione per produrre un termine non terminale di tipo Bad.Ad esempio, potremmo tradurre (\x. x x) (\x. x x) per l'espressione non terminata del tipo Bad di seguito:

unbad (bad (\x -> unbad x x)) (bad (\x -> unbad x x))

.

Sebbene il tipo sia stato un modulo particolarmente conveniente per questo argomento, può essere generalizzato con un po 'di lavoro a qualsiasi tipo di dati con occorrenze negative di ricorsione.

Answer 2

Un esempio Come questo tipo di dati ci consente di abitare qualsiasi tipo è indicato in Turner, D.A. (2004-07-28), Programmazione funzionale totale , setta. 3.1, pagina 758 in Regola 2: Type Recursion deve essere covariante . "

---

.

. Facciamo un esempio più elaborato usando Haskell. Inizieremo con un tipo di dati ricorsivo "cattivo"

data Bad a = C (Bad a -> a)

.

e costruisci il y combinator da esso senza alcuna altra forma di ricorsione. Ciò significa che avere un tale tipo di dati ci consente di costruire qualsiasi tipo di ricorsione o abitare qualsiasi tipo da una ricorsione infinita.

Il combinatore Y nel calcolo Lambda non adipendente è definito come

Y = λf.(λx.f (x x)) (λx.f (x x))

.

La chiave per questo è che applichiamo x a se stesso in x x. Nelle lingue digitate questo non è direttamente possibile, poiché non è possibile avere il tipo di generazione di tipo valido. Ma il nostro tipo di dati x consente di aggiungere / rimozione del modulo modulo:

selfApp :: Bad a -> a
selfApp (x@(C x')) = x' x

.

Prendendo Bad, possiamo scartare il suo costruttore e applicare la funzione all'interno del x :: Bad a stesso. Una volta che sappiamo come farlo, è facile costruire il combinatore Y:

yc :: (a -> a) -> a
yc f =  let fxx = C (\x -> f (selfApp x))  -- this is the λx.f (x x) part of Y
        in selfApp fxx

.

Nota che Né x né selfApp sono ricorsive, non vi è alcuna chiamata ricorsiva di una funzione a se stessa. Recursion appare solo nel nostro tipo di dati ricorsivo.

Possiamo verificare che il combinatore costruito faccia davvero cosa dovrebbe. Possiamo creare un ciclo infinito:

loop :: a
loop = yc id

.

o calcolo Let's Dice GCD :

gcd' :: Int -> Int -> Int
gcd' = yc gcd0
  where
    gcd0  :: (Int -> Int -> Int) -> (Int -> Int -> Int)
    gcd0 rec a b  | c == 0     = b
                  | otherwise  = rec b c
      where c = a `mod` b

.