How does return statement work in Haskell? [duplicate]

Question

Consider these functions

f1 :: Maybe Int
f1 = return 1

f2 :: [Int]
f2 = return 1

Both have the same statement return 1. But the results are different. f1 gives value Just 1 and f2 gives value [1]

Looks like Haskell invokes two different versions of return based on return type. I like to know more about this kind of function invocation. Is there a name for this feature in programming languages?

Answer 1

This is a long meandering answer!

As you've probably seen from the comments and Thomas's excellent (but very technical) answer You've asked a very hard question. Well done!

Rather than try to explain the technical answer I've tried to give you a broad overview of what Haskell does behind the scenes without diving into technical detail. Hopefully it will help you to get a big picture view of what's going on.

return is an example of type inference.

Most modern languages have some notion of polymorphism. For example var x = 1 + 1 will set x equal to 2. In a statically typed language 2 will usually be an int. If you say var y = 1.0 + 1.0 then y will be a float. The operator + (which is just a function with a special syntax)

Most imperative languages, especially object oriented languages, can only do type inference one way. Every variable has a fixed type. When you call a function it looks at the types of the argument and chooses a version of that function that fits the types (or complains if it can't find one).

When you assign the result of a function to a variable the variable already has a type and if it doesn't agree with the type of the return value you get an error.

So in an imperative language the "flow" of type deduction follows time in your program Deduce the type of a variable, do something with it and deduce the type of the result. In a dynamically typed language (such as Python or javascript) the type of a variable is not assigned until the value of the variable is computed (which is why there don't seem to be types). In a statically typed language the types are worked out ahead of time (by the compiler) but the logic is the same. The compiler works out what the types of variables are going to be, but it does so by following the logic of the program in the same way as the program runs.

In Haskell the type inference also follows the logic of the program. Being Haskell it does so in a very mathematically pure way (called System F). The language of types (that is the rules by which types are deduced) are similar to Haskell itself.

Now remember Haskell is a lazy language. It doesn't work out the value of anything until it needs it. That's why it makes sense in Haskell to have infinite data structures. It never occurs to Haskell that a data structure is infinite because it doesn't bother to work it out until it needs to.

Now all that lazy magic happens at the type level too. In the same way that Haskell doesn't work out what the value of an expression is until it really needs to, Haskell doesn't work out what the type of an expression is until it really needs to.

Consider this function

func (x : y : rest) = (x,y) : func rest
func _ = []

If you ask Haskell for the type of this function it has a look at the definition, sees [] and : and deduces that it's working with lists. But it never needs to look at the types of x and y, it just knows that they have to be the same because they end up in the same list. So it deduces the type of the function as [a] -> [a] where a is a type that it hasn't bothered to work out yet.

So far no magic. But it's useful to notice the difference between this idea and how it would be done in an OO language. Haskell doesn't convert the arguments to Object, do it's thing and then convert back. Haskell just hasn't been asked explicitly what the type of the list is. So it doesn't care.

Now try typing the following into ghci

maxBound - length ""
maxBound : "Hello"

Now what just happened !? minBound bust be a Char because I put it on the front of a string and it must be an integer because I added it to 0 and got a number. Plus the two values are clearly very different.

So what is the type of minBound? Let's ask ghci!

:type minBound
minBound :: Bounded a => a

AAargh! what does that mean? Basically it means that it hasn't bothered to work out exactly what a is, but is has to be Bounded if you type :info Bounded you get three useful lines

class Bounded a where
  minBound :: a
  maxBound :: a

and a lot of less useful lines

So if a is Bounded there are values minBound and maxBound of type a. In fact under the hood Bounded is just a value, it's "type" is a record with fields minBound and maxBound. Because it's a value Haskell doesn't look at it until it really needs to.

So I appear to have meandered somewhere in the region of the answer to your question. Before we move onto return (which you may have noticed from the comments is a wonderfully complex beast.) let's look at read.

ghci again

read "42" + 7
read "'H'" : "ello"
length (read "[1,2,3]")

and hopefully you won't be too surprised to find that there are definitions

read :: Read a => String -> a
class Read where
  read :: String -> a

so Read a is just a record containing a single value which is a function String -> a. Its very tempting to assume that there is one read function which looks at a string, works out what type is contained in the string and returns that type. But it does the opposite. It completely ignores the string until it's needed. When the value is needed, Haskell first works out what type it's expecting, once it's done that it goes and gets the appropriate version of the read function and combines it with the string.

now consider something slightly more complex

readList :: Read a => [String] -> a
readList strs = map read strs

under the hood readList actually takes two arguments readList' (Read a) -> [String] -> [a] readList' {read = f} strs = map f strs

Again as Haskell is lazy it only bothers looking at the arguments when it's needs to find out the return value, at that point it knows what a is, so the compiler can go and fine the right version of Read. Until then it doesn't care.

Hopefully that's given you a bit of an idea of what's happening and why Haskell can "overload" on the return type. But it's important to remember it's not overloading in the conventional sense. Every function has only one definition. It's just that one of the arguments is a bag of functions. read_str doesn't ever know what types it's dealing with. It just knows it gets a function String -> a and some Strings, to do the application it just passes the arguments to map. map in turn doesn't even know it gets strings. When you get deeper into Haskell it becomes very important that functions don't know very much about the types they're dealing with.

Now let's look at return.

Remember how I said that the type system in Haskell was very similar to Haskell itself. Remember that in Haskell functions are just ordinary values. Does this mean I can have a type that takes a type as an argument and returns another type? Of course it does!

You've seen some type functions Maybe takes a type a and returns another type which can either be Just a or Nothing. [] takes a type a and returns a list of as. Type functions in Haskell are usually containers. For example I could define a type function BinaryTree which stores a load of a's in a tree like structure. There are of course lots of much stranger ones.

So, if these type functions are similar to ordinary types I can have a typeclass that contains type functions. One such typeclass is Monad

class Monad m where
  return a -> m a
  (>>=) m a (a -> m b) -> m b

so here m is some type function. If I want to define Monad for m I need to define return and the scary looking operator below it (which is called bind)

As others have pointed out the return is a really misleading name for a fairly boring function. The team that designed Haskell have since realised their mistake and they're genuinely sorry about it. return is just an ordinary function that takes an argument and returns a Monad with that type in it. (You never asked what a Monad actually is so I'm not going to tell you)

Let's define Monad for m = Maybe! First I need to define return. What should return x be? Remember I'm only allowed to define the function once, so I can't look at x because I don't know what type it is. I could always return Nothing, but that seems a waste of a perfectly good function. Let's define return x = Just x because that's literally the only other thing I can do.

What about the scary bind thing? what can we say about x >>= f? well x is a Maybe a of some unknown type a and f is a function that takes an a and returns a Maybe b. Somehow I need to combine these to get a Maybe b`

So I need to define Nothing >== f. I can't call f because it needs an argument of type a and I don't have a value of type a I don't even know what 'a' is. I've only got one choice which is to define

Nothing >== f = Nothing

What about Just x >>= f? Well I know x is of type a and f takes a as an argument, so I can set y = f a and deduce that y is of type b. Now I need to make a Maybe b and I've got a b so ...

Just x >>= f = Just (f x)

So I've got a Monad! what if m is List? well I can follow a similar sort of logic and define

return x = [x]
[] >>= f = []
(x : xs) >>= a = f x ++ (xs >>= f)

Hooray another Monad! It's a nice exercise to go through the steps and convince yourself that there's no other sensible way of defining this.

So what happens when I call return 1?

Nothing!

Haskell's Lazy remember. The thunk return 1 (technical term) just sits there until someone needs the value. As soon as Haskell needs the value it know what type the value should be. In particular it can deduce that m is List. Now that it knows that Haskell can find the instance of Monad for List. As soon as it does that it has access to the correct version of return.

So finally Haskell is ready To call return, which in this case returns [1]!

Answer 2

The return function is from the Monad class:

class Applicative m => Monad (m :: * -> *) where
  ...
  return :: a -> m a

So return takes any value of type a and results in a value of type m a. The monad, m, as you've observed is polymorphic using the Haskell type class Monad for ad hoc polymorphism.

At this point you probably realize return is not an good, intuitive, name. It's not even a built in function or a statement like in many other languages. In fact a better-named and identically-operating function exists - pure. In almost all cases return = pure.

That is, the function return is the same as the function pure (from the Applicative class) - I often think to myself "this monadic value is purely the underlying a" and I try to use pure instead of return if there isn't already a convention in the codebase.

You can use return (or pure) for any type that is a class of Monad. This includes the Maybe monad to get a value of type Maybe a:

instance Monad Maybe where
...
    return      = pure  -- which is from Applicative

...
instance Applicative Maybe where
    pure = Just

Or for the list monad to get a value of [a]:

instance Applicative [] where
    {-# INLINE pure #-}
    pure x    = [x]

Or, as a more complex example, Aeson's parse monad to get a value of type Parser a:

instance Applicative Parser where
    pure a = Parser $ \_path _kf ks -> ks a