Skip to content

Instantly share code, notes, and snippets.

@fj
Created July 16, 2012 12:33
Show Gist options
  • Save fj/3122440 to your computer and use it in GitHub Desktop.
Save fj/3122440 to your computer and use it in GitHub Desktop.

A representative but thoroughly useless and unscientific way to see how people write short pieces of code.

Write a function, method, or other similar construct in your favorite language that:

  • accepts an array arr and a value v
  • returns the element in arr whose successor is v, if there is such an element; otherwise return nothing

Test cases:

find_before([5, 6, 7], 6)
# => 5

find_before([5, 6, 7], 7)
# => 6

find_before([5, 6, 7], 5)
# => nothing

find_before([5, 6, 7], 999)
# => nothing
@fj
Copy link
Author

fj commented Jul 16, 2012

Some examples in Ruby:

CS 101

def find_before(arr, v)
  i = arr.index(v)
  if i && i > 0
    arr[i-1]
  end
end

Entry-level Rubyist

def find_before arr, v
  arr.take(arr.index(v) || 0).last
end

Another flavor

def find_before arr, v
  arr.each_cons(2).find { |x, y| y == v }.first
end

Module-opening variant

module Enumerable
  def find_before(v)
    take(index(v) || 0).last
  end
end

# => arr.find_before v

@jonpryor
Copy link

A literal translation of the requirements into C# would be:

public static int? find_before (int[] arr, int v)
{
    int? p = null;
    foreach (var e in arr) {
        if (e == v)
            return p;
        p = e;
    }
    return null;
}

This uses nullable types to allow null to be used as "nothing." Unfortunately, this restricts the types to integers, which is (generally) undesirable. We could use C# generics and restrict things to value types, but that's still less than ideal.

A more ".NET-like" API would require changing the find_before() prototype, and making the method an extension method:

public static bool TryFindBefore<T>(this IEnumerable<T> values, T value, out T before, EqualityComparer<T> comparer = null)
{
    comparer    = comparer ?? EqualityComparer<T>.Default;
    before      = default (T);
    bool found  = false;
    foreach (var v in values) {
        if (comparer.Equals (value, v)) {
            return found;
        }
        before = v;
        found  = true;
    }
    return false;
}

Use:

int before;
if (new[]{5,6,7}.TryFindBefore(5, out before)) {
    // value found, stored in `before`...
}

The problem with this is that it requires using out parameters, though it is more consistent with the rest of the .NET framework.

Finally, we could use Cadenza, a collection of types and utility methods, including a Maybe<T> type. This allows us to unify reference and value types, allowing something closer-in-spirit to the Ruby methods:

public static Maybe<T> FindBefore<T>(this IEnumerable<T> values, T value, EqualityComparer<T> comparer = null)
{
    comparer    = comparer ?? EqualityComparer<T>.Default;
    return values.ContiguousSubsequences (2)
        .FirstOrDefault<IEnumerable<T>> (e => comparer.Equals (value, e.ElementAt (1)))
        .With (e => e == null ? Maybe<T>.Nothing : e.First ().Just ());
}

Use:

Maybe<int> m = new[]{5,6,7}.FindBefore(5);
// m.HasValue == false

@fj
Copy link
Author

fj commented Jul 16, 2012

@jonpryor Very nice! The API with the Maybe<T> return value variant feels really fluent too.

If you could keep the intent of the method, but change the specification -- for example, to do something else instead of returning null in the corner cases -- would you make an adjustment that would make it more similar to how you'd expect C# methods to work? (For example, would you expect an exception to be thrown instead?)

@jonpryor
Copy link

If I could change the specification, I'd alter it to take a "value not found" parameter which is returned if the value isn't found. A test case would thus become:

find_before([5, 6, 7], 5, nil)
# => nil

This would be in keeping with Nullable<T>.GetValueOrDefault(T) and other methods. C# implementation could thus become:

public static T FindBeforeOrDefault<T>(this IEnumerable<T> values, T value, T defaultValue = default (T), EqualityComparer<T> comparer = null)
{
    comparer    = comparer ?? EqualityComparer<T>.Default;
    return values.ContiguousSubsequences (2)
        .FirstOrDefault<IEnumerable<T>> (e => comparer.Equals (value, e.ElementAt (1)))
        .With (e => e == null ? defaultValue : e.First ());
}

I would not expect an exception to be thrown; exceptions are for errors and exceptions are (generally) slow, so they should be avoided for common errors. For example, Stream.Read() returns 0 on end-of-stream instead of throwing an EndOfStreamException, as hitting end-of-stream is a common condition.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment