DEV Community

loading...

Challenge: Parse simple and complex types from a string

JavaScript Joel
Cofounded Host Collective (DiscountASP.net). Cofounded Player Axis (Social Gaming). Computer Scientist and Technology Evangelist with 20+ years of experience with JavaScript!
・1 min read

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.

Discussion (22)

Collapse
gmartigny profile image
Guillaume Martigny • 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.

Collapse
joelnet profile image
JavaScript Joel Author

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!

Collapse
gmartigny profile image
Guillaume Martigny • Edited

I love them for the exact same reasons =D

Collapse
kspeakman profile image
Kasey Speakman

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.

Collapse
joelnet profile image
JavaScript Joel Author

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! ;)

Collapse
kspeakman profile image
Kasey Speakman

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

Thread Thread
joelnet profile image
JavaScript Joel Author

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

Collapse
avalander profile image
Avalander

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

["Apple" -> "(Banana -> Grape) -> Cherry"]
Collapse
joelnet profile image
JavaScript Joel Author

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

Collapse
avalander profile image
Avalander

It makes much more sense now :)

Thread Thread
joelnet profile image
JavaScript Joel Author

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

Thread Thread
avalander profile image
Avalander

Better here than in production systems :P

Thread Thread
joelnet profile image
JavaScript Joel Author

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

Collapse
joelnet profile image
JavaScript Joel Author

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.

Collapse
joelnet profile image
JavaScript Joel Author

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])
}
Collapse
jochemstoel profile image
Jochem Stoel

It is highly ironic that the real world use case is somewhere in Fantasy Land.

Collapse
joelnet profile image
JavaScript Joel Author

lol. Trying not to laugh out loud in meeting. Thanks for that one!

joelnet profile image
JavaScript Joel Author

I can definitely see the power in it!

Collapse
joelnet profile image
JavaScript Joel Author

I have not dug into Elixir at all. This block of code makes me curious. I like how you defined each parse step is.

Gonna have to add it to my list of languages to learn.

Thanks for sharing.