Haskell - Maybe Either

Question

-- | Convert a 'Maybe a' to an equivalent 'Either () a'. Should be inverse
-- to 'eitherUnitToMaybe'.
maybeToEitherUnit :: Maybe a -> Either () a
maybeToEitherUnit a = error "Not yet implemented: maybeToEitherUnit"

-- | Convert a 'Either () a' to an equivalent 'Maybe a'. Should be inverse
-- to 'maybeToEitherUnit'.
eitherUnitToMaybe :: Either () a -> Maybe a
eitherUnitToMaybe = error "Not yet implemented: eitherUnitToMaybe"

-- | Convert a pair of a 'Bool' and an 'a' to 'Either a a'. Should be inverse
-- to 'eitherToPairWithBool'.
pairWithBoolToEither :: (Bool,a) -> Either a a
pairWithBoolToEither = undefined  -- What should I do here?

-- | Convert an 'Either a a' to a pair of a 'Bool' and an 'a'. Should be inverse
-- to 'pairWithBoolToEither'.
eitherToPairWithBool :: Either a a -> (Bool,a)
eitherToPairWithBool = undefined  -- What should I do here?

-- | Convert a function from 'Bool' to 'a' to a pair of 'a's. Should be inverse
-- to 'pairToFunctionFromBool'.
functionFromBoolToPair :: (Bool -> a) -> (a,a)
functionFromBoolToPair = error "Not yet implemented: functionFromBoolToPair"

-- | Convert a pair of 'a's to a function from 'Bool' to 'a'. Should be inverse
-- to 'functionFromBoolToPair'.
pairToFunctionFromBool :: (a,a) -> (Bool -> a)
pairToFunctionFromBool = error "Not yet implemented: pairToFunctionFromBool"

I don't really know what to do. I know what maybe is, but I think I have a problem with either, because Either a a makes no sense in my mind. Either a b would be okay. This is either a or b but Either a a is a?!

I don't have any idea in general how to write these functions.

Answer 1

Note that Either a b means quite literally that a value of such a type can be either an a, or an a. It sounds like you have actually grasped this concept, but the piece you're missing is that the Either type differentiates between values constructed with Left and those constructed with Right.

For the first part, the idea is that Maybe is either Just a thing or Nothing -- Nothing corresponds to () because both are "in essence" data types with only one possible value.

The idea behind converting (Bool, a) pairs to Either a a pairs might seem a little trickier, but just think about the correspondence between True and False and Left and Right.

As for converting functions of type (Bool -> a) to (a, a) pairs, here's a hint: Consider the fact that Bool can only have two types, and write down what that initial function argument might look like.

Hopefully those hints help you to get started.

Answer 2

Either a a makes no sense in my mind.

Yes it does. Try to figure out the difference between type a and Either a a. Either is a disjoint union. Once you understand the difference between a and Either a a, your homework should be easy in conjunction with AndrewC's answer.

Answer 3

Given that I think this is homework, I'll not answer, but give important hints:

