Как можно моделировать недетерминизм с помощью монады List?

Ответ 1

Вот пример, основанный на бросании монет. Проблема заключается в следующем:

У вас есть две монеты с надписью "Предвзятые и справедливые". Предвзятая монета имеет две головы, а на Справедливой монете одна голова и один хвост. Выбирайте одну из этих монет случайно, бросайте ее и наблюдайте за результатом. Если результатом является голова, какова вероятность того, что вы выбрали монету с предубеждением?

Мы можем моделировать это в Haskell следующим образом. Во-первых, вам нужны типы монет и их лица

data CoinType = Fair | Biased deriving (Show)

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

Мы знаем, что подбрасывание справедливой монеты может появиться либо Head, либо Tail, тогда как смещенная монета всегда появляется Head. Мы моделируем это со списком возможных альтернатив (где неявно каждая возможность одинаково вероятна).

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

Нам также нужна функция, которая выбирает случайную или предвзятую монету случайно

pick = [Fair, Biased]

Затем мы все вместе ставим

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

Обратите внимание, что хотя код читается, как только мы запускаем эксперимент один раз, но монада-список - это моделирование недетерминированности и фактическое отслеживание всех возможных путей. Поэтому результат

>> experiment
[Biased, Biased, Fair]

Поскольку все возможности одинаково вероятны, мы можем заключить, что есть шанс 2/3, что у нас есть предвзятая монета, и только 1/3 шанс, что у нас есть честная монета.

Ответ 2

Когда мы говорим, что это недетерминизм, это означает, что он имеет более одного значения.

Книга Learn You A Haskell хорошо объясняет это:

Значение как 5 является детерминированным. У него только один результат, и мы точно знаем, что это такое. С другой стороны, значение типа [3,8,9] содержит несколько результатов, поэтому мы можем рассматривать его как одно значение, которое на самом деле является множеством значений одновременно. Использование списков в качестве аппликативных функторов прекрасно демонстрирует этот недетерминизм:

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

Все возможные комбинации умножения элементов из левого списка с элементами из правого списка включены в итоговый список. Когда мы имеем дело с недетерминизмом, есть много вариантов, которые мы можем сделать, поэтому мы просто пробуем все из них, и поэтому результат также является недетерминированным значением, только у него гораздо больше результатов.

Список моделей монад недетерминированности красиво. Его пример таков:

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

Таким образом, когда вы вводите недетерминированное значение, оно создает другой набор недетерминированных значений:

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

Ответ 3

Монада списка может быть, хотя и представлять "все возможные результаты от недетерминированного вычисления". Например, функция

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

можно интерпретировать как недетерминированное вычисление, которое принимает x и возвращает один из x, x+1 и x+2.

Функция

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

можно интерпретировать как недетерминированное вычисление, которое принимает x и возвращает либо 2 * x, либо 3 * x. "Композиция" этих двух недетерминированных вычислений должна быть еще одним недетерминированным вычислением, которое принимает x, превращает его в один из x, x + 1 или x + 2, а затем либо удваивает, либо утроит его, Таким образом, в терминах списков результат должен быть списком всех шести возможностей

Теперь

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

так действительно, это моделирует недетерминированность, как мы и ожидали.

(Существует некоторая неловкость в использовании списков для недетерминированности, поскольку они также имеют упорядочение элементов. "Установленная монада", вероятно, была бы более естественным способом моделирования недетерминированности. Списки, безусловно, содержат достаточную информацию для моделирования не детерминированность, но порядок означает, что у нас есть больше информации, чем необходимо.)

EDIT: на самом деле то, что я написал, действительно имеет значение только при использовании аппликативного экземпляра списка. Чтобы получить то, что полностью использует монадический интерфейс, вам нужно вычислить, который возвращает ряд результатов, которые зависят от его ввода, например

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

хотя, по общему признанию, это совершенно произвольный и немотивированный пример!

Ответ 4

Итак, важно четко определить, что здесь означает "недетерминизм", поскольку он не совсем такой, как его можно воспринимать, скажем, в недетерминированном алгоритме. Чувство, захваченное здесь, состоит в том, что ветки вычислений - могут быть несколько состояний, которые система может перемещать в любую конкретную точку.

Показывает модель, потому что просто они содержат несколько элементов. Более того, монадические понимания дают нам возможность составлять недетерминированные результаты, т.е. Моделировать одновременное изучение всех ветвей.