findRoot ::
    (Precision, effort) ->
    (effort -> RealApprox -> RealApprox) ->
    RealApprox ->
    RealApprox ->
    RealApprox
findRoot (prec, effFn) fn leftEndpoint rightEndpoint =
    case oppositeSigns leftSign rightSign of
        True ->
            shrinkLRandMerge (leftEndpointPrec, leftSign)  (rightEndpointPrec, rightSign)
        False ->
            error $
                "findRoot: cannot establish that the given function fn has opposite signs at the endpoints:"
                ++ "\n fn(" ++ show leftEndpointPrec ++ ") = " ++ show (fn effFn leftEndpointPrec)
                ++ "\n fn(" ++ show rightEndpointPrec ++ ") = " ++ show (fn effFn rightEndpointPrec)
    where
    leftSign = getSign leftEndpointPrec
    rightSign = getSign rightEndpointPrec
    getSign x =
        case (fnAtX >? 0, fnAtX <? 0) of
            (Just True, _) -> Just Positive
            (_, Just True) -> Just Negative
            _ -> Nothing
        where
        fnAtX = fn effFn x
    
    leftEndpointPrec = ensurePrecision prec leftEndpoint
    rightEndpointPrec = ensurePrecision prec rightEndpoint
    
    oppositeSigns (Just Positive) (Just Negative) = True
    oppositeSigns (Just Negative) (Just Positive) = True
    oppositeSigns _ _ = False
    
    shrinkLRandMerge lAndSign@(l,lSign) rAndSign@(r,rSign) =
        case findMidPointWithSign l r of
            Nothing -> l </\> r
            Just (mAndSign@(_, mSign))
                | oppositeSigns lSign mSign -> shrinkLRandMerge lAndSign mAndSign
                | oppositeSigns mSign rSign -> shrinkLRandMerge mAndSign rAndSign
    findMidPointWithSign l r =
        case potentialSplitPoints of
            [] -> Nothing
            mAndSign : _ -> Just mAndSign 
        where
        potentialSplitPoints = 
            filter hasSign $ map addSign $ pointsInBetween l r
        addSign x = (x, getSign x)
        hasSign (_, Nothing) = False
        hasSign _ = True
    pointsInBetween l r =
--        -- ensure the points are exact and in the interior of the interval [l,r]:
--        filter betweenLR $
--        map getLeftEndpoint $
        [
            (l * 2 + r) / 3
        ,
            (l + r * 2) / 3
        ]
--        where
--        betweenLR x =
--            ((l <? x) == Just True)
--            &&
--            ((x <? r) == Just True)
--        getLeftEndpoint x =
--            fst $ RefOrd.getEndpointsOut x
findRoot ::
    (Precision, effort) ->
    (effort -> RealApprox -> RealApprox) ->
    RealApprox ->
    RealApprox ->
    RealApprox
findRoot (prec, effFn) fn leftEndpoint rightEndpoint =
    case oppositeSigns leftSign rightSign of
        True ->
            shrinkLRandMerge (leftEndpointPrec, leftSign)  (rightEndpointPrec, rightSign)
        False ->
            error $
                "findRoot: cannot establish that the given function fn has opposite signs at the endpoints:"
                ++ "\n fn(" ++ show leftEndpointPrec ++ ") = " ++ show (fn effFn leftEndpointPrec)
                ++ "\n fn(" ++ show rightEndpointPrec ++ ") = " ++ show (fn effFn rightEndpointPrec)
    where
    leftSign = getSign leftEndpointPrec
    rightSign = getSign rightEndpointPrec
    getSign x =
        case (fnAtX >? 0, fnAtX <? 0) of
            (Just True, _) -> Just Positive
            (_, Just True) -> Just Negative
            _ -> Nothing
        where
        fnAtX = fn effFn x
    
    leftEndpointPrec = ensurePrecision prec leftEndpoint
    rightEndpointPrec = ensurePrecision prec rightEndpoint
    
    oppositeSigns (Just Positive) (Just Negative) = True
    oppositeSigns (Just Negative) (Just Positive) = True
    oppositeSigns _ _ = False
    
    shrinkLRandMerge lAndSign@(l,lSign) rAndSign@(r,rSign) =
        case findMidPointWithSign l r of
            Nothing -> l </\> r
            Just (mAndSign@(_, mSign))
                | oppositeSigns lSign mSign -> shrinkLRandMerge lAndSign mAndSign
                | oppositeSigns mSign rSign -> shrinkLRandMerge mAndSign rAndSign
    findMidPointWithSign l r =
        case potentialSplitPoints of
            [] -> Nothing
            mAndSign : _ -> Just mAndSign 
        where
        potentialSplitPoints = 
            filter hasSign $ map addSign $ pointsInBetween l r
        addSign x = (x, getSign x)
        hasSign (_, Nothing) = False
        hasSign _ = True
    pointsInBetween l r =
