La programmazione funzionale può essere utilizzata per risolvere problemi che richiedono casualità?

2

Questa vecchia domanda ci dice che nella programmazione funzionale la "vera" casualità non può essere raggiunta in quanto le funzioni FP sono pure / idempotenti e restituiscono lo stesso valore indipendentemente dal numero di invocazioni senza effetti collaterali.

Ma se questo è vero, in che modo la FP è applicabile a problemi come selezionare casualmente un Captcha o qualche enigma per interrogare l'utente prima di entrare nel sistema?

Ho considerato di prendere il tempo di sistema come seme all'interno della funzione. Ma dipende dallo stato esterno.

Qualcuno potrebbe dimostrarlo con uno snippet di codice in Haskell / Clojure, ecc.?

    
posta Vicky 03.01.2018 - 07:37
fonte

3 risposte

5

La tua domanda non è chiara in quanto non specifichi se stai parlando di numeri casuali veri o di numeri pseudo-casuali, quindi risponderò a entrambi.

Numeri casuali veri

Hai ragione che i programmi funzionali non possono produrre numeri casuali veri. Ma nessuno dei due può programmi imperativi. I computer sono ancora macchine deterministiche, indipendentemente dal fatto che stiano eseguendo un programma C o un programma Haskell.

Numeri Pseudo-Casuali

I numeri Pseudo-Casuali sono generati da un generatore di numeri pseudo-casuali (alias PRNG). I PRNG sono solo algoritmi come qualsiasi altro algoritmo. Possono essere espressi in un linguaggio funzionale così come possono essere espressi in un linguaggio imperativo.

Quindi, non c'è davvero alcuna differenza tra i linguaggi funzionali e le lingue imperative quando si tratta di numeri casuali. Entrambi possono calcolare numeri pseudo-casuali e nessuno può calcolare numeri casuali veri (dato che non possono essere calcolati affatto).

in functional programming "true" randomness cannot be achieved since in FP functions are pure/idempotent and return the same value irrespective of number of invocations without any side effects.

Ancora una volta, la stessa cosa è vera per la programmazione imperativa. Se chiami srand con lo stesso numero seme, determinerai sempre la stessa sequenza numerica pseudo-casuale da rand , ogni volta.

L'unico modo per ottenere la casualità vera è tramite I / O. Ma i linguaggi funzionali possono modellare l'I / O bene, sia con un Monade I / O (o qualcosa di più specializzato come Random monad), tipi lineari, tipi di mondo, tipi di effetti, un sistema di effetti o come Scala , ML, Clojure e F♯ lo fanno, semplicemente permettendoli e confidando che il programmatore non commetta errori.

Quindi, in altre parole, non ha senso chiedere dei numeri casuali specificamente . Un PRNG è solo una funzione, quindi se ti stai chiedendo in che modo la programmazione funzionale può essere usata per trattare numeri pseudo-casuali, allora dovresti chiedere come la programmazione funzionale può essere usata per gestire le funzioni, perché non c'è niente di speciale su un PRNG, è solo una funzione. E True Randomness è solo I / O, quindi, di nuovo, non ha senso chiedergli specificatamente .

Se accetti di poter scrivere funzioni in FP, devi anche accettare che puoi scrivere PRNG in FP. E se accetti di poter leggere l'orologio, leggere l'input dell'utente, leggere un file, accedere a un database, accedere al web, ecc., Allora devi anche accettare di poter leggere i numeri casuali veri. (In effetti, su Unix, ad esempio, i driver di dispositivo sono generalmente esposti come file e un dispositivo a numeri casuali verrebbe tipicamente esposto come un file letto. E c'è un servizio Web che serve numeri casuali veri.)

    
risposta data 04.01.2018 - 00:12
fonte
3

L'intero punto di un generatore di numeri casuali è di restituire un valore che è non una funzione deterministica del suo input.

Una "funzione di numero casuale" è quindi una contraddizione in termini. Non è nemmeno alla pari con I / O, che può ancora essere modellato puramente come funzione come parte di un sistema deterministico.

Quello che facciamo in un linguaggio funzionale è semplicemente implementare una chiamata al metodo non-deterministico, non-deterministico - può sembrare una funzione, avere l'abito della sintassi funzionale e assemblare insieme come una funzione (e essere chiamato o valutato , ed i suoi risultati usati, in un ordine deterministico relativo ad altre funzioni), ma chiaramente non è in realtà una funzione (perché i suoi output non si riferiscono ai suoi input) - e l'intero programma che dipende da esso cessa di essere una funzione più (perché il programma non esegue deterministicamente in base ai suoi input).

    
risposta data 03.01.2018 - 08:21
fonte
0

Risposta breve

La casualità viene gestita come qualsiasi altro tipo di input.

Risposta lunga

Casuale è Input

Casuale è come leggere lo stato dell'orologio hardware. E questo è come leggere lo stato della fotocamera per scattare una foto del profilo sull'utente del computer, o come leggere il contenuto di un determinato file. Random è solo un tipo speciale di input.

Gestione casuale a differenza di altri input

In teoria esiste la necessità di gestire diversamente la casualità da altri tipi di input. Ad esempio: per sicurezza. E la teoria della programmazione puramente funzionale può rispondere a tale esigenza. Ma in pratica questa direzione non viene perseguita. Ancora più importanti esigenze di sicurezza non sono ancora affrontate nella pratica semplicemente a causa del deficit nella capacità di ingegneria del software.

In che modo l'input viene gestito dalla programmazione puramente funzionale?

Questo argomento è discusso in molto materiale sul web. Se deve essere discusso qui su StackExchange, merita la sua stessa domanda.

Un po 'di aiuto concreto alla tua domanda comunque

Una funzione pura non restituisce il risultato finale, concreto, che dipende da azioni casuali, ma [possibilmente composte], come un piccolo algoritmo, che dice: ottieni un valore casuale; calcola qualche altra azione con essa ed esegui quell'altra azione. Una funzione pura restituisce solo un valore deterministico che rappresenta, descrive cosa deve fare il programma. Invia i problemi "sporchi" di non determinismo, IO al sistema runtime. Una funzione pura non fa nulla, si limita a calcolare [e restituisce] cosa fare.

    
risposta data 04.01.2018 - 10:31
fonte

Leggi altre domande sui tag