Haskell: can Lazy Evaluation help stop voting earlier?

Question

Suppose I have 10 heavy different functions (in parallel or not) that solve the same problem. Is there a good way to implement a voting scheme that is lazily-automatically implemented when a majority is reached and no longer needs to be calculated?

obs: This is more a question about the scope / limits of a lazy ev. Of course, a simple “if” could detect the majority.

thanks

[EDIT 1]

... a simple "if" could detect most.

Sorry, I meant by "single if" → "single wait to complete the whole process."

... parallel or not ...

I just don't know what parallelism matters in this case. (problems with my ambiguous English)

Answer 1

You can do this without parallel pricing trivially using lazy naturals. In this case, I decided to use the peano-inf package for hacking: 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 -} 

Please note that 5 is not printed in the trace because the score is reduced to this.

To do this, using parallelism requires the manual creation and destruction of threads, etc., which is fine, but, of course, less enjoyable.

Please note that the code above uses the standard amount. Such an unusual use case is why, although many people think it’s not worth it, the amount is not made as strict as possible.

Answer 2

The short answer. Yes, you can implement such a system, but no, the built-in laziness will not help.

Long answer. I believe that you need a slightly different laziness. Haskell's lazy rating is a kind of normal rating procedure that works as follows:

• When a function is called, the evaluator tries to calculate it first without calculating its arguments.
• If the control flow arrives at the point where some argument needs to be calculated, it evaluates it. Then the evaluation of the function continues.

So, arguments are evaluated as needed "on demand." Moreover, they are evaluated one after another. This is a good idea for the language itself, and even imperative languages ​​with an applied evaluation order cannot work without such lazy functions. Operators like or and and lazy in nature in most programming languages. But in your situation, is that what you really need? Nope. You need to evaluate all the arguments in parallel and finish evaluating the function itself when some of the arguments are computed.

How to implement. You need to completely repeat the evaluation system, and I believe that pure functional programming without side effects and lazy evaluation will only hinder you. Here is one way to do it. Create a function, say paplly :: [ArgumentType] -> TriggerFunction -> ResultType , where papply means "parallel use", ArgumentType is the type of actual arguments to calculate (in your case, it could be closing the problem with the + function), TriggerFunction is a function that is called when evaluating one of the arguments, and ResultType is logical in your case. This function should work as follows:

• Evaluate all arguments in parallel.
• When one of the arguments is evaluated, it must call the TriggerFunction function with the result of the evaluation.
• The trigger function must have a “memory” to remember all previous results. If the call reveals that there are enough arguments to complete the evaluation of the main function, it does this, interrupting the calculation of the remaining arguments.

This is only one way to do this, and not the most functional one (it uses mutable "memory"). You can also run a trigger function in parallel with other arguments and use some kind of synchronization to transfer control between all of them. Or you can use messages like Erlang or Scala. Unfortunately, I don't have enough experience with Haskell to write real code, but the @Dietrich Epp post seems like a similar idea, so you can use it as a base.

Answer 3

You need a function like this:

 majority :: [Bool] -> Bool 

And you want it to work in parallel. No sweat! Unfortunately, I do not know how to do this without going around the type system. Here is an example implementation:

 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 vx else return () threads <- mapM (forkIO . count) votes r <- takeMVar v mapM_ killThread threads return r 

Note. I am not sure if this is correct.

Answer 4

I tried combining the sclv solution with luqui's unamb and would like to share my results. I will start with test cases:

 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 

It should print

 True False True False 

First, I'll start with the list1 example. The voting function that passes may look like this:

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

This is the same as in sclv answer. Now we need to make sum lazier so that the calculation does not interrupt when it encounters an undefined term. My first take on this was:

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

Here |+ is the addition operator in the first argument, and + not strict in both of its arguments. He worked on toy examples, such as list1 , but the performance of this solution deteriorates very quickly due to exponentially inflating the number of threads (see How each + produces 2 threads, each of which calls + again, usually with the same arguments). With this kind of performance, vote list3 does not end fast enough. To deal with this, I tried to break the unamb contract and implemented the following function:

 -- | The same as unamb, but does not have the -- 'agree unless bottom' precondition. brokenUnamb = unamb infoMinMax ab = (x, y) where ~(x, y) = (a `seq` (b, a)) `brokenUnamb` (b `seq` (a, b)) 

This function sorts its two arguments by the amount of information they store. It always returns a less-valued value as x and a more-valued value as y . This violates cleanliness by violating the condition of unamb arguments to equal. However, this allows us to more efficiently implement + :

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

This allows us to take the big test ( list3 )! Now, to the false tests ... It turned out that the infoMinMax function is useful here!

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

Now this allows the program to pass all four tests, although the larger ones take a few seconds. CPU usage will increase dramatically to 200% if I replaced undefined with odd (sum [1..]) , so some parallelism does occur.

However, the problem of broken purity persists. Can anyone suggest a solution in which a simple unamb ?

Answer 5

considering that these functions cause Boolean functions, the question arises if one can write a function that takes 10 Boolean functions and returns true if 6 of them are true, which always requires values ​​less than 10 of its inputs.

an easy way, but one that does not meet the specified requirements, is to test each entry in turn, counting the number of truths and falsifications, if trues> = 6 stop return true else, if falses> = 6 stop return false and if we we get to the last input without starting any of these conditions, return false. as this checks all inputs in some cases, so I think there is no answer to this question, lazy evaluation does not help in this example.