Page 1 of 1

From C# to F# and back again: lambdas and more.

#1 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Posted 23 November 2013 - 04:37 PM

*
POPULAR

As a language standard, C# has come a very long way since its creation, when it was little more than Java for .NET. In the spanning years, it has thrown off Java's OO shackles to embrace many paradigms and offer an amazing amount of programmer flexibility. ( Perhaps too much? ;) )

Here I'm ( hopefully ) going to show how C# can take you to the edge of functional programming and then do something uniquely its own.

Our task will be the ever popular: return the Roman Numeral string for given a number.

C# version 1:
string toRoman(int n) {
	String result = "";
	while (n > 0) {
		if (n >= 1000) {
			result += "M";
			n -= 1000;
		} else if (n >= 900) {
			result += "CM";
			n -= 900;
		} else if (n >= 500) {
			result += "D";
			n -= 500;
		} else if (n >= 400) {
			result += "CD";
			n -= 400;
		} else if (n >= 100) {
			result += "C";
			n -= 100;
		} else if (n >= 90) {
			result += "XC";
			n -= 90;
		} else if (n >= 50) {
			result += "L";
			n -= 50;
		} else if (n >= 40) {
			result += "XL";
			n -= 40;
		} else if (n >= 10) {
			result += "X";
			n -= 10;
		} else if (n >= 9) {
			result += "IX";
			n -= 9;
		} else if (n >= 5) {
			result += "V";
			n -= 5;
		} else if (n >= 4) {
			result += "IV";
			n -= 4;
		} else {
			result += "I";
			n -= 1;
		}
	}
	return result;
}



This code works and fulfills the stated goal. Most first year students will turn this in and be happy. A programmer of any experience should be cringing at the copy paste nature of it, though.

To sooth the C# programmer's soul, we refactor.

