Skip to content

Instantly share code, notes, and snippets.

@noblethrasher
Created December 16, 2012 06:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save noblethrasher/4303853 to your computer and use it in GitHub Desktop.
Save noblethrasher/4303853 to your computer and use it in GitHub Desktop.
C# vs ML
abstract class ListPair<T>
where T : IComparable<T>
{
static IEnumerable<T> empty = new T[0];
public abstract IEnumerable<T> Merge();
protected virtual LeftList Left { get; private set; }
protected virtual RightList Right { get; private set; }
public static ListPair<T> Create(LeftList left, RightList right)
{
foreach (var x in left)
foreach (var y in right)
return new BothNonEmpty () { Left = left, Right = right };
foreach (var x in left)
return OneEmpty.Create (left);
return OneEmpty.Create (right);
}
public abstract class TaggedList : IEnumerable<T>
{
IEnumerable<T> xs;
public TaggedList(IEnumerable<T> xs)
{
this.xs = xs;
}
public IEnumerator<T> GetEnumerator()
{
return xs.GetEnumerator ();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator ();
}
}
public sealed class LeftList : TaggedList
{
public LeftList(IEnumerable<T> xs) : base (xs) { }
}
public sealed class RightList : TaggedList
{
public RightList(IEnumerable<T> xs) : base (xs) { }
}
sealed class BothNonEmpty : ListPair<T>
{
public override IEnumerable<T> Merge()
{
var fst = new[] { Left.First (), Right.First () };
var max = new[] { fst.Max () };
var min = new[] { fst.Min () };
var left = new LeftList(max.Concat (Left.Skip (1)));
var right = new RightList(Right.Skip (1));
var rest = ListPair<T>.Create (left, right).Merge ();
return min.Concat (rest);
}
}
abstract class OneEmpty : ListPair<T>
{
private IEnumerable<T> xs;
public static OneEmpty Create(LeftList xs)
{
return new _Left (xs);
}
public static OneEmpty Create(RightList xs)
{
return new _Right (xs);
}
sealed class _Left : OneEmpty
{
public _Left(LeftList xs) { this.xs = xs; }
protected override LeftList Left { get { return new LeftList (xs); } }
protected override RightList Right { get { return new RightList(empty); } }
}
sealed class _Right : OneEmpty
{
public _Right(RightList xs) { this.xs = xs; }
protected override LeftList Left { get { return new LeftList (empty); } }
protected override RightList Right { get { return new RightList (xs); } }
}
public sealed override IEnumerable<T> Merge()
{
return xs;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment