[Haskell-cafe] Roman Numeral Problem
kusimari share
kusimari.share at gmail.com
Tue Jun 25 21:08:59 CEST 2013
Coincidence. I blogged about this today
http://kusimari.blogspot.in/2013/06/roman-numerals-using-parser-combinators.html.
I can share the haskelish python code offline, assuming this is not needed
to pass the thoughtworks code submission.
It more or less resembles what Richard has written.
-Santhosh
On Mon, Jun 24, 2013 at 12:54 PM, Richard A. O'Keefe <ok at cs.otago.ac.nz>wrote:
> An important question here is whether you want to notice
> when a Roman numeral is invalid, e.g., iix, or not.
>
> From a parsing point of view context-free grammars are not
> ideal. We have the patterns
> i{1,3} | iv | vi{1,3} | ix units
> x{1,3} | xl | lx{1,3} | xc tens
> c{1,3} | cd | dc{1,3} | cm hundreds
> m{1,3} | mↁ | ↁm{1,3} | mↂ thousands
> so we want to write a grammar rule like
>
>
> roman(N) -->
> group('m', 'ↁ', 'ↂ', M),
> group('c', 'd', 'm', C),
> group('x', 'l', 'c', X),
> group('i', 'v', 'x', I),
> {N is M*1000 + C*100 + X*10 + I}.
>
> group(U, F, T, N) -->
> ( [U,T] -> {N = 9}
> ; [U,F] -> {N = 4}
> ; [U,U,U] -> {N = 3}
> ; [U,U] -> {N = 2}
> ; [U] -> {N = 1}
> ; [F,U,U,U] -> {N = 8}
> ; [F,U,U] -> {N = 7}
> ; [F,U] -> {N = 6}
> ; [F] -> {N = 5}
> ).
>
> using DCG notation. This is not context-free. It is an
> attribute grammar with attributes passed down the parse
> tree (U, F, T) and passed up the parse tree (N).
>
> Parser combinators are the easy way to do this in Haskell;
> see 'parsec' or any number of parser combinator tutorials.
>
> For that matter, it's pretty trivial to do this particular
> one with plain code that pretty much mirrors the structure
> shown above. Just write something that takes (as many
> arguments as you want) then a list of characters coming in
> and returns a pair with a computed answer and the remaining
> characters. But wait! That _is_ a parser combinator!
> I guess parser combinators can't be that hard after all (:-).
>
> Good luck finding the five thousand character (ↁ) or the
> ten thousand character (ↂ) or any of the other Unicode
> "I'm not a letter, no, honest, I'm really not, I'm a
> Roman numeral" characters on your keyboard.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130626/4e20001c/attachment.htm>
More information about the Haskell-Cafe
mailing list