return-type polymorphism of monads done right in a dynamic language

While monads can be encoded in dynamically-typed language, the usual encodings are usually uglier than monads in type-class-based language because type inference is not there to help determine which monad instance we're talking about. Some use-cases of type inference can be replaced by dynamic type dispatch, but not the so-called "return type polymorphism" where it is the type expected by the context that matters, not the type carried by values. Monads are just one instance where return-type polymorphism matters (in the form of "return : forall a, a -> m a"), but this is a general problem with other structures (typically structures with a default element such as monoids/groups).

Intuitively it seems that this problem would be solveable by keeping, in the dynamic type representation, a "not known yet" marker, and using the free monad operations in this case. But there is a gap from intuition from usable code, and Tony Garnock-Jones just wrote a very nice blog post exposing this technique in Racket:

Monads in Dynamically-Typed Languages


(run-io (do (mdisplay "Enter a number: ")
            n <- mread
            all-n <- (return (for/list [(i n)] i))
            evens <- (return (do i <- all-n
                                 #:guard (even? i)
                                 (return i)))
            (return evens)))

Doesn't work in general

This only works if there is no way to extract concrete information from the abstract type, doesn't it?

class Foo f where
    ret  :: a -> f a
    comp :: f a -> f b -> Bool

foo = let x = ret 10
          y = ret 'a'
      in  if comp x y then x else y  -- which branch to take?

By Matt M at Mon, 2015-01-26 15:18 | login or register to post comments

That sounds right.

The whole problem seems to involve time at a fairly basic level: we don't know the type "now", we will learn the type "later". So using the trick in circumstances where you need an answer now won't work. (For that reason, (coerce List (return 1)) is needed to make sure things are as expected when calling list primitives.)

An indirect CPS-like encoding of comp, where the program isn't so set on having the result right now, might be able to be made to work though. For example, and this is slightly handwavey, comp :: f a -> f b -> (Bool -> c) -> g c, where g would be some delayed computation structure coercible using the same mechanism that coerces fs, once the right type is known.

By tonyg at Mon, 2015-01-26 15:44 | login or register to post comments

Same in typed languages

Is your problem really different from the ambiguity that arises in:


class Print a where
  Print :: a -> String

class Parse a where 
  Parse :: String -> a

foo = Print (return (Parse a))

By gasche at Tue, 2015-01-27 15:31 | login or register to post comments

Somewhat different?

I think your code has bugs, but I assume you meant something like this:

foo = print . parse

This is an example where overloading on return type plainly can't work. You can't let the context figure out the instance if when the context works with any number of instances. My example above is one where overloading on return type works just fine, but isn't amenable to this dynamic encoding (unless you're ok with tricks a la Tony G's comment). I guess I'm just stating the obvious without any insight, but they do seem a little different to me. Shrug.

By Matt M at Tue, 2015-01-27 16:18 | login or register to post comments

Ben Wolfson

Apparently here was another library with support for return-type polymorphism in Clojure that I didn't know about:

https://github.com/bwo/monads

By gasche at Mon, 2015-01-26 18:15 | login or register to post comments

Lambda the Ultimate

User login

Navigation