Figuring out which of several mutually exclusive, potentially inconclusive Bools is True

(Long lasting question, specific questions at the bottom)

I'm working on a hobby project that deals with subsets of countable types, and I want to find out which (possibly infinite) "given" value belongs to.

So, I have a series of mutually exclusive, potentially non-final values Bool

(in my case, the values โ€‹โ€‹of the features for a given value), which are:

  • Exactly one of them will evaluate up True

    to a finite time.
  • The rest will either be evaluated up False

    to a finite time, or their calculations will not stop.

and my goal is to figure out which one is returning True

.

A generic signature best suits my needs (I think!)

decide :: [(Bool, b)] -> b

      

(but I'm open to suggestions here, I can search b

at a later stage, say if it Int

works better).

Morally, it decide

should be equivalent snd . (\[x] -> x) . filter fst

if all calculations are completed (if it \[x] -> x

explodes, Iโ€™ll rather see a programmerโ€™s mistake earlier).

Here's an example of the desired behavior (I intentionally don't use even

it odd

in this example either , because the set indicator functions I'm working with may never return False

!):

type Natural = Integer
isNatural :: Integer -> Bool
isNatural = (>= 0)

evenOnNatural :: Natural -> Maybe Boolean
evenOnNatural x = decide [( x `elem` [0,2..],     Just True),
                          ( x `elem` [1,3..],     Just False),
                          ( not . isNatural $ x , Nothing)]

-- evenOnNatural 2 should be Just True
-- evenOnNatural 3 should be Just False
-- evenOnNatural (-1) should be Nothing (as it is outside the 'domain')

      


I have combined the following code, which does what I want for this example (and can serve as a reference implementation):

import Control.Monad(when)
import Control.Concurrent(forkIO,killThread)
import Control.Concurrent.MVar
import System.IO.Unsafe(unsafePerformIO) -- Oh dear!

decide :: [(Bool, a)] -> a
decide xs = unsafePerformIO $ do
    mv <- newEmptyMVar
    let actions = map (\(b,val) -> when b (putMVar mv val)) xs 
    threadIds <- mapM forkIO actions
    result <- takeMVar mv
    mapM_ killThread threadIds -- probably wrong, doesn't kill subthreads
    return result

      

I think about using Data.Unamb unambs

and assuming

combinators like this:

decide' :: [(Bool, a)] -> a
decide' = unambs . map (uncurry assuming)

      

which certainly looks much better! And I'm sure Conall Elliott is a better programmer than me :-)

But before I do that, I would like to answer the following questions:

  • Is it decide

    already available or implementable with the Haskell framework?
  • Does the c solution have the unambs

    behavior I want regarding mutual exclusivity?
  • Are there other important issues I should be aware of?

[I understand that this question in a less specific form may be better for SE or SE Code Code SE programmers; I tried to formulate it in such a way that it would answer unambiguously (ha!). ]

+3


source to share


1 answer


What you describe matches, it seems to me, the class Searchable

here: https://hackage.haskell.org/package/countable

The trick that is cool is described here: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/



There are some slides for further research: http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf

+1


source







All Articles