A Proper Constant Function in Scala

This evening there was a discussion in #scala on Freenode about how to define a properly quantified and appropriately lazy constant function in Scala. In short, the following does not suffice for two reasons:

def const[A,B](a: A) = (b: B) => a

Firstly, it’s too strict. The B argument is always evaluated, so this fails:

scala> val x = const(7)(error("too strict"))
java.lang.RuntimeException: too strict

Secondly, it’s not properly quantified:

scala> val x = const _
x: (Nothing) => (Any) => Nothing = <function1>

That type should be [A,B](A => B => A). That is, the function x should be polymorphic in its arguments.

This exposes a shortcoming with a fundamental design decision about how functions are represented in Scala. The representation is a little bit naive, but suffices for most day-to-day coding. But, for higher-order programming (like abstracting over combinator libraries), specifically to properly encode the constant function, what’s needed is a representation similar to this:

// The identity functor that maps every type to itself
type Id[A] = A

// A constant functor that maps every type to A
trait Const[A] { type Apply[B] = A }

// A natural transformation between functors
trait ~>[F[_],G[_]] { def apply[B](f: => F[B]): G[B] }

// A natural transformation from the identity functor to the constant functor,
// or if you like, the type of functions that return A but are
// polymorphic in their argument.
type K[A] = Id ~> Const[A]#Apply

// The non-strict, universally quantified constant function.
def const = new (Id ~> K) {
  def apply[A](a: => A) = new K[A] {
    def apply[B](b: => B) = a
  }
}

This is now sufficiently lazy and properly quantified:

scala> val x = const
x: java.lang.Object with ~>[Id,K] = $anon$1@8f84a7

scala> val y = x(7)
y: K[Int] = $anon$1$$anon$2@1eb89ca

scala> val z = y(error("too strict"))
z: Int = 7

We can implicitly convert various applications of ~> to regular old Function1. For example:

implicit def kToFn[A,B](f: K[A]) = (b: B) => f(b): A

Which lets us now use our universally quantified nonstrict constant function in the usual manner:

scala> val x = List(1,2,3) map const(7)
x: List[Int] = List(7, 7, 7)

