DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

JavaScript Joel
JavaScript Joel

Posted on

Challenge: Parse simple and complex types from a string

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 (22)

Collapse
 
gmartigny profile image
Guillaume Martigny • Edited on

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

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 on

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

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

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

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

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

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

Collapse
 
joelnet profile image
JavaScript Joel

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

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

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

 
joelnet profile image
JavaScript Joel

I can definitely see the power in it!

Collapse
 
joelnet profile image
JavaScript Joel

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.

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: