## Sunday, September 7, 2008

Either is standard Haskell datatype defined by

data Either a b = Left a | Right b

Let's define Either monad as follows:

return = Right
x >>= f = case x of
Left _ -> x
Right r -> f r

This means we fix the type of Left part and consider Either a as monadic constructor of kind * -> *. Binding operator has the following sense: the function transforms data if it's Right and leaves it unchanged if it's Left (it's similar to Maybe monad, Right corresponding to Just and Left corresponding to Nothing).

Now the puzzle itself. 1) Why the above code won't typecheck and 2) how to make it valid with minimal changes?

The answer on the first question was obvious for me, and I thank #haskellers for giving me solution to the second.

e.v.e said...

let me guess...

Left a -> Left a

?

Roman Cheplyaka said...

Correct :)

Bonus said...

I kind of thought it was going to be Left a -> Left a, probably because of the way Left _ would behave on Left undefined, however, I'm not sure exactly why this does not typecheck and Left a -> Left a does, anyone care to elaborate?

Bryan said...

Bonus, I think it has to do with the unification algorithm.

(>>=) :: m a -> (a -> m b) -> m b

The type checker has already determined that the variable 'x' is of type 'm a', or 'Either l a', and we need to return an 'm b' or 'Either l b'. So we need to recreate the Left so we get a fresh variable to type check against.

beroal said...

A long-winded explanation:

Just infer a type for (>>=):
Either a b1 -> (b1 -> Either a b2) -> Either a b2

So types don't much:
Either a b1 /= Either a b2

So (>>=) may not return its first argument. But you can construct 'Either a b2' from 'a'.

dino said...

I know you said "minimal changes", but I prefer the pattern match (which also does type check):
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8092265129089355, "perplexity": 2968.309343037973}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-15/segments/1398223202774.3/warc/CC-MAIN-20140423032002-00355-ip-10-147-4-33.ec2.internal.warc.gz"}