23 thoughts on “A Proper Constant Function in Scala

  1. Damn, I didn’t realise scala.Function.const was strict before now! You learn something new every day :-)

    At least a non-strict version is possible (even if you need to jump through what seems like a lot of hoops to get to it).

    By the way, it looks like there’s a typo in the third code snippet – I guess `k` should be `const`.

  2. @Eyal
    Care to expand? Horrible in the sense of “is too verbose compared to the Haskell version” or “I don’t like static typing”? Horrible in the sense of “I don’t understand it so it must be bad”? Horrible in the same way the landscape looks all blurry when driving a high speed sports car? :)

    • Horrible in the sense of “is too verbose compared to the Haskell version”:

      const :: a -> b -> a
      const x _ = x

      • Yes, this is an unfortunate consequence of the fact that Scala is strict by default and does not have polymorphic first-class values.

      • Thanks for the clarification. The type annotations can be really verbose and cumbersome to use, but on the other hand, I like the fact that in Scala, at least you can express those concepts.

    • It’s debatable whether this makes up for the sacrifices, but Scala is natively interoperable with Java, and it has first-class modules. A lot of people find the former a desirable property, but it constrains the language design somewhat. The latter is very handy when programming “in the large”.

      It’s not really up for debate that Scala comes out the loser in any comparison against Haskell. I just wanted to show a problem with the Scala standard libraries and present a reasonable solution.

      • > It’s not really up for debate that Scala comes out the loser in any comparison against Haskell. > I just wanted to show a problem with the Scala standard libraries and present a reasonable solution.

        I would challenge that. Scala’s goal was never to be a “better Haskell”, if they wanted to that they would just probably done it.

        Scala is a general-purpose language which was built to solve real world problems.
        Scala doesn’t force people to use a specific paradigm to solve problems.

        On the way to provide developers a language they actually want to use certain compromises have been made. For instance they choose a simpler type inference mechanism than Haskell, because that was the requirement for having OO in the language. Personally, I’m quite happy with that compromise.

        But in the end the amount of type annotations people write in Scala/Haskell will be the same.
        Scala will make people write type annotations for method arguments from day one.
        Haskellers will do the same once they have the first hard-to-debug bug due to Haskell happily inferencing a type the programmer didn’t expect, making the program crash not in that function but in a different, totally unrelated functions later.

        If Haskell’s features are so important to you why don’t you use scalaz?

        Having bought the book “Real World Haskell” a few weeks ago, I have to say that it is not as well-written as “Programming in Scala” but does the job.
        Haskell is maybe 30 years ahead of those languages in mainstream use today, but from a usability point of view, it has probably 15 years of work ahead before being usable.

        That’s the nice thing about Scala: I have 95% of the future now.

        OK, end of trolling :-)

      • > I would challenge that. Scala’s goal was never to be a “better Haskell”, if they wanted to that they would just probably done it.

        You would challenge that, but this isn’t the forum for language advocacy. We’re all aware that improving on Haskell was not one of Scala’s design goals. But comparing languages is interesting and educational, if done irreligiously.

        > Scala is a general-purpose language which was built to solve real world problems.

        So is Haskell, so is Java, etc. Specifically, Haskell’s main design goal was to solve the real-world problems of modularisation of software and program correctness.

        > Scala doesn’t force people to use a specific paradigm to solve problems.

        Yes it does. It forces you to use the specific paradigm of programming with first-class modules.

        > For instance they choose a simpler type inference mechanism than Haskell, because that was the requirement for having OO in the language. Personally, I’m quite happy with that compromise.

        “Having OO in the language” is pretty meaningless. More specifically, subtyping restricts Scala’s type inference. This compromise comes at a great cost when programming at higher levels of abstraction (e.g. when designing combinator libraries). But subtyping actually offers no benefit, so it’s more of a sacrifice than a compromise. You’re happy with it because subtyping is familiar to you. But it would be quite easy for you to become familiar with a less expensive alternative.

        > But in the end the amount of type annotations people write in Scala/Haskell will be the same.

        Having written a good amount of code in both of these languages, I can tell you with some confidence that this is false. In Haskell, you generally want to annotate the types of supercombinators as a sanity check, and at that level you should already know the types as part of your design. But Scala actually requires type annotations at a much finer level of granularity, and you end up spending your time inferring types at a level where you don’t care very much about them. The result is that when Haskell gives you a type error, you know that you have a mistake in your code and you spend time finding and fixing it. When Scala gives you a type error, you don’t know if the mistake is yours or if Scala just needs more type annotation, and you spend time figuring this out first (and this step will involve manual type inference on your part), as well as finding and fixing your mistake if you have one.

        > If Haskell’s features are so important to you why don’t you use scalaz?

        I am one of the authors of Scalaz, and I use it pervasively.

        > Having bought the book “Real World Haskell” a few weeks ago, I have to say that it is not as well-written as “Programming in Scala” but does the job.

        I agree. I recommend “Programming in Haskell” by Graham Hutton instead of RWH. “Programming in Scala” is really rather jolly good.

        > Haskell is maybe 30 years ahead of those languages in mainstream use today, but from a usability point of view, it has probably 15 years of work ahead before being usable.

        This is just a cheap smear. Usable by whom and for what purpose? Lots of people/companies are using it and getting good results.

    • Maybe “actually being used in real world applications”?
      Built-in compatibility with and easy migration from less sophisticated languages like Java?
      Object-oriented features built in when people need them? (I know a true Haskeller considers that useless.)

      • Steve,

        You should know that “actually being used in real world applications” is a smear and an appeal to popularity. The implication is that Haskell isn’t being used for anything “real”. This is an opinion that you absorbed passively, and the validity of which you haven’t bothered to check.

        I’ve already said that Scala’s main strength is interoperability with Java and the JVM.

        There is no such thing as a “true Haskeller”, and there’s no such thing as “Object-oriented” either.

  3. Hi,
    would you mind explaining, or pointing me to something that will, what is going on in this line:

    type K[A] = Id ~> Const[A]#Apply

    in particular, I don’t understand the right hand side of the expression Id ~> Const[A]#Apply

    Thanks

    • Channing,

      The type constructor called ~> is defined in the post. I’m using it infix for legibility. You can figure out what’s going on with that type expression by unpacking the definitions.

      By looking at the definition of ~>, you can see that Id ~> Const[A]#Apply is the type of objects with a method apply[B](f: Id[B]): Const[A]#Apply[B]. The return type of that method is equivalent to just A (by the definition of Const, and Id[X] is the same as X. So an object of type K[A] has a method apply[B](f: B): A. I’m omitting the by-name annotation here.

      So it represents a function whose domain type is free, with a codomain bound by the outer scope. This is exactly the return type of our const function, which takes a value x of some type A, and yields a value of type K[A]. The only implementation that makes sense is for that K[A]‘s apply method to always return that value x.

      I hope that helps.

      • Oh, and in case you’re not familiar with that syntax, #Apply[B] is a type member of Const. The type-expression Const[A]#Apply[B] is exactly equivalent to simply A. We do this to get a type constructor of the appropriate kind to pass to the ~> trait. Const[A] is a partially applied type constructor.

        The kinds of our type constructors are as follows (Haskell kind annotation):

        (~>) :: (* -> *) -> (* -> *) -> *
        Id :: * -> *
        Const :: * -> * -> *
        K :: * -> *

      • That does help, thanks. I need to do more studying though to fully understand this stuff.

  4. No real quibbles with anything you’re doing here. However, a more direct encoding is a little more transparent,

    trait LF[A] { def apply[B](b : => B) : A }
    def const[A](a : A) = new LF[A] { def apply[B](b : => B) = a }
    

    REPL session,

    scala> val x = const(7)
    x: java.lang.Object with LF[Int] = $anon$1@1154718
    
    scala> x("foo")
    res3: Int = 7
    
    scala> x(error("too strict"))
    res4: Int = 7
    
    • Actually, that doesn’t quite do the trick. This does,

      trait LF[A] { def apply[B](b : => B) : A }
      trait GF[F[_]] { def apply[A](a : A) : F[A] }
      def const = new GF[LF] {
        def apply[A](a : A) = new LF[A] {
          def apply[B](b : => B) = a
        }
      }
      

      but it’s moved quite a bit closer to yours, so my comment about greater transparency is pretty much moot.

  5. The following also fulfills the lazyness requirement:


    def const = new {
    def apply[A](a: => A) = new {
    def apply[B](b: => B) = a
    }
    }

    I am not sure whether it’s properly quantified though:


    scala> const _
    res20: () => java.lang.Object{def apply[A](a: => A): java.lang.Object{def apply[B](b: => B): A}} =

    Does not look too bad to me (at least no sign of Any and Nothing). Still, it does not feel quite right but I can’t put the finger on it… maybe due to the use of structural typing?

    Any hints? :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s