Das Countdown Problem
Das Countdown Problem lautet wie folgt: Gegeben seien eine Folge positiver ganzer Zahlen, die Quellzahlen, und eine positive ganze Zahl, die Zielzahl. Gesucht wird ein arithmetischer Ausdruck, in dem jede der Quellzahlen höchstens einmal auftritt und der als Ergebnis die Zielzahl liefert. Als Operatoren können in dem Ausdruck +, -, * und / verwendet werden, wobei jedes Zwischenergebnis ebenfalls eine positive ganze Zahl sein muss. Zum Beispiel löst für die Quellzahlen [1; 3; 7; 10; 25; 50] und die Zielzahl 765 der Ausdruck (1 + 50) * (25 - 10) das Problem. [Referenz: http://www.mathematik.uni-marburg.de/~loogen/Lehre/ws06/Konzepte/Uebungen/u6.pdf]
Unter diesem Link kann die Lösung in C# heruntergeladen werden.
Die C#-Lösung unterscheidet sich zu der Haskell-Lösung vorallem dadurch, dass in C# objektorientierte Konstrukte eingeführt wurden. Nachfolgend eine Auflistung der Haskell-Features welche nur erschwert in C# abgebildet werden konnten
- Rekursive Typen wurden als Klassenhierarchien abgebildet. Folgender Haskell-Code
data Expr = Val Int App Op Expr Expr
wurde in C# zupublic interface IExpression{}
public struct Value : IExpression
{
public Value(int value){}
}
public abstract class Operation : IExpression
{
protected Operation(IExpression l, IExpression r){}
}
public class Add : Operation
{
public Add(IExpression l, IExpression r) : base(l, r) { }
}
public class Sub : Operation
{
public Sub(IExpression l, IExpression r) : base(l, r) { }
}
public class Mul : Operation
{
public Mul(IExpression l, IExpression r) : base(l, r) { }
}
public class Div : Operation
{
public Div(IExpression l, IExpression r) : base(l, r) { }
}
Während der Haskellausdruck an Produktionsregeln erinneren und somit eine internal DSL bilden, fehlt in C# 3.0 eine solche Möglichkeit. In C# wurde der dieser Ausdruck als ein Expression-Tree abgebildet. Die Anwendung des rekursiven Typs sieht in Haskell wie folgt aus:evaluate( App Add( Val 2 ) ( Val 3 ))
während in C# der Expression-Tree wie folgt instanziert und evaluiert würde:new Add(new Value(2), new Value(3)).Eval();
Das Problem an der objektorientierten Lösung in C# ist, dass in der Anwendung immer Objekte erzeugt werden müssen. Dies verlangt das Schlüsselwort 'new' welches im Gegensatz zum Haskell-Beispiel, den Ausdruck verschleiert. Auch ein FluentInterface bringt in diesem Fall nichts, da damit keine Ausdrücke verschachtelt werden könnten. - Lazy-Evaluation wird für die Lösung des Countdown-Problem benötigt, ansonsten alle Lösungskandidaten am Anfang der Berechnung in den Speicher geladen werden müssten. Lazy-Evaluation ermöglicht die Berechnungsfunktionen so zu kaskadieren, dass nur immer die gerade benötigten Resultat ermittelt werden und dass nicht mehr benötigte Zwischenresultat sofort im Speicher freigegeben werden können.
Während in Haskell diesbezüglich keine Vorkehrungen nötig sind muss in C# explizit jede Berechnung und Berechnungsschlaufe über IEnumerable erfolgen. Verwendet man LINQ und Extension-Methods so können alle Haskell-Lösungen in die entsprechende LINQ-Lösung übersetzt werden. Aus der Haskell-Funktion
solutions :: [Int] -> Int -> [Expr]
solutions ns n = [e ns' <- choises ns,
e <- exprs ns',
evaluate e == [n]]
wird in C# 3.0 zupublic static IEnumerable<IExpression> GetSolutions(IEnumerable<int> values, int result)
{
return values.Choises().SelectMany(choise => choise.Exprs()).Where( exp => exp.IsValid() && exp.Eval() == result);
} - Pattern-Matching ist ein Konstrukt um die Komplexität pro Funktion oder Methode zu reduzieren. Die Haskell-Funktion
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x)(perms xs))
behandelt den Fall der leeren Liste und den Fall der nicht leeren Liste in zwei getrennten Funktionsimplementionen. Da C# Pattern-Matching nicht kennt müssen dort die beiden Fälle in der Methodenimplementation durch eine if-Anweisung explizit behandelt werden:public static IEnumerable<IEnumerable<int>> Perms(this IEnumerable<int> list)
{
if (list.Count() == 0)
{
return new int[][] { new int[] { } };
}
else
{
return list.Skip(1).Perms().SelectMany(subList => subList.Interleave(list.First()));
}
} - Listen sind in Haskell tief in die Sprache eingebettet. Folgendes Beispiel
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x)(perms xs))
ist im starken Kontrast mit C# 3.0:public static IEnumerable<IEnumerable<int>> Perms(this IEnumerable<int> list)
{
if (list.Count() == 0)
{
return new int[][] { new int[] { } };
}
else
{
return list.Skip(1).Perms().SelectMany(subList => subList.Interleave(list.First()));
}
}
Folgendes kann beobachtet werden:
- x in Haskell entspricht list.First() in C#
- xs in Haskell entspricht list.Skip(1) in C#
Listen haben unter C# einen langen Leidensweg hinter sich:
- .NET 1.0 kennt untypisierten Listen aus System.Collections
- .NET 2.0 unterstützte typisierte Listen aus System.Collections.Generic
- ab Visual Studio 2008 wird nun LINQ eingeführt
LINQ ist grossartig doch leider kommt es sehr spät. Eine grosse Erneuerung ist die Erkenntnis dass man anstellen von Listen nun mit IEnumerable's arbeitet. Während Listen (z.B List) in .NET die Eigenschaft der Eager Evaluation haben, wird mit IEnumerable Lazy-Evaluation erreicht (siehe auch oben). Leider muss man sich in Zukunft immer explizit für 'Eager' oder 'Lazy'-Evaluation entscheiden und es wird immer einen konzeptionellen Bruch zwischen den beiden Ansätzen geben. Die Verwendung von IEnumerable (Lazy-Evaluation) ist auf jeden Fall der Verwendung von IList,ICollection usw. (Eager-Evaluation) vorzuziehen.
Mit C# 3.0 lassen sich einige Konzepte aus der funktionalen Programmierung anwenden. Diese Konzepte sind allerdings in einer funktionalen Sprache wie Haskell eleganter umgesetzt. Dagegen steht im Kontrast dass in Haksell objektorientierte Konzepte fehlen, welche vorallem für den Bau von grossen und komplexen Softwaresystemen benötigt werden (z.B Abstrakte Datentypen)
Posts
