Haskell: может ли Lazy Evaluation помочь остановить голосование раньше?

Question

Предположим, у меня есть 10 различных функций (параллельных или нет), решающих одну и ту же проблему.Есть ли хороший способ реализовать схему голосования, которая лениво автоматически реализует, когда достигается большинство и больше не требуется вычислений?

obs .: Это больше вопрос о сфере действия / пределах ленивых ev.Конечно, простое «если» может обнаружить большинство.

Спасибо

[EDIT 1]

... простое «если» может обнаружить большинство.

Извините, я имел в виду "одиночное, если" -> "одиночное ожидание завершения всего процесса".

... параллельно или нет ...

Я просто не знаю, в этом случае имеет значение параллелизм.(проблемы с моим неоднозначным английским)

Answer 1

Краткий ответ. Да, такую ​​систему можно реализовать, но нет, встроенная лень вам не поможет.

Длинный ответ. Полагаю, вам нужна немного другая лень.Ленивая оценка Haskell является своего рода нормальным порядком оценки , который работает следующим образом:

1. Когда функция вызывается, оценщик сначала пытается вычислить ее, не вычисляя ее аргументы.
2. Если поток управления подходит к точке, где необходимо вычислить какой-либо аргумент, он оценивает его.Затем оценка функции продолжается.

Таким образом, аргументы оцениваются по мере необходимости «по требованию».Более того, они оцениваются один за другим .Это хорошая идея для самого языка, и даже императивные языки с аппликативным порядком оценки не могут работать без таких ленивых функций - операторы типа or и and по своей природе ленивы в большинстве языков программирования.Но в вашей ситуации это то, что вам действительно нужно?Нету.Вам нужно оценить все аргументы параллельно и завершить оценку самой функции, когда вычисляются некоторые аргументы.

Как внедрить. Вам необходимо полностью заново внедрить систему оценки, и я считаю, что чисто функциональное программирование без побочных эффектов и ленивых вычислений будет только мешать вам.Вот один из способов сделать это.Создайте функцию, скажем, paplly :: [ArgumentType] -> TriggerFunction -> ResultType, где papply означает «параллельное применение», ArgumentType - это тип фактических аргументов для вычисления (в вашем случае это может быть закрытие функции + решаемая задача), TriggerFunctionявляется функцией, которая вызывается при вычислении одного из аргументов, а ResultType в вашем случае является логическим.Эта функция должна работать следующим образом:

1. Запустить оценку всех аргументов параллельно.
2. Когда один из аргументов вычислен, он должен вызвать функцию TriggerFunction с результатом вычисления.
3. Функция триггера должна иметь «память» для запоминания всех предыдущих результатов.Если при вызове выясняется, что имеется достаточно аргументов для завершения оценки основной функции, он делает это, прерывая вычисление остальных аргументов.

Это только один из способов сделать это, не самый функциональный (в нем используется изменяемая «память»).Вы также можете запустить функцию триггера параллельно с другими аргументами и использовать какую-то синхронизацию для передачи управления между ними.Или вы можете использовать какие-то сообщения, как в Erlang или Scala.К сожалению, у меня недостаточно опыта работы с Haskell для написания реального кода, но пост @Dietrich Epp, похоже, представляет аналогичную идею, поэтому вы можете использовать его в качестве основы.

Answer 2

Вам нужна такая функция:

majority :: [Bool] -> Bool

И вы хотите, чтобы он работал параллельно. Нет пота! К сожалению, я не знаю способа сделать это без обхода системы типов. Вот пример реализации:

import Control.Concurrent
import Control.Concurrent.MVar
import System.IO.Unsafe

majority :: [Bool] -> Bool
majority votes = unsafePerformIO $
  do v <- newEmptyMVar
     nfalse <- newMVar 0
     ntrue <- newMVar 0
     let n = length votes
         m = (n `div` 2) + 1
         count x =
           let (var, min) = if x then (ntrue, m) else (nfalse, n-m+1)
           in do i <- modifyMVar var $ \i -> return (i+1, i+1)
                 if i == min then putMVar v x else return ()
     threads <- mapM (forkIO . count) votes
     r <- takeMVar v
     mapM_ killThread threads
     return r

Примечание: я не уверен, что это правильно.

Answer 3

Вы можете сделать это без параллельной оценки тривиально, используя ленивые натуралы. В этом случае я решил использовать пакет peano-inf для взлома: http://hackage.haskell.org/package/peano-inf

