[Haskell-cafe] Roman Numeral Problem

[kusimari share]

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>