Exploring ML-Style Modular Programming in Scala | Hacker News Reader

Exploring ML-Style Modular Programming in Scala

github.com

72 pointsyawaramin10 comments

These are not equivalent:

    /* signature INTMAP =                       */ import scala.language.higherKinds
    /*   sig                                    */
    /*     exception NotFound                   */ trait IntMap[A] {
    /*     type 'a t                            */   type NotFound
    /*                                          */   type T[_]
    /*     val empty: 'a t                      */
    /*     val get: int -> 'a t -> 'a           */   val empty: T[A]
    /*     val insert: int * 'a -> 'a t -> 'a t */   def get(i: Int)(x: T[A]): A
    /*   end;                                   */   def insert(k: Int, v: A)(x: T[A]): T[A]
    /*                                          */ }

What you want is

    /* signature INTMAP =                       */ import scala.language.higherKinds
    /*   sig                                    */
    /*     exception NotFound                   */ trait IntMap {
    /*     type 'a t                            */   type NotFound
    /*                                          */   type T[_]
    /*     val empty: 'a t                      */
    /*     val get: int -> 'a t -> 'a           */   def empty[A]: T[A]
    /*     val insert: int * 'a -> 'a t -> 'a t */   def get[A](i: Int)(x: T[A]): A
    /*   end;                                   */   def insert[A](k: Int, v: A)(x: T[A]): T[A]
    /*                                          */ }

Update: To elaborate further, the problem with the trait as defined in the original post is that it has moved type quantification outside of the functions/methods. A ML module satisfying the signature INTMAP could create instances of t for any 'a, while an instance of IntMap[A] would be limited to instances of specific to A. At this point, because T[_] depends on A, there is no reason for it to have a higher kind.

In case someone else is having difficulties finding the differences: the second Scala version moved the "[A]" from besides "trait IntMap" and put it on every method definition.

Yes, you are right that in a literal sense the port is not exact. Primarily, I wanted to have the freedom to use that trait parameter type as a building block for other types if I wished to.

See e.g. my 'Graph' implementation.[1] In it, I pass in the type of the vertex as a trait type parameter 'A'. In the 'Graph[A]' trait I also have an abstract type 'E' to represent the edge. 'E' is used in a couple of the methods.

Later I define a more specialised 'MapGraph' trait and refine the type 'E' to be a pair of 'A's. I couldn't have done this if I wasn't passing in the 'A' as a type parameter.

This leads me to believe that all things considered you get more flexibility from always using type parameters, not to mention somewhat better signal-to-noise in the code (getting rid of all the method type params), and also being able to use 'val's.

[1] https://github.com/yawaramin/scala-modules/blob/8df0ec516629...

It isn't about freedom. If you are going to parametrize the entire trait, there is no longer any point to giving T a higher kind. As such it just adds noise and is bad style.

Actually I agree with you. In fact if you look at the 'UnbalancedSet' functor I define the type 'T' to not take any parameters. In the case of 'IntMap' it just happened that I missed that. So thanks for pointing it out. I'll make the necessary updates.

And using "def" is actually considered better Scala style in situations like this, exactly because it is more flexible. You can override a "def" with a "val" but not the other way around.

I'm happy to answer questions about the design decisions if anyone is curious.

Nice post! I think your encoding of functors could be replaced by:

  object Module {
    private class MyUnbalancedSet[A](O: Ordered[A]) extends MySet[A] {
      ... body as in your post
    }
    def UnbalancedSet[A](O: Ordered[A]): MySet[A] = new MyUnbalancedSet[A](0)
  }

Which looks more like "normal" Scala but still offers the same amount of abstraction.

Thanks!

Yes, you're right that we can use a class here and instantiate an object of the class. I thought I would skip the intermediate step because all I care about is the upcast type, MySet[A], and not the actual derived type.

But it's very much a matter of preference!

Awesome work! Thank you for sharing.

Reply on news.ycombinator.com