import Number.Peano.Inf
import Debug.Trace
import Data.List

myList = [trace "1" True, trace "2" True, trace "3" False, trace "4" True, trace "5" True]

btoNat True = 1 :: Nat
btoNat False = 0 :: Nat

ans = sum $ map btoNat myList
{-
*Main> ans > 2
1
2
3
4
True
-}

Обратите внимание, что 5 не печатается в трассировке, потому что оценка прервана до этого.

Чтобы сделать это с параллелизмом, требуется вручную создавать и убивать потоки и т. Д., Что хорошо, но, безусловно, менее приятно.

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

Answer 4

Я попытался объединить решение sclv с комментарием luqui о unamb и хотел бы поделиться своими результатами.Я начну с тестовых случаев:

list1 = [True, True, undefined, True, undefined]
list2 = [undefined, False, False]
list3 = concat $ replicate 500 list1
list4 = concat $ replicate 500 list2


main = mapM (print . vote) [list1, list2, list3, list4]

vote :: [Bool] -> Bool

Это должно вывести

True
False
True
False

Сначала я начну с примера list1.Функция голосования для ее передачи может выглядеть следующим образом:

voteByTrue list = sum (map bToNat list) >= threshold
  where
    threshold = (genericLength list + 1) `quot` 2

Это то же самое, что и в ответе sclv.Теперь нам нужно сделать sum более ленивым, чтобы вычисление не прерывалось при обнаружении undefined слагаемого.Мой первый взгляд на это был:

Zero |+ y = y
Succ x |+ y = Succ (x + y)

instance Num Nat where
    x + y = (x |+ y) `lub` (y |+ x)

Здесь |+ является строгим оператором сложения в первом аргументе, а + не является строгим в обоих аргументах.Он работал для примеров игрушек, как list1, но производительность этого решения очень быстро ухудшается из-за экспоненциального увеличения числа потоков (посмотрите, как каждый + порождает 2 потока, каждый из которых вызывает +опять же, обычно с теми же аргументами).При такой производительности vote list3 завершается недостаточно быстро.Чтобы бороться с этим, я попытался нарушить контракт unamb и реализовал следующую функцию:

-- | The same as unamb, but does not have the 
--   'agree unless bottom' precondition.
brokenUnamb = unamb

infoMinMax a b = (x, y) 
  where
    ~(x, y) = (a `seq` (b, a)) `brokenUnamb` (b `seq` (a, b))

Эта функция сортирует два аргумента по количеству информации, которой они располагают.Он всегда возвращает менее оцененное значение как x и более оцененное значение как y.Это нарушает чистоту, нарушая условие unamb аргументов, чтобы быть равными.Тем не менее, это позволяет нам реализовать + более эффективно:

instance Num Nat where
    x + y = x' |+ y' where (y', x') = infoMinMax x y

Это позволяет нам пройти большой тест (list3)!Теперь о ложных тестах ... Оказалось, что функция infoMinMax здесь тоже полезна!

vote list = voteByTrue list `maxInfo` voteByFalse list
  where
    voteByFalse = not . voteByTrue . map not
    maxInfo x y = snd (infoMinMax x y)

Теперь это позволяет программе пройти все четыре теста, хотя и большиенесколько секунд, чтобы закончить.Загрузка процессора возрастает до 200%, если я заменим undefined на odd (sum [1..]), поэтому некоторый параллелизм действительно имеет место.

Однако проблема нарушенной чистоты остается.Может кто-нибудь предложить решение, где достаточно простого unamb?

Answer 5

, если учесть, что эти функции выдают логические значения, возникает вопрос, можно ли написать функцию, которая принимает 10 логических значений и возвращает значение true, если 6 из них являются истинными, для которых всегда требуются значения менее 10 из ее входных данных.

простой способ, но не соответствующий заявленным требованиям, состоит в том, чтобы проверять каждый вход по очереди, подсчитывая количество истинных и ложных значений, если истинные значения> = 6 stop return true, в противном случае false => 6 stop returnfalse, и если мы достигнем последнего ввода, не вызвав ни одно из этих условий, вернем false.поскольку в некоторых случаях это будет проверять все входные данные, поэтому я думаю, что ответ на этот вопрос - нет, в этом примере ленивая оценка не поможет.