If you look for the definitions on hoogle (http://www.haskell.org/hoogle/) you find

data Bool = True | False
data Either a b = Left a | Right b

This means that Bool can only be True or False, but that Either a b can be Left a or Right b.

which means your functions should look like

pairWithBoolToEither :: (Bool,a) -> Either a a
pairWithBoolToEither (True,a) = ....
pairWithBoolToEither (False,a) = ....

and

eitherToPairWithBool :: Either a a -> (Bool,a)
eitherToPairWithBool (Left a) = ....
eitherToPairWithBool (Right a) = ....

Comparing with Maybe

Maybe a is given by

data Maybe a = Just a | Nothing

so something of type Maybe Int could be Just 7 or Nothing.

Similarly, something of type Either Int Char could be Left 5 or Right 'c'.

Something of type Either Int Int could be Left 7 or Right 4.

So something with type Either Int Char is either an Int or a Char, but something of type Either Int Int is either an Int or an Int. You don't get to choose anything other than Int, but you'll know whether it was a Left or a Right.

Why you've been asked this/thinking behind it

If you have something of type Either a a, then the data (eg 5 in Left 5) is always of type a, and you've just tagged it with Left or Right. If you have something of type (Bool,a) the a-data (eg 5 in (True,5)) is always the same type, and you've paired it with False or True.

The maths word for two things which perhaps look different but actually have the same content is "isomorphic". Your instructor has asked you to write a pair of functions which show this isomorphism. Your answer will go down better if pairWithBoolToEither . eitherToPairWithBool and eitherToPairWithBool . pairWithBoolToEither do what id does, i.e. don't change anything. In fact, I've just spotted the comments in your question, where it says they should be inverses. In your write-up, you should show this by doing tests in ghci like

ghci> eitherToPairWithBool . pairWithBoolToEither $ (True,'h')
(True,'h')

and the other way round.

(In case you haven't seen it, $ is defined by f $ x = f x but $ has really low precedence (infixr 0 $), so f . g $ x is (f . g) $ x which is just (f . g) x and . is function composition, so (f.g) x = f (g x). That was a lot of explanation to save one pair of brackets!)

Functions that take or return functions

This can be a bit mind blowing at first when you're not used to it.

functionFromBoolToPair :: (Bool -> a) -> (a,a)

The only thing you can pattern match a function with is just a variable like f, so we'll need to do something like

functionFromBoolToPair f = ...

but what can we do with that f? Well, the easiest thing to do with a function you're given is to apply it to a value. What value(s) can we use f on? Well f :: (Bool -> a) so it takes a Bool and gives you an a, so we can either do f True or f False, and they'll give us two (probably different) values of type a. Now that's handy, because we needed to a values, didn't we?

Next have a look at

pairToFunctionFromBool :: (a,a) -> (Bool -> a)

The pattern match we can do for the type (a,a) is something like (x,y) so we'll need

pairToFunctionFromBool (x,y) = ....

but how can we return a function (Bool -> a) on the right hand side?

There are two ways I think you'll find easiest. One is to notice that since -> is right associative anyway, the type (a,a) -> (Bool -> a) is the same as (a,a) -> Bool -> a so we can actually move the arguments for the function we want to return to before the = sign, like this:

pairToFunctionFromBool (x,y) True  = ....
pairToFunctionFromBool (x,y) False = ....

Another way, which feels perhaps a little easier, would to make a let or where clause to define a function called something like f, where f :: Bool -> a< a bit like:

pairToFunctionFromBool (x,y) = f where
  f True = ....
  f False = ....

Have fun. Mess around.

Answer 4

Perhaps it's useful to note that Either a b is also called the coproduct, or sum, of the types a and b. Indeed it is now common to use

type (+) = Either

You can then write Either a b as a + b.

eitherToPairWithBool :: (a+a) -> (Bool,a)

Now common sense would dictate that we rewrite a + a as something like 2 ⋅ a. Believe it or not, that is exactly the meaning of the tuple type you're transforming to!

To explain: algebraic data types can roughly be seen as "counting¹ the number of possible constructions". So

data Bool = True | False

has two constructors. So sort of (this is not valid Haskell!)

type 2 = Bool

Tuples allow all the combinations of constructors from each argument. So for instance in (Bool, Bool), we have the values

      (False,False)
      (False,True )
      (True, False)
      (True, True )

You've guessed it: tuples are also called products. So the type (Bool, a) is basically 2 ⋅ a: for every value x :: a, we can create both the (False, x) tuple and the (True, x) tuple, alltogether twice as many as there are x values.

Much the same thing for Either a a: we always have both Left x and Right x as a possible value.

All your functions with "arithmetic types":

type OnePlus = Maybe

maybeToEitherUnit :: OnePlus a -> () + a
eitherUnitToMaybe :: () + a -> OnePlus a
pairWithBoolToEither :: 2 ⋅ a -> a + a
eitherToPairWithBool :: a + a -> 2 ⋅ a
functionFromBoolToPair :: a² -> a⋅a
pairToFunctionFromBool :: a⋅a -> a²

---

¹_{For pretty much any interesting type there are actually infinitely many possible values, still this kind of naïve arithmetic gets you surprisingly far.}