Skip to main content

Sasa.Collections.Arrays - Purely Functional Array Combinators

This is the twentieth post in my ongoing series covering the abstractions in Sasa. Previous posts:

Many abstractions in Sasa provide purely functional semantics since such features tend to be absent in .NET's base class libraries. Sasa.Collections.Arrays is then exactly what it sounds like: a purely functional interface for manipulating one-dimensional arrays. The exported API includes extension methods for slicing, setting slots, appending, inserting and removing elements, all without mutating the original array.

I don't recall the original inspiration for this API, but it was likely some combination of APL and concatenative languages like Forth and Factor. The interface is also not necessarily complete, but it's sufficiently complete that I could relatively easily implement a hash-array mapped trie.

Sasa.Collections.Arrays.Append

The Arrays.Append extension method creates a new array with a new value appended to the end:

var array = new[] { 1, 2, 3 }.Append(4);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 2, 3, 4, 

Sasa.Collections.Arrays.Bound

The Arrays.Bound extension method ensures that the given array is of exactly the size passed in as an argument. If the array is longer, it creates a slice of the given array starting at index 0:

var array = new[] { 1, 2, 3, 4 }.Bound(2);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 2, 

Sasa.Collections.Arrays.Concat

Arrays.Concat operates much like Enumerable.Concat, but returns an array instead of an IEnumerable<T>:

var array = new[] { 1, 2, 3 }.Concat(4, 5);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 2, 3, 4, 5, 

Sasa.Collections.Arrays.Create

Arrays.Create is a simple convenience method for constructing arrays:

var array = Arrays.Create(1, 2, 3, 4);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 2, 3, 4, 

Sasa.Collections.Arrays.Dup

Arrays.Dup creates an exact duplicate of the given array:

var orig = new[] { 1, 2, 3 };
var dup = orig.Dup();
Console.WriteLine(orig == dup);
Console.WriteLine(orig.SequenceEqual(dup));
// output:
// false
// true

Sasa.Collections.Arrays.Fill

Arrays.Fill is an extension method that fills a given array with a given value between certain bounds. The following code sample utilizes C#'s named parameters for clarity:

var array = new int[4];
array.Fill(item: 1, start: 0, count: 2);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 1, 0, 0, 

Sasa.Collections.Arrays.IndexOf

Arrays.IndexOf is an extension method that searches an array from beginning to end and returns the first item that matches a predicate, or -1 if no item matches:

var array = new[] { 1, 2, 3, 4 };
var i = array.IndexOf(x => x > 2);
Console.WriteLine(i);
// output:
// 2

Sasa.Collections.Arrays.Insert

Arrays.Insert is an extension method that creates a new array with the given element inserted at the given index:

var orig = new[] { 1, 2, 3 };
var array = orig.Insert(index: 1, value: 99);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 99, 2, 3, 

Sasa.Collections.Arrays.Remove

Arrays.Insert is an extension method that creates a new array with the element at the given index removed:

var orig = new[] { 1, 99, 2, 3 };
var array = orig.Remove(1);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 2, 3, 

Sasa.Collections.Arrays.Repeat

Arrays.Repeat is an extension method that repeats all elements up to the given index as many times as will fit in the given array:

var array = new[] { 1, 2, 3, 4, 5 }.Repeat(2);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 2, 1, 2, 1, 

Sasa.Collections.Arrays.Set

Arrays.Set is an extension method that creates a new array with the given index initialized to the given value:

var orig = new[] { 1, 2, 3 };
var array = orig.Set(index: 1, value: 99);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 1, 99, 3, 

Sasa.Collections.Arrays.Set

Arrays.Slice is an extension method that extracts a sub-array from the given array delimited by a start and end index:

var array = new[] { 1, 2, 3, 4, 5, 6, 7, 8 }
            .Slice(start: 2, end: 5);
foreach (var x in array)
    Console.Write("{0}, ", x);
// output:
// 3, 4, 5, 

Sasa.Collections.Arrays.ToArray

Arrays.ToArray is a set of extension methods that copies an enumerable sequence into a newly created array given by the lower bounds and lengths:

var source = new[] { 1, 2, 3, 4 };
var twod = source.ToArray<int[,],int>(new[]{ 0, 0 }, new[]{ 2, 2 });
Console.Write("| {0}, {1} |", twod[0,0], twod[0,1]);
Console.Write("| {0}, {1} |", twod[1,0], twod[1,1]);
// output:
// | 1, 2 |
// | 3, 4 |

This extension attempts to copy the array using the fastest means possible, and only uses the slow, generic array indexing interface when the array type has more than 3 indexes.

Comments

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

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

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