### Binary Search in Haskell and Python 3.6

I've been learning a lot about Haskell lately, so I decided to write my own implementation of binary search after coming across Jacob Sheehy's implementation. In the following I wanted a nicer functional interface to locating a value in an entire list. I also wanted it to be safe, using the Maybe monad in the event a value doesn't exist or the list is empty.
-- A humble implementation of binary search in Haskell
binarySearch :: Int -> [Int] -> Maybe Int
binarySearch _ [] = Nothing
binarySearch value list = search 0 ((length list) - 1)
where
search :: Int -> Int -> Maybe Int
search i j sublist = do
if i > j
then Nothing
else do
let midPoint = ((i + j) quot 2)
currentValue = list !! midPoint
-- compare outputs one of LT, GT, EQ
case compare value currentValue of
LT -> search i (midPoint - 1)
GT -> search (midPoint + 1) j
EQ -> Just midPoint

main :: IO()
main = do
print (binarySearch (1) [1..10])
I'm sure this is hardly the most efficient solution, but it lets me write a somewhat similar solution in Python for comparison, using code from prior posts.
#! /usr/bin/env python3.6
# -*- coding: utf-8 -*-

"""
What I believe to be the same (or similar) pattern as expressed in Haskell.
"""

from abc import abstractmethod
from typing import Callable, Any, Generic, TypeVar, List, Text, Optional

U = TypeVar('U')

"""
"""

@abstractmethod
def bind(self, f: Callable[[Any], Any]) -> 'Monad':
raise NotImplementedError

def __rshift__(self, f: Callable[[Any], Any]) -> 'Monad':
return self.bind(f)

@classmethod
@abstractmethod
def unit(cls, *args: Any) -> 'Monad':
raise NotImplementedError

"""
"""
def __init__(self, __value: Optional[U] =None, just: bool =True) -> None:
self.value = __value
self.just = just

def __str__(self) -> Text:
if self.just:
return f'Just({self.value})'
else:
return 'Nothing'

def __repr__(self) -> str:
return self.__str__()

def bind(self, f: Callable[[Any], Any]) -> 'Maybe':
if self.just:
# instead of having the function return a new instance internally
return Maybe(f(self.value))
else:
return self

@classmethod
def unit(cls, value: Optional[U] =None) -> 'Maybe':
return cls(value)

class Just(Maybe[U]):
"""
"""
def __init__(self, __value: Optional[U] =None) -> None:
super(Just, self).__init__(__value)

class Nothing(Maybe[U]):
"""
"""
def __init__(self) -> None:
super(Nothing, self).__init__(just=False)

def binarySearch(value: int, sorted_list: List[int]) -> Maybe[int]:
"""
Recursively search a sorted list for a value.
"""
length = len(sorted_list)

if not length:
return Nothing()

def search(lower_bound=0, upper_bound=length - 1):
if lower_bound > upper_bound:
return Nothing()

mid_point = (lower_bound + upper_bound) // 2
current_value = sorted_list[mid_point]

if current_value > value:
return search(lower_bound, mid_point - 1)
elif current_value < value:
return search(mid_point + 1, upper_bound)
else:
return Just(mid_point)

result = search()

return result

if __name__ == '__main__':
some_list = [1, 14, 16, 17, 21, 35]

print(binarySearch(1, some_list))  # Just(0)
print(binarySearch(2, some_list))  # Nothing
I've been learning a lot about typing while helping bring Python 2-style annotations to Pillow/PIL.

EDIT: I found while type checking with Mypy that defining a unit method in the ABC Monad violated the Liskov Substitution Principle, and so deleted it.)

EDIT 4/27/2018: I also wanted to add to this post, however late, that there is a great module by Florian Leitner, pymonad, that has many nice definitions of categorical types, like monads and monoids. However, while it does work with Python 3.6, it does not currently have support for typing, let alone generic types.