JavaScript Joel

Posted on Nov 1, 2018

Challenge: Parse simple and complex types from a string

#challenge #javascript

The Challenge

Create a function to parse to parse the signatures into an array of types. There are two types one is simple like Apple, the other is complex like (Banana -> Grape). There could be any number of Arrows, even in the complex type.

"Apple" //=> ["Apple"]
"Apple -> Banana -> Grape" //=> ["Apple", "Banana", "Grape"]
"(Apple -> Banana) -> Grape" //=> ["(Apple -> Banana)", "Grape"]
"Apple -> (Banana -> Grape)" //=> ["Apple", "(Banana -> Grape)"]
"Apple -> (Banana -> Grape) -> Cherry" //=> ["Apple", "(Banana -> Grape)", "Cherry"]

function parseSignature(signature) {
  /* insert code here */
}

parseSignature("Apple -> (Banana -> Grape) -> Cherry")
//=> ["Apple", "(Banana -> Grape)",  "Cherry"]

Fun tip: This has a real world use case as it is part of the hindley milner signature pattern used by Haskell or the Fantasy Land specification.

Top comments (19)

Guillaume Martigny • Nov 2 '18 • Edited

I have no idea of the purpose of this, but I never refuse a fun challenge :D

I use the proximity of your syntaxe with JSON to parse more easily.

function parseSignature (str) {
    const reg = /\(.+\)|( ?-> ?)/g;
    return JSON.parse(`["${str.replace(reg, (match, capture) => capture ? `", "` : match)}"]`);
}

parseSignature("Apple -> (Banana -> Grape) -> Cherry");

runkit.com/gmartigny/5bdc0d1932ccd...

Works with inconsistent white-space but not with deeper nested complex types.

JavaScript Joel • Nov 2 '18

I hate regex. It's so easy to write and so hard to read. I tried to not use regex in my solution, but it was just easier.

Great solution, I believe yours is even easier to read than mine!

Guillaume Martigny • Nov 2 '18 • Edited

I love them for the exact same reasons =D

Kasey Speakman • Nov 2 '18

I am half-tempted to peak into the F# compiler source code, since it uses these exact type signatures and the Hindley-Milner type system. But it generates a syntax tree as the result. So the inner (Banana -> Grape) would become another expression tree.

JavaScript Joel • Nov 2 '18

Ya I'm sure they make an AST. That would have been too complex for this challenge. You are more than welcome to show is how it's done though! ;)

Kasey Speakman • Nov 2 '18

Oh, not me. :o) I guess just pointing out another practical application. And the F# compiler is bootstrapped (written in F#).

JavaScript Joel • Nov 2 '18

I always love when a compiler is written with that language. Eat your own dog food!

Avalander • Nov 2 '18

What is the output supposed to be? This doesn't look like valid javascript.

["Apple" -> "(Banana -> Grape) -> Cherry"]

JavaScript Joel • Nov 2 '18

I may have been typing directly into dev.to. lemme fix :D

Avalander • Nov 2 '18

It makes much more sense now :)

JavaScript Joel • Nov 2 '18

Thanks for catching that. Sometimes I gets the dumbs. :D

Avalander • Nov 3 '18

Better here than in production systems :P

JavaScript Joel • Nov 3 '18

That gives me a great idea. CI/CD system for blog posts! Haha

JavaScript Joel • Nov 1 '18

My solution using recursion:

const parse = (signature, values = []) => {
  if (!signature) {
    return values
  }
  const next = /^\([^)]+\)|\w+/.exec(signature)[0]
  const nextSignature = signature.substr(next.length + 4)
  return parse(nextSignature, [...values, next])
}

note: this solution doesn't account for inconsistent whitespace.

JavaScript Joel • Nov 1 '18

This one takes white space into consideration:

const parse = (signature, values = []) => {
  if (!signature) {
    return values
  }
  const next = /^\([^)]+\)|\w+/.exec(signature.trim())[0]
  const nextArrow = signature.indexOf('->', next.length)
  const trimAt = nextArrow === -1 ? next.length : nextArrow + 2
  const nextSignature = signature.substr(trimAt).trim()
  return parse(nextSignature, [...values, next])
}