Skip to main content

Towards the best collection API... in C#. And some partial applications too.

The venerable Oleg Kiselyov once posted about the "best" collection traversal API. Let's call this ideal iterator a "SuperFold". LTU also covered his article. Essentially, a SuperFold is a left fold with early termination support. Any cursor can then be automatically derived from the SuperFold. The converse is not true.

Additional arguments are made in the above paper and in the LTU thread, so I won't repeat them here. Without further ado, I present the SuperFold for my purely functional list in C#:
//OCaml signature: ((T → B → bool * B) → B → B) → (T → B → bool * B) → B → B
B SuperFold<B>(
  Fun<Fun<T, B, Pair<bool, B>>, B, B> self,
  Fun<T, B, Pair<bool, B>> proc,
  B seed)
{
  bool cont;
  proc(head, seed).Bind(out cont, out seed);
  return cont ? self(proc, seed) : seed;
}

While quite simple, it's not as efficient as it should be since C#/.NET doesn't support proper tail calls. You can see in that source file that I derived FoldLeftDerived from SuperFold. Deriving FoldRight is a bit trickier, so I have to think about it. The simple, inefficient, answer is to simply reverse the list.

I've also enhanced the FP# library with:
  1. A number of tuple types (up to 10),
  2. Tuple inference,just call: Tuple._(a,b,c,...)
  3. streamed versions of Map/Filter/FoldRight over IEnumerable which don't build intermediate lists,
  4. FoldLeft over IEnumerable including support for early termination,
  5. FoldLeft over my purely functional list including support for early termination,
  6. Option type now looks more like System.Nullable, with an overload for the | operator to choose between an empty option, or a default value [1],
  7. Partial application for almost all defined function types
I'll probably remove SuperFold from my purely functional list, since I don't think it will end up being useful in C#. The iterated FoldLeft I defined is more efficient due to the lack of tail recursion, and the iterated version also supports early termination.

[1] It's very frustrating to see how close MS gets to a truly general and useful abstraction, only to lock it down for no apparent reason. What good reason is there for Nullable to be restricted to struct types? If you give it more than a second's thought, I think you'll realize that there is no good reason. Nullable is the option type if it weren't for this restriction!
Labels:

Comments

leppie said…
As C# does not support tail calls (the CLR does however support them just fine), you should not use a recursive construct. Rewriting the recursion to use iteration is fairly simply in the case, and should be employed.
January 17, 2008 at 3:21 AM
Sandro Magi said…
1. The CLR unfortunately does not support tail calls just fine, it supports them poorly, despite work demonstrating that tail calls are not in conflict with stack inspection.

2. I think there is no iterative equivalent of SuperFold, due to the mutual recursion between self and proc.
January 17, 2008 at 12:25 PM
Post a Comment

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre...
1 comment
Read more

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu...
Post a Comment
Read more

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen...
Post a Comment
Read more