### 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.

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,

-- 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') class Monad: """ Abstract base monad type. """ @abstractmethod def bind(self, f: Callable[[Any], Any]) -> 'Monad': raise NotImplementedError def __rshift__(self, f: Callable[[Any], Any]) -> 'Monad': return self.bind(f)I've been learning a lot about~~@classmethod~~~~@abstractmethod~~~~def unit(cls, *args: Any) -> 'Monad':~~~~raise NotImplementedError~~class Maybe(Monad, Generic[U]): """ A Maybe monad. """ 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]): """ A successful Maybe monad. """ def __init__(self, __value: Optional[U] =None) -> None: super(Just, self).__init__(__value) class Nothing(Maybe[U]): """ A 'failed' Maybe monad. """ 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

`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.
## Comments

## Post a Comment