haskell - monadas - ¿Cómo se puede modelar el no determinismo con una mónada de lista?

monada espiritual

Question

¿Alguien puede explicar (mejor con un ejemplo en inglés simple) lo que puede hacer una mónada lista para modelar cálculos no deterministas? Es decir, cuál es el problema y qué solución puede ofrecer una lista de una mónada.

Answer 1

Aquí hay un ejemplo basado en el lanzamiento de monedas. El problema es el siguiente:

Tienes dos monedas, rotundas y justas . La moneda con sesgo tiene dos cabezas, y la moneda de la Feria tiene una cabeza y una cola. Elige una de estas monedas al azar, tírala y observa el resultado. Si el resultado es una cabeza, ¿cuál es la probabilidad de que haya elegido la moneda con sesgo ?

Podemos modelar esto en Haskell de la siguiente manera. Primero, necesitas los tipos de moneda y sus caras.

data CoinType = Fair | Biased deriving (Show)
data Coin = Head | Tail deriving (Eq,Show)

Sabemos que lanzar una moneda justa puede aparecer en Head o Tail mientras que la moneda sesgada siempre aparece en Head . Modelamos esto con una lista de posibles alternativas (donde implícitamente, cada posibilidad es igualmente probable).

toss Fair = [Head, Tail]
toss Biased = [Head, Head]

También necesitamos una función que elija aleatoriamente la moneda justa o sesgada

pick = [Fair, Biased]

Luego lo juntamos todo así.

experiment = do
coin <- pick -- Pick a coin at random
result <- toss coin -- Toss it, to get a result
guard (result == Head) -- We only care about results that come up Heads
return coin -- Return which coin was used in this case

Observe que aunque el código se lee como si solo estuviéramos ejecutando el experimento una vez, pero la mónada de la lista está modelando el no determinismo, y en realidad seguimos todas las rutas posibles. Por lo tanto el resultado es

>> experiment
[Biased, Biased, Fair]

Debido a que todas las posibilidades son igualmente probables, podemos concluir que existe una probabilidad de 2/3 de que tengamos la moneda sesgada, y solo una probabilidad de 1/3 de que tengamos la moneda justa.

Answer 2

Cuando decimos que es no determinista, significa que tiene más de un valor.

El libro Learn You A Haskell explica muy bien esto:

Un valor como 5 es determinista. Solo tiene un resultado y sabemos exactamente cuál es. Por otro lado, un valor como [3,8,9] contiene varios resultados, por lo que podemos verlo como un valor que en realidad es muchos valores al mismo tiempo. El uso de listas como funtores aplicativos muestra muy bien este no determinismo:

ghci> (*) <$> [1,2,3] <*> [10,100,1000]
[10,100,1000,20,200,2000,30,300,3000]

Todas las combinaciones posibles de elementos multiplicadores de la lista izquierda con elementos de la lista derecha se incluyen en la lista resultante. Cuando tratamos con el no determinismo, hay muchas opciones que podemos hacer, así que solo probamos todas ellas, por lo que el resultado es un valor no determinista y solo tiene muchos más resultados.

Lista de modelos de mónadas no deterministas muy bien. Su instancia es así:

instance Monad [] where
return x = [x]
xs >>= f = concat (map f xs)
fail _ = []

Entonces, cuando alimenta un valor no determinista producirá otro conjunto de valor no determinista:

ghci> [3,4,5] >>= /x -> [x, x * 2]
[3,6,4,8,5,10]

Answer 3

Entonces, es importante definir claramente qué significa "no determinismo" aquí, ya que no es exactamente lo mismo que la forma en que podría percibirse en, por ejemplo, un algoritmo no determinista. El sentido que se captura aquí es que el cómputo se ramifica ; puede haber múltiples estados a los que el sistema puede moverse en cualquier punto en particular.

Las listas modelan esto porque, simplemente, contienen múltiples elementos. Lo que es más, las comprensiones monádicas nos dan una manera de componer resultados no deterministas, es decir, modelar la exploración de todas las ramas a la vez.

Answer 4

La lista de la mónada puede representar "todos los resultados posibles de un cálculo no determinístico". Por ejemplo, la función.

f x = [x, x + 1, x + 2]

puede interpretarse como un cálculo no determinista que toma x y devuelve uno de x , x+1 y x+2 .

La función

g x = [2 * x, 3 * x]

puede interpretarse como un cálculo no determinista que toma x y devuelve 2 * x o 3 * x . La "composición" de estos dos cálculos no deterministas debe ser otro cálculo no determinista que toma x , lo transforma en uno de x , x + 1 o x + 2 , y luego lo duplica o lo triplica. Así, en términos de listas, el resultado debería ser una lista de las seis posibilidades.

Ahora

g =<< f x = [2 * x, 3 * x, 2 * (x + 1), 3 * (x + 1), 2 * (x + 2), 3 * (x + 2)]

Así que, efectivamente, esto modela el no determinismo como esperábamos.

(Existe cierta incomodidad en el uso de listas para el no determinismo, ya que también tienen un ordenamiento de elementos. Una "mónada establecida" probablemente sería una forma más natural de modelar el no determinismo. Las listas ciertamente contienen suficiente información para modelar el no determinismo , pero el ordenamiento significa que tenemos más información de la necesaria.)

EDITAR: de hecho, lo que escribí solo realmente va tan lejos como para usar la instancia de aplicación de lista. Para obtener algo que aproveche al máximo la interfaz monádica, desea un cálculo que devuelva una serie de resultados que dependen de su entrada, por ejemplo

g 0 = [1000, 1001]
g x = [2 * x, 3 * x, 4 * x]

¡Aunque hay que admitir que este es un ejemplo completamente arbitrario y desmotivado!