C# version 2:
string toRoman(int n) {
	int[] dec = new int[] { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
	string[] rom = new string[] { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
	String result = "";
	while (n > 0) {
		for(int i=0; i<dec.Length; i++) {
			int d = dec[i];
			if (n >= d) {
				result += rom[i];
				n -= d;
				break;
			}
		}
	}
	return result;
}



Ah, much better. This code is pretty good, except for two things. One is a potential optimization, discussed later. The other is... parallel arrays! While in something as simple as this, I suppose we can let them go. Still, I see parallel arrays as questionable design even here.

But, for the moment, let's forget C#. Fear not, we'll be returning to C# with a renewed passion. Now, for something completely different... F#.

What is F#? Isn't it that thing frustrated Scala programmers use in .NET? Isn't it only useful for math stuff? To quote:

Quote

F# is a succinct, expressive, and efficient functional and object-oriented language for Microsoft .NET that helps you write simple code to solve complex problems.
-- http://research.micr...rojects/fsharp/


I know that if you like C# you're probably thinking "who cares, I already use the best .NET language. I don't really need another." But what if looking at F# made you a better C# programmer? The could be crazy talk, but what if it's not?

So, our program above in F#:
let toRoman num =
  let dec = [|1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1|]
  let rom = [|"M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"|]
  let mutable n = num
  let mutable result = ""
  while n>0 do
    let mutable i = 0
    let mutable found = false
    while i<dec.Length && (not found) do
      let d = dec.[i]
      if n < d then i <- i + 1
      else
        result <- result + rom.[i]
        n <- n - d
        found <- true
  result



This is a near identical transcription. Well, as close as I could get; there' no break in F#. It does look a little awkward, though. In fact, while this was a reasonable C# program, it's kind of a terrible F# program. Just seeing the word "mutable" fills me with dread. Actually, "while" is also generally disturbing in F#. But, one thing at a time.

In F#, we define functions in functions as often as you define variables in C#. Perhaps more often. A logical chunk of code to separate out into to its own function would be the finding a match code. Let's do that now:
let toRoman num =
  let dec = [|1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1|]
  let rom = [|"M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"|]
  let getIndex n = 
    let mutable i = 0
    let mutable found = false
    while i<dec.Length && (not found) do
      let d = dec.[i]
      if n < d then i <- i + 1 else found <- true
    i

  let mutable n = num
  let mutable result = ""
  while n>0 do
    let i = getIndex n
    let d = dec.[i]
    result <- result + rom.[i]
    n <- n - d
  result



This is the exact same program as the prior one, but now we have the function getIndex to play with. Let's focus on cleaning up getIndex:
  let getIndex n = 
    let rec loop i = if n >= dec.[i] then i else loop (i+1)
    loop 0



In F#, recursion is your friend. One reason is that there are no mutables here. Just a simple recursive loop that finds our value. Note, there are built in functions that will do this for us, but this is rather nice.

We could bang away at this version a little more, but instead let's define and fix our initial problems.

First problem: parallel arrays suck. In F#, we like lists better than arrays; they're immutable. They aren't great for index lookups, but you often manage to avoid that. Also, in F# arbitrary structures are expressed with ease. So:
let toRoman num =
  let lookup = [(1000,  "M"); (900, "CM"); (500,  "D"); (400, "CD"); (100,  "C"); (90, "XC"); (50,  "L"); (40, "XL"); (10,  "X"); (9, "IX"); (5,  "V"); (4, "IV"); (1,  "I"); ]
  let getPair n = 
    let rec loop xs = 
      match xs with
      | x :: [] -> x
      | (dec,rom) :: ys when n >=dec -> (dec,rom)
      | _ :: ys  -> loop ys
    loop lookup

  let mutable n = num
  let mutable result = ""
  while n>0 do
    let (dec,rom) = getPair n
    result <- result + rom
    n <- n - dec
  result



Our two arrays have been replaced by a list of pairs. Our getIndex, with getPair, that basically does the same thing but returns both values.

We can prune down getPair with one of those built in functions now:
  let getPair n =
    let found = List.tryFind (fun (dec,_)->n>=dec) lookup
    found.Value



Now, let's kill our while mutables with that loop paradigm. A reasonably complete F# program would be:
let toRoman num =
  let lookup = [(1000,  "M"); (900, "CM"); (500,  "D"); (400, "CD"); (100,  "C"); (90, "XC"); (50,  "L"); (40, "XL"); (10,  "X"); (9, "IX"); (5,  "V"); (4, "IV"); (1,  "I"); ]
  let getPair n =
    let found = List.tryFind (fun (dec,_)->n>=dec) lookup
    found.Value
  let rec loop n result =
    if n=0 then result
    else 
      let (dec,rom) = getPair n
      loop (n - dec) (result + rom)
  loop num ""



Recall we had two problems with our C# program. One was parallel arrays. Check. The other, an optimization issue: should I always start at the top of my list and search down? The logic of this is that once I pass X I will never go back to C. Perhaps something like:
let toRoman num =
  let rec reduce (result,n) (dec,rom) =
    if n<dec then (result,n)
    else reduce ((result + rom),(n - dec)) (dec,rom)
  let rec loop state xs =
      match xs with
      | [] -> state
      | y :: ys  -> loop (reduce state y) ys
  [(1000,  "M"); (900, "CM"); (500,  "D"); (400, "CD"); (100,  "C"); (90, "XC"); (50,  "L"); (40, "XL"); (10,  "X"); (9, "IX"); (5,  "V"); (4, "IV"); (1,  "I"); ]
  |> loop ("", num)
  |> fst



Pay attention to reduce. This is where the action is at. We "loop" on a pair until exhausted and then leave, returning a new state. This kind of behavior is common enough in functional programming that there is a special method for it: the fold.

Here's our final F# program:
let toRoman num =
  let rec reduce (result,n) (dec,rom) = if n<dec then (result,n) else reduce ((result + rom),(n - dec)) (dec,rom)
  [(1000,  "M"); (900, "CM"); (500,  "D"); (400, "CD"); (100,  "C"); (90, "XC"); (50,  "L"); (40, "XL"); (10,  "X"); (9, "IX"); (5,  "V"); (4, "IV"); (1,  "I"); ]
  |> List.fold reduce ("",num)
  |> fst



If you got this far, you might be thinking "what the hell just happened?" That seems pretty common when you first start looking at functional programming coming from standard imperative fare. Also, if you don't know F# syntax, I've just thrown a whole lot at you. If you want to know how the above program do the voodoo it do, you'll probably have to find out more about F#. I really hope you do.

Right, enough with the F#, back to our old friend C#.

One thing F# showed us: it would be nice if we could just describe pairs are arbitrary data points. Well, in C#, you can. It's called a Tuple.

In a perfect C# world, you could do this:
Tuple<int, string> [] list = { (1000,"M"),(900,"CM"),(500,"D"),(400,"CD"),(100,"C"),(90,"XC"),(50,"L"),(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I") };



Alas, that's not currently an option and your compiler will choke.

You can do:
Tuple<int, string>[] list = { new Tuple<int, string>(1000, "M"), new Tuple<int, string>(900, "CM"), new Tuple<int, string>(500, "D"), new Tuple<int, string>(400, "CD"), new Tuple<int, string>(100, "C"), new Tuple<int, string>(90, "XC"), new Tuple<int, string>(50, "L"), new Tuple<int, string>(40, "XL"), new Tuple<int, string>(10, "X"), new Tuple<int, string>(9, "IX"), new Tuple<int, string>(5, "V"), new Tuple<int, string>(4, "IV"), new Tuple<int, string>(1, "I") };



But, let's be honest, that looks awful. If only we could make that Tuple init shorter. We could make a method for it, but it really only matters to this one method. In F# we would just make a function in a function... In C# we can make functions in functions! Really.
Func<int, string, Tuple<int, string>> p = (d,r) => new Tuple<int, string>(d,r);
var list = new List<Tuple<int, string>> { p(1000, "M"), p(900, "CM"), p(500, "D"), p(400, "CD"), p(100, "C"), p(90, "XC"), p(50, "L"), p(40, "XL"), p(10, "X"), p(9, "IX"), p(5, "V"), p(4, "IV"), p(1, "I") };



Nice, huh? We're getting into the inference mood with the var, too. So, as we once moved C# directly to F#, let's move F# directly to C#.
string toRoman(int n) {
"L"), new Tuple<int, string>(40, "XL"), new Tuple<int, string>(10, "X"), new Tuple<int, string>(9, "IX"), new Tuple<int, string>(5, "V"), new Tuple<int, string>(4, "IV"), new Tuple<int, string>(1, "I") };
	Func<int, string, Tuple<int, string>> p = (d,r) => new Tuple<int, string>(d,r);
	var list = new List<Tuple<int, string>> { p(1000, "M"), p(900, "CM"), p(500, "D"), p(400, "CD"), p(100, "C"), p(90, "XC"), p(50, "L"), p(40, "XL"), p(10, "X"), p(9, "IX"), p(5, "V"), p(4, "IV"), p(1, "I") };
	Func<Tuple<string, int>, Tuple<int, string>, Tuple<string, int>> reduce = (state, decRom) => {
		var result = state.Item1;
		var num = state.Item2;
		var d = decRom.Item1;
		while (n >= d) {
				result += decRom.Item2;
				num -= d;
			}
		return new Tuple<string,int>(result, num);
	};
	var resultPair = new Tuple<string,int>("", n);
	list.ForEach((x)=> resultPair = reduce(resultPair, x));
	return resultPair.Item1;
}



As before, when we did it the other way around, it looks awful but it works. There is a paradigm clash here. F#, being functional, embraces the immutable. In C#, immutable state makes for inefficient code. Perhaps bringing F# code into C# was a bad idea?

Not at all! At the very least, we're thinking about the problem differently now, which is good. What if we still think of functions and tuples, but also embrace our mutable state? Consider:
string toRoman(int n) {
	string result = "";
	Func<int, string, Tuple<int, string>> p = (d, r) => new Tuple<int, string>(d, r);
	new List<Tuple<int, string>> { 
		p(1000, "M"), p(900, "CM"), p(500, "D"), p(400, "CD"), p(100, "C"), p(90, "XC"), p(50, "L"), p(40, "XL"), p(10, "X"), p(9, "IX"), p(5, "V"), p(4, "IV"), p(1, "I") 
	}.ForEach((decRom)=> {
		var d = decRom.Item1;
		while (n >= d) {
			result += decRom.Item2;
			n -= d;
		}
	});
	return result;
}



That's rather neat, but still kind of F#ish. And, really, seems messy in C#. Wait. What if we just implemented the reduce and took advantage of the closure and mutable state?

Final C# version:
string toRoman(int n) {
	string result = "";
	Action<int, string> p = (d, rom) => { while (n >= d) { result += rom; n -= d; } };
	p(1000, "M"); p(900, "CM"); p(500, "D"); p(400, "CD"); p(100, "C"); p(90, "XC"); p(50, "L"); p(40, "XL"); p(10, "X"); p(9, "IX"); p(5, "V"); p(4, "IV"); p(1, "I");
	return result;
}



That seems nice. It's simple C#, with functional programming awareness but not blind adherence.

I hope this got you thinking about different ways to solve problems in C#. Or even taking a look at the somewhat different beastie, F#.

Happy programming.

Is This A Good Question/Topic? 9
  • +

Replies To: From C# to F# and back again: lambdas and more.

#2 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2257
  • View blog
  • Posts: 9,449
  • Joined: 29-May 08

Posted 23 November 2013 - 07:09 PM

baavgai you disappoint me, you could have at least used a recursive lambda function, instead of the while loop as well as using the inbuilt reduce function (ie Aggregate).

So here is the VB.net 2LoC implementation
Spoiler

Was This Post Helpful? 0
  • +
  • -

#3 lucky3  Icon User is offline

  • Friend lucky3 As IHelpable
  • member icon

Reputation: 231
  • View blog
  • Posts: 765
  • Joined: 19-October 11

Posted 24 November 2013 - 02:38 AM

I tested both solutions (edit C# and VB.NET), and it seems like C# was 8 - 10 times faster.

Edit: here's the solution with all 3 projects (F#, C#, and VB.NET): Attached File  DecimalToRoman.zip (555.05K)
Number of downloads: 83

This post has been edited by lucky3: 24 November 2013 - 04:06 AM

Was This Post Helpful? 0
  • +
  • -

#4 code_m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 202
  • Joined: 21-April 09

Posted 24 November 2013 - 03:06 AM

As I skimmed through this I couldn't help but think, "this seems like an awful lot like a dictionary situation". That's the Python talking in me. Then I stopped to think how I'd actually code up a dictionary solution. The answer is that you can, but it would suck because order matters here.

I really thank you for this contribution baavgai. You actually made a strong argument for functional programming with a rather contrived example, which takes some real skill.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Posted 24 November 2013 - 04:06 AM

Well, this is about C#... AdamSpeight2008 you disappoint me by always sticking VB.NET in places it has no business being. And, not reading TFA. :P

Your solution relies on a syntax in a different language and even then has to use an import alias so that it's almost readable. I also question the dictionary.

In F#, TFA showed a nice clean fold as the final solution. It works well in that language. Could we use fold's "special" cousin, Enumerable.Aggregate, in C#? Sure. However, one of the points put out was the inherent ungainliness of Tuple syntax in C#.

Finding a clean solution in C# that couldn't be done better in F# was clearly an implicit goal here. Trying to use an Aggregate function dramatically fails that goal.
Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2257
  • View blog
  • Posts: 9,449
  • Joined: 29-May 08

Posted 24 November 2013 - 09:11 AM

Purely Recursive Version
Spoiler


Which I think is the following in F#
let ToRoman x =
  let rec f(n,d,result,v,s) = match d with
                           | _ when d > 12    -> result
                           | _ when n >= v[d] -> f(n-v[d], d, result & s[d], v,s)
                           | _                -> f(n,d+1,result,v,s)
  f(x,0,"", [|1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1|],[|"M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"|])



This post has been edited by AdamSpeight2008: 24 November 2013 - 09:51 AM

Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Posted 24 November 2013 - 12:08 PM

Hmm... thanks for the F# code. I'd still iterate over a list of pairs, rather than parallel arrays. However, if you really did want to do it all in your function like that:
let ToRoman x =
  let v = [|1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1|]
  let s = [|"M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"|]
  let rec f n result d = 
    if d >= v.Length then result
    elif n >= v.[d] then f (n-v.[d]) (result + s.[d]) d
    else f n result (d+1)
  f x "" 0



Or, to remove your check for d:
let ToRoman x =
  let v = [|1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1|]
  let s = [|"M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"|]
  let rec f (n,result) d = 
    if n >= v.[d] then f (n-v.[d], result + s.[d]) d
    else (n,result)
  [ 0 .. v.Length-1 ] |> List.fold f (x,"") |> snd



Note the little snd at the end there. That turns (_,result) into result. Tuple pairs are so very common, that the functions fst and snd exist to pluck off the first or second value respectively.

Now, instead of the arrays, if we passed the v.[d], s.[d] pair to the function...
let ToRoman x =
  let rec f (n,result) (v,s) = 
    if n >= v then f (n-v, result + s) (v,s)
    else (n,result)
  ["M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"]
  |> List.zip [1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1]
  |> List.fold f (x,"")
  |> snd



We're getting rather close to the final version from the article.

Note:
["M"; "CM"; "D"; "CD"; "C"; "XC"; "L"; "XL"; "X"; "IX"; "V"; "IV"; "I"]
|> List.zip [1000; 900; 500; 400; 100; 90; 50; 40; 10; 9; 5; 4; 1]


results:
val it : (int * string) list =
  [(1000, "M"); (900, "CM"); (500, "D"); (400, "CD"); (100, "C"); (90, "XC");
   (50, "L"); (40, "XL"); (10, "X"); (9, "IX"); (5, "V"); (4, "IV"); (1, "I")]


Was This Post Helpful? 1
  • +
  • -

#8 boxed  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 06-November 13

Posted 26 November 2013 - 01:20 AM

Great tutorial! I really am inspired to look into F# and scala now. I've always just kind of ignored F#'s existence, but now that I've seen it in action I am really curious to see what I can do with it.

If anyone else is as interested as I am I just found what appears to be a great resource (with a pretty slick design!): http://www.tryfsharp.org/Learn
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1