4 ms·

Incidentally, I am just reading through All About Monads (http://www.haskell.org/haskellwiki/All_About_Monads http://www.haskell.org/haskellwiki/All_About_Monad

Incidentally, I am just reading through All About Monads (http://www.haskell.org/haskellwiki/All_About_Monads http://www.haskell.org/haskellwiki/All_About_Monads) and his point 3 ("Allow polymorphism on return types") is what confused me in this example: getAny :: (Random a) => State StdGen a getAny = do g <- get (x,g') <- return $ random g put g' return x I was like.. how on Earth Haskell knows which function "get" should it call? I think this is a point which should be more stressed in the tutorials (I read Learn yourself a Haskell and glanced at couple of others..)

tel 13y ago
It's easy for a Haskell expert to sweep typeclass resolution under the rug, but it's definitely some pretty black magic at first no matter how "simple" its implementation is. The reality is that the compiler works really hard to ensure that it can guess the right "get" and it's pretty possible for it to fail. Of course, when it fails you know immediately and can remedy it by type annotations, but that can still be challenging. To answer the question, `get` has its principle type resolved by the type inference engine. In this case, `get`'s most general type is `MonadState s m => m s` and it can resolve what `m` is by unifying it with the type annotation of `getAny`, so we know that we need `get :: MonadState s (State StdGen) => State StdGen s`. From here, the compiler searches through the type class instances in a Prolog-like style to find that `MonadState s (State StdGen)` occurs when `s ~ StdGen`. This resolves more type information and also tells us which definition of `get` is needed—the one that was defined as `instance MonadState s (State s) where`! The end result is that get ends up with the type `get :: State StdGen StdGen` and is the function defined as `get = State $ \s -> (s, s)`.
- alipang 13y ago
  It's also quite possible for this type of functions to get a polymorphic type, in which case the compiler generate code that will pass along essentially a virtual table object for the particular instance of the call site. Hardly black magic.
  - tel 13y ago
    I agree that the implementation is quite obvious. It's the inference—the collusion between the HM type constraints and the Prolog-like typeclass constraints—that's magical.
- asgard1024 13y ago
  Thanks. I sometimes wonder, is there a way in Haskell to display a type signature of a function for a particular instance? For example, is there a way to display type of get when used as an instance of State ? I know I can derive it but I would sometimes like to see if I am correct..
  - acomar 13y ago
    Some vim and emacs plugins can give you the type of subexpressions like this. Namely, you want the ghc-mod plugin since it provides the hooks into the compiler to query type information.
    - asgard1024 13y ago
      Is there a way to do this in ghci? I know the :t command, but I don't know how to say that I want a specific instance.
  - tel 13y ago
    There's a hack you can use until Type Holes lands in production GHCi. If you turn on ImplicitParams you can write getAny :: (Random a) => State StdGen a getAny = do g <- ?whatAmI get (x,g') <- return $ random g put g' return x which will fail the type checker because your type didn't include the information about what ?whatAmI is---the error will be something like "could not find definition of ?whatAmI :: State StdGen StdGen -> State StdGen StdGen", although you may only get partial information as the compiler may complain about your undefined function before it's resolved what you're looking for. You can also leave off the type annotation and GHCi will infer the type of ?whatAmI. Then if you check the type of "getAny" you'll see getAny :: (?whatAmI::m s -> n s', RandomGen s', Random b, MonadState s m, MonadState s' n) => m b which provides all of the information the typechecker knows all in one go. Take note that the type it derives is somewhat more general than the one we want since it allows ?whatAmI to transform the involved monad. Obviously "get" doesn't do this.

tel 13y ago

It's easy for a Haskell expert to sweep typeclass resolution under the rug, but it's definitely some pretty black magic at first no matter how "simple" its implementation is. The reality is that the compiler works really hard to ensure that it can guess the right "get" and it's pretty possible for it to fail. Of course, when it fails you know immediately and can remedy it by type annotations, but that can still be challenging. To answer the question, `get` has its principle type resolved by the type inference engine. In this case, `get`'s most general type is `MonadState s m => m s` and it can resolve what `m` is by unifying it with the type annotation of `getAny`, so we know that we need `get :: MonadState s (State StdGen) => State StdGen s`. From here, the compiler searches through the type class instances in a Prolog-like style to find that `MonadState s (State StdGen)` occurs when `s ~ StdGen`. This resolves more type information and also tells us which definition of `get` is needed—the one that was defined as `instance MonadState s (State s) where`! The end result is that get ends up with the type `get :: State StdGen StdGen` and is the function defined as `get = State $ \s -> (s, s)`.

alipang 13y ago
It's also quite possible for this type of functions to get a polymorphic type, in which case the compiler generate code that will pass along essentially a virtual table object for the particular instance of the call site. Hardly black magic.
- tel 13y ago
  I agree that the implementation is quite obvious. It's the inference—the collusion between the HM type constraints and the Prolog-like typeclass constraints—that's magical.
asgard1024 13y ago
Thanks. I sometimes wonder, is there a way in Haskell to display a type signature of a function for a particular instance? For example, is there a way to display type of get when used as an instance of State ? I know I can derive it but I would sometimes like to see if I am correct..
- acomar 13y ago
  Some vim and emacs plugins can give you the type of subexpressions like this. Namely, you want the ghc-mod plugin since it provides the hooks into the compiler to query type information.
  - asgard1024 13y ago
    Is there a way to do this in ghci? I know the :t command, but I don't know how to say that I want a specific instance.
- tel 13y ago
  There's a hack you can use until Type Holes lands in production GHCi. If you turn on ImplicitParams you can write getAny :: (Random a) => State StdGen a getAny = do g <- ?whatAmI get (x,g') <- return $ random g put g' return x which will fail the type checker because your type didn't include the information about what ?whatAmI is---the error will be something like "could not find definition of ?whatAmI :: State StdGen StdGen -> State StdGen StdGen", although you may only get partial information as the compiler may complain about your undefined function before it's resolved what you're looking for. You can also leave off the type annotation and GHCi will infer the type of ?whatAmI. Then if you check the type of "getAny" you'll see getAny :: (?whatAmI::m s -> n s', RandomGen s', Random b, MonadState s m, MonadState s' n) => m b which provides all of the information the typechecker knows all in one go. Take note that the type it derives is somewhat more general than the one we want since it allows ?whatAmI to transform the involved monad. Obviously "get" doesn't do this.