--        -- ensure the points are exact and in the interior of the interval [l,r]:
--        filter betweenLR $
--        map getLeftEndpoint $
        [
            (l * 2 + r) / 3
        ,
            (l + r * 2) / 3
        ]
--        where
--        betweenLR x =
--            ((l <? x) == Just True)
--            &&
--            ((x <? r) == Just True)
--        getLeftEndpoint x =
--            fst $ RefOrd.getEndpointsOut x
findRoot (prec, effFn) fn leftEndpoint rightEndpoint =
    case oppositeSigns leftSign rightSign of
        True ->
            shrinkLRandMerge (leftEndpointPrec, leftSign)  (rightEndpointPrec, rightSign)
        False ->
            error $
                "findRoot: cannot establish that the given function fn has opposite signs at the endpoints:"
                ++ "\n fn(" ++ show leftEndpointPrec ++ ") = " ++ show (fn effFn leftEndpointPrec)
                ++ "\n fn(" ++ show rightEndpointPrec ++ ") = " ++ show (fn effFn rightEndpointPrec)
    where
    leftSign = getSign leftEndpointPrec
    rightSign = getSign rightEndpointPrec
    getSign x =
        case (fnAtX >? 0, fnAtX <? 0) of
            (Just True, _) -> Just Positive
            (_, Just True) -> Just Negative
            _ -> Nothing
        where
        fnAtX = fn effFn x
    
    leftEndpointPrec = ensurePrecision prec leftEndpoint
    rightEndpointPrec = ensurePrecision prec rightEndpoint
    
    oppositeSigns (Just Positive) (Just Negative) = True
    oppositeSigns (Just Negative) (Just Positive) = True
    oppositeSigns _ _ = False
    
    shrinkLRandMerge lAndSign@(l,lSign) rAndSign@(r,rSign) =
        case findMidPointWithSign l r of
            Nothing -> l </\> r
            Just (mAndSign@(_, mSign))
                | oppositeSigns lSign mSign -> shrinkLRandMerge lAndSign mAndSign
                | oppositeSigns mSign rSign -> shrinkLRandMerge mAndSign rAndSign
    findMidPointWithSign l r =
        case potentialSplitPoints of
            [] -> Nothing
            mAndSign : _ -> Just mAndSign 
        where
        potentialSplitPoints = 
            filter hasSign $ map addSign $ pointsInBetween l r
        addSign x = (x, getSign x)
        hasSign (_, Nothing) = False
        hasSign _ = True
    pointsInBetween l r =
--        -- ensure the points are exact and in the interior of the interval [l,r]:
--        filter betweenLR $
--        map getLeftEndpoint $
        [
            (l * 2 + r) / 3
        ,
            (l + r * 2) / 3
        ]
--        where
--        betweenLR x =
--            ((l <? x) == Just True)
--            &&
--            ((x <? r) == Just True)
--        getLeftEndpoint x =
--            fst $ RefOrd.getEndpointsOut x