DEV Community

JavaScript Joel
JavaScript Joel

Posted on

5

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (19)

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 •

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 •

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.