monads.py

#! /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)


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