Perché il functor delle liste rappresenta un contesto di scelta non deterministica?

Question

Cosa significa questa citazione?

the list functor represents a context of nondeterministic choice; 

Nel contesto di Functional in programmazione funzionale.

Penso di capire che un Functor è un "contenitore" di qualche tipo insieme alla possibilità di applicare una funzione uniforme agli elementi nel contenitore senza alterare la struttura. Quindi forse è un Functor che rappresenta un contesto o un contenitore con possibili errori, ma perché l'elenco rappresenta un contesto o un contenitore con una scelta non deterministica?

Answer 1

Come meglio posso dire, un calcolo è "non deterministico" se ha più risposte possibili. Bene, una lista può contenere più risposte possibili. Ecco perché

(Quanto al perché si chiama non deterministico, non ho idea ... Mi sarei aspettato non deterministico per significare casuale, che è qualcosa di molto diverso.)

Answer 2

calcoli "classici" prendere 1 ingresso e dare 1 uscita. Quello che vuoi rappresentare con questi calcoli non deterministici è: cosa posso dire sull'output se non sono sicuro dell'input?

Due usuali modi per rappresentare l'incertezza è da considerare:

1. che l'ingresso è un elemento di un dato insieme
2. che l'ingresso è data da una distribuzione di probabilità nota

Ad esempio, considera la funzione (2 *) che raddoppia l'input. Cosa puoi dire dell'output di quella funzione quando l'input è il risultato di un lancio di dado?

1. so il dado ha 6 facce modo che il risultato sia nell'insieme {} 2.4.6.8.10.12
2. so le probabilità di ciascuna faccia è 1/6 quindi so che ognuno di questi numeri ha probabilità 1/6 di apparire

Il functor di lista rappresenta calcoli non deterministici nel senso di 1 .: rappresenta insiemi di liste.

Answer 3

Si consideri il seguente:

foo = do 
    x <- [1 .. 10] 
    y <- [2, 3, 5, 7] 
    return (x * y) 

Che cosa è foo? Ebbene, è x * y, eccetto con le scelte non deterministiche di x è un numero da 1 a 10, e y essendo o 2, 3, 5, o 7. Pertanto, foo è [2, 3, 5, 7, 4, 6, 10, 14, etc... ]

Answer 4

Tradizionalmente, in computabilità e complessità, un modello di calcolo non deterministico ha fatto riferimento a un modello, nel qual caso è possibile "ramificarsi". Wikipedia spiega in questo modo:

Nella teoria della complessità computazionale, algoritmi non deterministici sono quelle che, ad ogni passo possibile, possono permettere per più continuazioni (immaginate un uomo che cammina lungo un sentiero in un bosco e, ogni volta che passi inoltre, deve scegliere la biforcazione sulla strada che desidera prendere).Questi algoritmi non arrivano a una soluzione per ogni possibile percorso computazionale; tuttavia, è garantito che arrivino ad una soluzione corretta per un percorso (ad esempio, l'uomo che cammina attraverso la foresta può trovare la sua cabina solo se sceglie una combinazione di percorsi "corretti"). Le scelte possono essere interpretate come ipotesi in un processo di ricerca.

Nella lista monade, questo è esattamente quello che stai facendo. Ad esempio, si consideri questa soluzione per la versione decisione del clique problem, nell'elenco Monade:

cliques :: Int -> Graph -> [[Node]] 
cliques 0 _ = [[]] 
cliques minCliqueSize graph = do 
    v <- nodes graph 
    vs <- cliques (minCliqueSize - 1) (deleteNode v graph) 
    mapM_ (\ w -> guard (isAdjacent v w graph)) vs 
    return (v:vs) 

Questo è esattamente come ci si programmano per esempio una macchina di Turing non deterministica per risolvere il problema della cricca.

Answer 5

Oltre a visualizzare un funtore come un contenitore, è anche possibile visualizzarlo come un certo tipo di contesto. I tuoi valori sono in questo contesto e se vuoi operare su di essi, devi utilizzare map per sollevare una funzione nel contesto. Un altro modo per dirla è che i tuoi valori sono aumentati con quel contesto.

Per capire in che modo il functor di elenco è un contesto di scelta non deterministica, può essere utile vedere come un altro functor è un contesto: Il functor di Maybe è un contesto di un calcolo che potrebbe non riuscire. Se si tenta di applicare una funzione a un valore in un functor Maybe, il valore risultante manterrà lo stesso contesto in cui si è verificato o meno un calcolo non riuscito.

Allo stesso modo, una lista può essere vista come il risultato di una computazione che non ha un risultato deterministico, ma il cui risultato potrebbe invece essere scelto non deterministicamente da uno di più valori. Se si è tentato di mappare una funzione su una lista con 3 elementi, tali elementi sarebbero stati modificati, ma il contesto in cui si poteva scegliere tra tre valori rimaneva lo stesso.

Prendendo in prestito un po 'di Dan Burton risposta, guarda la notazione monadica per gli elenchi:

foo = do 
    x <- [1 .. 10] 
    y <- [2, 3, 5, 7] 
    return (x * y) 

sembra a prima un po' strano, dal momento che la notazione sembra indicare, che si potrebbe estrarre un singolo valore da ognuna delle liste, ma poi ottieni come risultato una lista lunga 40 elementi. Ha più senso quando si guardano i funtori (beh, le monadi in questo caso) come un contesto per un singolo valore. Nell'esempio, x e sono tali valori, ma il loro contesto è che non sono deterministici. Quando si moltiplicano due di questi valori, si ottiene un ancor più nondeterminismo, risultante in una lista più lunga. Quindi con monade e >>=, il contesto può essere modificato, mentre con i funtori e map, non può.