<s> import functools <EOL> import types <EOL> import string <EOL> import sys <EOL> from collections import namedtuple <EOL> from hindley_milner import TypeVariable <EOL> from hindley_milner import TypeOperator <EOL> from hindley_milner import Var <EOL> from hindley_milner import App <EOL> from hindley_milner import Lam <EOL> from hindley_milner import unify <EOL> from hindley_milner import analyze <EOL> from hindley_milner import Function <EOL> from hindley_milner import Tuple <EOL> from hindley_milner import ListType <EOL> if sys . version [ <NUM_LIT:0> ] == '<STR_LIT:2>' : <EOL> lowercase = string . lowercase <EOL> else : <EOL> lowercase = string . ascii_lowercase <EOL> if sys . version [ <NUM_LIT:0> ] == '<STR_LIT:2>' : <EOL> __python_builtins__ = set ( ( <EOL> types . BooleanType , types . BufferType , types . BuiltinFunctionType , <EOL> types . BuiltinMethodType , types . ClassType , types . CodeType , <EOL> types . ComplexType , types . DictProxyType , types . DictType , <EOL> types . DictionaryType , types . EllipsisType , types . FileType , <EOL> types . FloatType , types . FrameType , types . FunctionType , <EOL> types . GeneratorType , types . GetSetDescriptorType , types . InstanceType , <EOL> types . IntType , types . LambdaType , types . ListType , types . LongType , <EOL> types . MemberDescriptorType , types . MethodType , types . ModuleType , <EOL> types . NoneType , types . NotImplementedType , types . ObjectType , <EOL> types . SliceType , types . StringType , types . StringTypes , <EOL> types . TracebackType , types . TupleType , types . TypeType , <EOL> types . UnboundMethodType , types . UnicodeType , types . XRangeType , set , <EOL> frozenset ) ) <EOL> __python_function_types__ = set ( ( <EOL> types . FunctionType , types . LambdaType , types . MethodType , <EOL> types . UnboundMethodType , types . BuiltinFunctionType , <EOL> types . BuiltinMethodType ) ) <EOL> else : <EOL> __python_builtins__ = set ( ( <EOL> bool , dict , type ( Ellipsis ) , float , int , type ( None ) , str , tuple , <EOL> type , types . BuiltinFunctionType , types . BuiltinMethodType , <EOL> types . CodeType , types . DynamicClassAttribute , types . FrameType , <EOL> types . FunctionType , types . GeneratorType , types . GetSetDescriptorType , <EOL> types . LambdaType , types . MappingProxyType , types . MemberDescriptorType , <EOL> types . MethodType , types . ModuleType , types . TracebackType ) ) <EOL> __python_function_types__ = set ( ( <EOL> types . FunctionType , types . LambdaType , types . MethodType , <EOL> types . BuiltinFunctionType , types . BuiltinMethodType ) ) <EOL> def is_builtin ( cls ) : <EOL> """<STR_LIT>""" <EOL> return cls in __python_builtins__ <EOL> def nt_to_tuple ( nt ) : <EOL> """<STR_LIT>""" <EOL> return tuple ( ( getattr ( nt , f ) for f in nt . __class__ . _fields ) ) <EOL> class TypeMeta ( type ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , * args ) : <EOL> super ( TypeMeta , self ) . __init__ ( * args ) <EOL> self . __instances__ = { } <EOL> self . __dependencies__ = self . mro ( ) [ <NUM_LIT:1> : - <NUM_LIT:2> ] <EOL> def __getitem__ ( self , item ) : <EOL> try : <EOL> if isinstance ( item , ADT ) : <EOL> return self . __instances__ [ id ( item . __type_constructor__ ) ] <EOL> elif isinstance ( typeof ( item ) , ListType ) : <EOL> return self . __instances__ [ id ( type ( item ) ) ] <EOL> elif isinstance ( item , Hask ) : <EOL> return self . __instances__ [ id ( typeof ( item ) ) ] <EOL> return self . __instances__ [ id ( type ( item ) ) ] <EOL> except KeyError : <EOL> raise TypeError ( "<STR_LIT>" . format ( item ) ) <EOL> class Typeclass ( object ) : <EOL> """<STR_LIT>""" <EOL> __metaclass__ = TypeMeta <EOL> @ classmethod <EOL> def make_instance ( typeclass , type_ , * args ) : <EOL> raise NotImplementedError ( "<STR_LIT>" ) <EOL> @ classmethod <EOL> def derive_instance ( typeclass , type_ ) : <EOL> raise NotImplementedError ( "<STR_LIT>" ) <EOL> def build_instance ( typeclass , cls , attrs ) : <EOL> """<STR_LIT>""" <EOL> for dep in typeclass . __dependencies__ : <EOL> if id ( cls ) not in dep . __instances__ : <EOL> raise TypeError ( "<STR_LIT>" % dep . __name__ ) <EOL> __methods__ = namedtuple ( "<STR_LIT>" % str ( id ( cls ) ) , attrs . keys ( ) ) ( ** attrs ) <EOL> typeclass . __instances__ [ id ( cls ) ] = __methods__ <EOL> return <EOL> def has_instance ( cls , typeclass ) : <EOL> """<STR_LIT>""" <EOL> if not issubclass ( typeclass , Typeclass ) : <EOL> return False <EOL> return id ( cls ) in typeclass . __instances__ <EOL> class Hask ( object ) : <EOL> """<STR_LIT>""" <EOL> def __type__ ( self ) : <EOL> raise TypeError ( ) <EOL> class Undefined ( Hask ) : <EOL> """<STR_LIT>""" <EOL> def __type__ ( self ) : <EOL> return TypeVariable ( ) <EOL> class PyFunc ( object ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> def typeof ( obj ) : <EOL> """<STR_LIT>""" <EOL> TypeVariable . next_var_name = '<STR_LIT:a>' <EOL> if isinstance ( obj , Hask ) : <EOL> return obj . __type__ ( ) <EOL> elif isinstance ( obj , tuple ) : <EOL> return Tuple ( map ( typeof , obj ) ) <EOL> elif obj is None : <EOL> return TypeOperator ( None , [ ] ) <EOL> elif type ( obj ) in __python_function_types__ : <EOL> return TypeOperator ( PyFunc , [ ] ) <EOL> return TypeOperator ( type ( obj ) , [ ] ) <EOL> class TypeSignature ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , args , constraints ) : <EOL> self . args = args <EOL> self . constraints = constraints <EOL> class TypeSignatureHKT ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , tcon , params ) : <EOL> self . tcon = tcon <EOL> self . params = params <EOL> class TypeSignatureError ( Exception ) : <EOL> pass <EOL> def build_sig_arg ( arg , cons , var_dict ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( arg , str ) and all ( ( l in lowercase for l in arg ) ) : <EOL> if arg not in var_dict : <EOL> if arg in cons : <EOL> var_dict [ arg ] = TypeVariable ( constraints = cons [ arg ] ) <EOL> else : <EOL> var_dict [ arg ] = TypeVariable ( ) <EOL> return var_dict [ arg ] <EOL> elif isinstance ( arg , TypeSignature ) : <EOL> return make_fn_type ( build_sig ( arg , var_dict ) ) <EOL> elif isinstance ( arg , TypeSignatureHKT ) : <EOL> if type ( arg . tcon ) == str : <EOL> hkt = build_sig_arg ( arg . tcon , cons , var_dict ) <EOL> else : <EOL> hkt = arg . tcon <EOL> return TypeOperator ( hkt , [ build_sig_arg ( a , cons , var_dict ) <EOL> for a in arg . params ] ) <EOL> elif arg is None : <EOL> return TypeOperator ( None , [ ] ) <EOL> elif isinstance ( arg , tuple ) : <EOL> return Tuple ( map ( lambda x : build_sig_arg ( x , cons , var_dict ) , arg ) ) <EOL> elif isinstance ( arg , list ) and len ( arg ) == <NUM_LIT:1> : <EOL> return ListType ( build_sig_arg ( arg [ <NUM_LIT:0> ] , cons , var_dict ) ) <EOL> elif isinstance ( arg , type ) : <EOL> return TypeOperator ( arg , [ ] ) <EOL> raise TypeSignatureError ( "<STR_LIT>" % arg ) <EOL> def make_fn_type ( params ) : <EOL> """<STR_LIT>""" <EOL> if len ( params ) == <NUM_LIT:2> : <EOL> last_input , return_type = params <EOL> return Function ( last_input , return_type ) <EOL> return Function ( params [ <NUM_LIT:0> ] , make_fn_type ( params [ <NUM_LIT:1> : ] ) ) <EOL> def build_sig ( type_signature , var_dict = None ) : <EOL> """<STR_LIT>""" <EOL> args = type_signature . args <EOL> cons = type_signature . constraints <EOL> var_dict = { } if var_dict is None else var_dict <EOL> return [ build_sig_arg ( i , cons , var_dict ) for i in args ] <EOL> class TypedFunc ( Hask ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , fn , fn_args , fn_type ) : <EOL> self . __doc__ = fn . __doc__ <EOL> self . func = fn <EOL> self . fn_args = fn_args <EOL> self . fn_type = fn_type <EOL> return <EOL> def __type__ ( self ) : <EOL> return self . fn_type <EOL> def __call__ ( self , * args , ** kwargs ) : <EOL> env = { id ( self ) : self . fn_type } <EOL> env . update ( { id ( arg ) : typeof ( arg ) for arg in args } ) <EOL> ap = Var ( id ( self ) ) <EOL> for arg in args : <EOL> if isinstance ( arg , Undefined ) : <EOL> return arg <EOL> ap = App ( ap , Var ( id ( arg ) ) ) <EOL> result_type = analyze ( ap , env ) <EOL> if len ( self . fn_args ) - <NUM_LIT:1> == len ( args ) : <EOL> result = self . func ( * args ) <EOL> unify ( result_type , typeof ( result ) ) <EOL> return result <EOL> return TypedFunc ( functools . partial ( self . func , * args , ** kwargs ) , <EOL> self . fn_args [ len ( args ) : ] , result_type ) <EOL> def __mod__ ( self , arg ) : <EOL> """<STR_LIT>""" <EOL> return self . __call__ ( arg ) <EOL> def __mul__ ( self , fn ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( fn , TypedFunc ) : <EOL> return fn . __rmul__ ( self ) <EOL> env = { id ( self ) : self . fn_type , id ( fn ) : fn . fn_type } <EOL> compose = Lam ( "<STR_LIT>" , App ( Var ( id ( self ) ) , App ( Var ( id ( fn ) ) , Var ( "<STR_LIT>" ) ) ) ) <EOL> newtype = analyze ( compose , env ) <EOL> composed_fn = lambda x : self . func ( fn . func ( x ) ) <EOL> newargs = [ fn . fn_args [ <NUM_LIT:0> ] ] + self . fn_args [ <NUM_LIT:1> : ] <EOL> return TypedFunc ( composed_fn , fn_args = newargs , fn_type = newtype ) <EOL> class ADT ( Hask ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> def make_type_const ( name , typeargs ) : <EOL> """<STR_LIT>""" <EOL> def raise_fn ( err ) : <EOL> raise err ( ) <EOL> default_attrs = { "<STR_LIT>" : tuple ( typeargs ) , "<STR_LIT>" : ( ) } <EOL> cls = type ( name , ( ADT , ) , default_attrs ) <EOL> cls . __type__ = lambda self : TypeOperator ( cls , [ TypeVariable ( ) for i in cls . __params__ ] ) <EOL> cls . __iter__ = lambda self : raise_fn ( TypeError ) <EOL> cls . __contains__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __add__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __radd__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __rmul__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __mul__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __lt__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __gt__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __le__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __ge__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __eq__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __ne__ = lambda self , other : raise_fn ( TypeError ) <EOL> cls . count = lambda self , other : raise_fn ( TypeError ) <EOL> cls . index = lambda self , other : raise_fn ( TypeError ) <EOL> cls . __repr__ = object . __repr__ <EOL> cls . __str__ = object . __str__ <EOL> return cls <EOL> def make_data_const ( name , fields , type_constructor , slot_num ) : <EOL> """<STR_LIT>""" <EOL> base = namedtuple ( name , [ "<STR_LIT>" % i for i , _ in enumerate ( fields ) ] ) <EOL> cls = type ( name , ( type_constructor , base ) , { } ) <EOL> cls . __type_constructor__ = type_constructor <EOL> cls . __ADT_slot__ = slot_num <EOL> if len ( fields ) == <NUM_LIT:0> : <EOL> cls = cls ( ) <EOL> else : <EOL> def __type__ ( self ) : <EOL> args = [ typeof ( self [ fields . index ( p ) ] ) if p in fields else TypeVariable ( ) <EOL> for p in type_constructor . __params__ ] <EOL> return TypeOperator ( type_constructor , args ) <EOL> cls . __type__ = __type__ <EOL> type_constructor . __constructors__ += ( cls , ) <EOL> return cls <EOL> def build_ADT ( typename , typeargs , data_constructors , to_derive ) : <EOL> """<STR_LIT>""" <EOL> newtype = make_type_const ( typename , typeargs ) <EOL> dcons = [ make_data_const ( dc_name , dc_fields , newtype , i ) <EOL> for i , ( dc_name , dc_fields ) in enumerate ( data_constructors ) ] <EOL> for tclass in to_derive : <EOL> tclass . derive_instance ( newtype ) <EOL> for i , ( dc_name , dc_fields ) in enumerate ( data_constructors ) : <EOL> if len ( dc_fields ) == <NUM_LIT:0> : <EOL> continue <EOL> return_type = TypeSignatureHKT ( newtype , typeargs ) <EOL> sig = TypeSignature ( list ( dc_fields ) + [ return_type ] , [ ] ) <EOL> sig_args = build_sig ( sig , { } ) <EOL> dcons [ i ] = TypedFunc ( dcons [ i ] , sig_args , make_fn_type ( sig_args ) ) <EOL> return tuple ( [ newtype , ] + dcons ) <EOL> class PatternMatchBind ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , name ) : <EOL> self . name = name <EOL> return <EOL> class PatternMatchListBind ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , head , tail ) : <EOL> self . head = head <EOL> self . tail = tail <EOL> return <EOL> def pattern_match ( value , pattern , env = None ) : <EOL> """<STR_LIT>""" <EOL> env = { } if env is None else env <EOL> if isinstance ( pattern , PatternMatchBind ) : <EOL> if pattern . name in env : <EOL> raise SyntaxError ( "<STR_LIT>" % pattern . name ) <EOL> env [ pattern . name ] = value <EOL> return True , env <EOL> elif isinstance ( pattern , PatternMatchListBind ) : <EOL> head , tail = list ( value [ : len ( pattern . head ) ] ) , value [ len ( pattern . head ) : ] <EOL> matches , env = pattern_match ( head , pattern . head , env ) <EOL> if matches : <EOL> return pattern_match ( tail , pattern . tail , env ) <EOL> return False , env <EOL> elif type ( value ) == type ( pattern ) : <EOL> if isinstance ( value , ADT ) : <EOL> return pattern_match ( nt_to_tuple ( value ) , nt_to_tuple ( pattern ) , env ) <EOL> elif hasattr ( value , "<STR_LIT>" ) : <EOL> matches = [ ] <EOL> if len ( value ) != len ( pattern ) : <EOL> return False , env <EOL> for v , p in zip ( value , pattern ) : <EOL> match_status , env = pattern_match ( v , p , env ) <EOL> matches . append ( match_status ) <EOL> return all ( matches ) , env <EOL> elif value == pattern : <EOL> return True , env <EOL> return False , env </s>
