Adam Saleh's notes

Why would I want to attempt to create a monoid-like thing for records? Well, the reasoning is three-fold. First, when playing around with Purescript, I often have these large record definitions and then I have to initialize them. I would much rather just say "This record has all fields empty, figure it out." Second, these large records are often the heart of some state, that I update all the time, and I would much rather just do

updateFunction state update = appendRecord state update

than

updateFunction state update = state {a = state.a <> update.a ...}

Third, because Record is kind-of like a row-polymorphic Tuple, and Tuple has a Monoid instance, it should mean that creating a something similar for Records should be quite an easy puzzle to solve :-)

Because I wouldn't be implementing a proper instance (still not entirely sure that is possible just yet in Purescript, would I need overlapping typeclass instance support to do that?), and just the two hepler functions, that more or less try to convey the implementation of the instance in spirit, I start with the memptyRecord implementation.

It turns out it is easier than the appendRecord one.

For the class itself, I just need the RowList and output row.

class MemptyRecord rl row | rl -> row
  where
    memptyRecordImpl :: RLProxy rl -> Record row

And Nil case will be just an empty record.

instance memptyRecordNil :: MemptyRecord Nil () where
  memptyRecordImpl _ = {}

In the Cons instance, I just iterate over the RowList, on constraint that every there is a Monoid in every row and insert a mempty for that row.

instance memptyRecordCons ::
  ( IsSymbol name
  , Monoid t
  , MemptyRecord tail tailRow
  , RowLacks name tailRow
  , RowCons name t tailRow row
  ) => MemptyRecord (Cons name t tail) row where
  memptyRecordImpl _ =
     insert namep mempty rest
   where
     namep = SProxy :: SProxy name
     tailp = RLProxy :: RLProxy tail
     rest = memptyRecordImpl tailp

To tie it all together, I wrap the memptyRecordImpl in memptyRecord function, that makes the compiler to figure out the row-list for me.

memptyRecord :: forall rl row . RowToList row rl
   => MemptyRecord rl row
   => Record row
memptyRecord = memptyRecordImpl (RLProxy :: RLProxy rl)

In the end, this was fairly simple and I managed to solve the first problem, because now

{a : "", b : []}  == memptyRecord :: {a :: String, b :: Array Int}

This of-course doesn't really work on nested records, but I think it is still an improvement.

For the sake of simplicity I will just dump the entirety of my first attempt at this. It actually worked and

~appendRecord {a: "1", b: [2], c: "3"} {a: "a", b: [4], c: "c"} == {a: "1a", b: [2,4], c: "3c"}~

It looked like this:

+class SemigroupRecord rl row row'
  | rl -> row row'
  where
    appendRecordImpl :: RLProxy rl -> Record row -> Record row -> Record row'

instance appendRecordCons ::
  ( IsSymbol name
  , Semigroup ty
  , RowCons name ty trash row
  , SemigroupRecord tail row tailRow'
  , RowLacks name tailRow'
  , RowCons name ty tailRow' row'
  ) => SemigroupRecord (Cons name ty tail) row row' where
  appendRecordImpl _ a b =
      insert namep (valA <> valB) rest
    where
      namep = SProxy :: SProxy name
      valA = get namep a
      valB = get namep b
      rest = appendRecordImpl (RLProxy :: RLProxy tail) a b

 instance appendRecordNil :: SemigroupRecord Nil row () where
   appendRecordImpl _ _ _ = {}

This implementation required, that when I use appendRecord, both records have the same keys, and that didn't really fit the record-updating semantics I had in mind. If I had a large record to update, I don't really want to specify all of the keys, I just want to specify the keys that I want to update.

With this in mind, I went to #purescript on functionalprogramming.slack.com and started asking, if anybody knows how to implement outer join of two records. If I knew, that you could somehow merge {a: 1, b:"b"} with {b:"b", c:"c"} to get {a:1, b:"b", c:"c" }, changing it do {a:1, b:"bb", c:"c" } should be simple, right?

Unfortunately, it turns out, doing outer-join with RowLists seems to be hard, mostly ending the conversation about my outer-join ideas with the question "So, why do you actually want to do that?" After I described the use-case for updating records, @monoidmusician suggested to change the appendRecord function to allow the second record be a subset of first one. This means that the appendRecordImpl type becomes

RLProxy rl -> Record big -> Record small -> Record big

This makes everything simpler, and @paluh even sent me an implementation in gist.

First interesting thing I have noticed, that with the new class definition, I don't actually need any functional dependencies.

class AppendSubrecordImpl rl bigger smaller where
  appendSubrecordImpl :: RLProxy rl -> Record bigger -> Record smaller -> Record bigger

Because the iteration happens over the smaller record, in nil case I just return the bigger record.

instance appendSubrecordNil :: AppendSubrecordImpl Nil bigger smaller where
  appendSubrecordImpl _ b s = b

And because I know that the result will be the Row bigger, I don't actually need the machinery to build up the output row.

instance appendSubrecordCons ::
  ( IsSymbol name
  , RowCons name t trash smaller
  , RowCons name t trash' bigger
  , Semigroup t
  , AppendSubrecordImpl tail bigger smaller
  ) => AppendSubrecordImpl (Cons name t tail) bigger smaller where
    appendSubrecordImpl _ bigger smaller = modify key modifier rest
      where
	key = SProxy :: SProxy name
	modifier v = v <> get key smaller
	rest = appendSubrecordImpl (RLProxy ∷ RLProxy tail) bigger smaller

One day, I maybe will be bugging @jusrin00 to merge this PR as well :-)

Now that I have what I wanted, I started thinking if this still can be considered a monoid. If we would have one well defined type, that would go through all of our functions, a single closed row-type, I don't think there would be a problem with any of the monoid laws and fairly easily we could do:

newtype User = User {name: Maybe String, surname: Maybe String}

instance semigroupUser :: Semigroup User where
  append (User a) (User b) = User (appendSubrecord a b)

instance monoidUser :: Monoid User where
  mempty = User {name : Nothing, surname: Nothing}

But I am not really sure what does the fact, that we relaxed the second row to be a sub-set of the first actually mean. It seems that there might be some foot-guns hidden in there. For example, because I only iterate through the smaller row RowList, the first row could contain keys that aren't Semigroups. Is that a bug, or a feature? I am not sure yet, but I definitely can't claim that {a:String, b:MyNotASemigroup} is a Semigroup, even though I could appendSubrecord {a:"Adam", b:Test} {a: " Saleh"}. The compiler would still catch, if I try to append the wrong key. On the whole, this starts to resemble more of a relational algebra, than the group-hierarchy. I wonder how would rest of the instances from Tuple look like, if I ported them over to Record. Maybe I will try to take a stab at Row-polymorphic curry and uncurry, that might be fun.

After a few stabs at this, I have decided I should write about my experience with Purescript's meta-programming capabilities. Purescript is a nice small language, inspired by Haskell, that mostly compiles to Javascript. I know there are some other backends, like Erlang, or C++, but I haven't tried those yet.

It has a really nice book to guide you through the language, given you have at least some limited Haskell experience. My experience with Haskell so far is roughly a half-semester at a university-course (where the other half was concerned with Prolog), and a few never-published toy-projects.

It even has several interesting features that you wouldn't find in Haskell (unless you enabled some extensions). The feature I have mostly played around is concerned with row-types.

Read more…