How to write Extension Methods in F# and Swift

I’ve used extension methods for a while in F# as a neat way of adding utility methods to system types. For example, suppose you have a set and want to add some elements to it? You might write something like this:

  let collection = ... // initial set defined elsewhere
  let collection = // add extra elements into collection
    [| 1; 2; 3 |] |> Array.fold (fun (acc : Set<'T>) item -> acc.Add item) collection

You might find yourself writing this snippet frequently and for different container types. Instead of defining the operation every time, it’s better to write an extension method:

namespace MusingStudio.Extensions
module Set =
  let AddMulti (items : seq<'T>) (collection : Set<'T>) =
    items |> Seq.fold (fun (acc : Set<'T>) item -> acc.Add item) collection

Then, by bringing the extensions into scope, we can call AddMulti as if it were part of the system Set interface:

open MusingStudio.Extensions

[<EntryPoint>]
let main argv = 
    let initial = [| 1; 2; 3 |] |> Set.ofArray
    let updated = initial |> Set.AddMulti [| 4; 5; 6 |]
    printfn "%A" updated
    0 // return an integer exit code

I was looking for a way to get the current time/date in Swift, and found some code on Stack Overflow that uses Extension Methods to do it. I’ve added a couple more methods to get the seconds and day-of-month:

import Foundation

// From: http://stackoverflow.com/questions/24070450/how-to-get-the-current-time-and-hour-as-datetime
extension NSDate
{
    func hours() -> Int
    {
        //Get Hours
        let calendar = NSCalendar.currentCalendar()
        let components = calendar.components(.Hour, fromDate: self)
        let hours = components.hour
        
        //Return Hour
        return hours
    }
    
    func minutes() -> Int
    {
        //Get Minutes
        let calendar = NSCalendar.currentCalendar()
        let components = calendar.components(.Minute, fromDate: self)
        let minutes = components.minute
        
        //Return Minute
        return minutes
    }
    
    func seconds() -> Int
    {
        // Get Seconds
        let calendar = NSCalendar.currentCalendar()
        let components = calendar.components(.Second, fromDate: self)
        let seconds = components.second
        
        return seconds
    }
    
    func day() -> Int
    {
        // Get Day
        let calendar = NSCalendar.currentCalendar()
        let components = calendar.components(.Day, fromDate: self)
        let day = components.day
        
        return day
    }
}

This simplifies the interface to NSDate:

  // Get the time properties
  let currentDate = NSDate()
  let minutes = currentDate.minutes()
  let hours = currentDate.hours()
  let seconds = currentDate.seconds()
  let dayOfMonth = currentDate.day()

2 Comments

Filed under F#, Programming, Swift

C++17 News

Herb Sutter blogged about the Oulo ISO C++ meeting. There’s a link to an interview he did for the excellent CppCast podcast and also to a reddit post on features approved at the meeting.
CppCast

As Herb called out in the interview, I think the following two features will be widely used:
Structured Bindings
This is interesting because I’ve been using the std::tie syntax for a while, despite the clumsiness when you need to introduce new variables to take the return types (leaving them uninitialised until assignment). The proposal above avoids that problem.

tuple<T1,T2,T3> f(/*...*/) { /*...*/ return {a,b,c}; }

// BEFORE
T1 x;
T2 y;
T3 z;
std::tie( x, y, z ) = f();

// AFTER
auto [x,y,z] = f(); // x has type T1, y has type T2, z has type T3

Initialisation clause for if and switch
This proposal makes if/switch more consistent with for loops that allow separate initialisation/increment clauses as well as a condition. So now you can initialise a variable separately from the if condition, which also allows you to limit the scope of that variable.

// BEFORE
status_code c = bar();     
if (c != SUCCESS) 
{       
    return c;     
}

// AFTER
if (status_code c = bar(); c != SUCCESS) 
{     
  return c;   
}

Leave a comment

Filed under C++, Programming

IET Meetup: Rosetta Spacecraft Seminar

Meetup - Rosetta SpacecraftI was thrilled when the IET announced that they were organising a seminar on the European Space Agency’s Rosetta mission. I’d followed the progress of the mission and the audacious landing of the Philae probe on the comet – it was fascinating to meet Paulo Ferri, the Operations Manager for the mission. Also speaking was Mark Bentley, Principal Investigator of the MIDAS instrument on board Rosetta.

Rosetta67P

I asked Paulo how the agency chose comet 67P as the target for the mission. Apparently, it wasn’t the original choice, but a failed Ariane rocket caused the mission to pause and the launch window for the original comet was missed. They re-examined the list of choices and given that Rosetta and Philae had already been built, the only other suitable comet for a mission of that type was 67P!

Leave a comment

Filed under Meetup, Technology

Book Review: Moon Dust, Andrew Smith

MoonDustThis book tells the journey taken by the author in his attempts to find and interview all the remaining astronauts who have walked on the moon. Twelve men in history have known what it is like, and at the time of his writing, only nine were alive. The book describes the impact such an event had on the lives of the men.

It’s an interesting read, primarily it’d good to hear about astronauts other than Buzz Aldrin – the others have just as interesting stories, both of their lunar expeditions, and the effect on their lives afterwards. Yet, the media attention is generally given to Buzz Aldrin these days, with his ideas on colonisation of Mars.
Three Stars

Leave a comment

Filed under Book Review

IET Meetup: Robots Helping People, Yiannis Demiris

IETLogo
Meetup - Robots helping PeopleProfessor Yiannis Demiris gave the latest Prestige Lecture at the IET. His work is truly inspirational – his research aims to develop robots that can help both children with disabilities and adults with chronic or mobility problems. A running theme throughout his talk was the need for the robot’s behaviour to adapt during the life of the relationship with the person – as the person learns a skill, the robot can lower its levels of assistance. Or, the robot can take the person to the next level, for example in therapeutic exercises or in gaming.
YiannisDemiris
The speaker heads the Personal Robotics Laboratory at Imperial College London, where he conducts research in personalised assistive robotic systems, with applications in healthcare, in-vehicle intelligence, and support for children and adults with disabilities.

Leave a comment

Filed under Meetup, Technology

How to initialise data concisely in C++

In the past, creating a collection of dates was a chore, because you had to individually insert them into a container (e.g. declaring a vector on one line and then pushing dates into it on subsequent lines). With features like std::initializer_list from C++11 onwards, it’s now much easier to do this concisely.

Here’s some simple, concise code to create dates without all the hassle:

struct Date
{
    std::string Event;

    int Year;
    int Month;
    int Day;
};

void print( const Date& date )
{
    std::cout << date.Event << ": "<< date.Year << "/" << date.Month << "/" << date.Day << "\n";
}

void print( const std::vector<Date>& dates )
{
    for ( auto date : dates )
    {
        print( date );
    }
}

void test()
{
    std::cout << "Print date:\n";
    print( { "Today", 2015, 5, 5 } );

    std::cout << "Print dates:\n";
    print( {
        { "Christmas", 2015, 12, 25 },
        { "Spring Bank Holiday", 2016, 6, 30 }
           } );
}

This style is particularly useful when writing tests – you can write a whole test, including setting up the data, on a single line (or at least, in a single function call).

Another compelling use case comes when creating test cases for graph algorithms. Suppose you have the following data structures for an undirected, weighted graph:

struct Edge
{
    const size_t end1;
    const size_t end2;
    const size_t cost;
};

struct Graph
{
    size_t source;
    size_t nodes;
    std::vector<Edge> edges;
};

Then creating a test graph to pass into an algorithm is as simple as:

shortest_path( { 0, 4, { {0,1,24}, {0,3,20}, {2,0,3}, {3,2,12} } })

Leave a comment

Filed under C++, C++ Code, Programming

How to efficiently find the n’th biggest element in a collection

Looking at std::nth_element the other day, I noticed that it’s complexity is O(n) for a collection of size n, and wondered how that was achieved. A basic implementation of an algorithm to find the ith-biggest element might start by sorting the collection and index to the ith afterwards – complexity O(n*log(n)):

int ith_element_by_sorting( std::vector<int> input, int i )
{
    std::sort( std::begin(input), std::end(input) );
    return input[i];
}

It’s a small step to realise then that you don’t need to sort all n elements of the collection – only the first i elements, so complexity O(n*log(i)):

int ith_element_by_partial_sort( std::vector<int> input, int i )
{
    std::partial_sort( std::begin( input ), std::begin( input ) + i + 1, std::end( input ) );
    return input[i];
}

But the real trick is that you don’t need to do any sorting at all. That’s the approach taken by quickselect, which is the selection sibling to quicksort, and achieves O(n) complexity on average:

int partition( std::vector<int>& values, int left, int right, int pivot )
{
     auto pivotValue = values[ pivot ];

     std::swap( values[pivot], values[right] ); // Move pivot to end
     auto store_pos = left;

     for ( int j = left; j < right; ++j )
     {
         if ( values[j] < pivotValue )
         {
             std::swap( values[ store_pos ], values[j] );
             ++store_pos;
         }
     }

     std::swap( values[right], values[ store_pos ] );  // Move pivot to its final place

     return store_pos;
}

int quickselect( std::vector<int> values, int left, int right, int i )
{
    // Unordered - no need to sort values at all, 
    // instead we recursively partition only the subset of values
    // containing the i'th element, until we have either
    // a) trivial subset of 1
    // b) pivot is moved to exactly the location we wanted 
    while( 1 )
    {
         if ( left == right )
         {
             return values[left];
         }

         // Pick a pivot from middle of values.
         // Better options are a random pivot or median of 3
         auto pivot = (left + right)/2; 

         // Move anything smaller than values[pivot] to the left of pivot,
         // and return updated position of pivot
         pivot = partition( values, left, right, pivot );

         if ( pivot == i )
         {
             return values[i];
         }
         else if ( i < pivot )
         {
             right = pivot - 1;
         }
         else
         {
             left = pivot + 1;
         }
    }
}

int ith_element_by_quickselect( const std::vector<int>& input, int i )
{
    return quickselect( input, 0, input.size()-1, i );
}

int ith_element( const std::vector<int>& input, int i )
{
    if ( i < 0 || i >= input.size() )
    {
        std::ostringstream ss;
        ss << "Input '" << i << "' outside range [0," << input.size() << ")";
        throw std::out_of_range( ss.str() );
    }

    return ith_element_by_quickselect( input, i );
}

Here’s some test code to check that the implementation works:

template <typename F, typename T>
void should_be( T t, F f, const std::string& message )
{
    try
    {
        std::ostringstream ss;

        auto got = f();
        if ( got != t )
        {
            ss << message << " got " << got << ", expected " << t;
            throw std::runtime_error( ss.str() );
        }
        else
        {
            ss << "OK: " << message << ": got " << got;
            std::cout << ss.str() << "\n";
        }
    }
    catch( const std::exception& ex )
    {
        // Report error if either f() threw or we found unexpected value
        std::cout << "ERROR: " << ex.what() << "\n";
    }
}

template <typename F>
void should_throw( F f, const std::string& message )
{
    try
    {
        f();
    }
    catch( const std::exception& ex )
    {
        std::cout << "OK: " << message << ": threw \"" << ex.what() << "\"\n";
        return;
    }

    std::cout << "ERROR: " << message << " should have thrown\n";
}

#define SHOULD_BE( t, expr ) should_be( t, [](){ return expr; }, #expr )
#define SHOULD_THROW( expr ) should_throw( [](){ expr; }, #expr )

void testIthElement()
{
    SHOULD_THROW( ith_element( {}, 0 ) );
    SHOULD_THROW( ith_element( {1,2}, -1 ) );
    SHOULD_THROW( ith_element( {1,2,3}, 3 ) );

    SHOULD_BE( 1, ith_element( {1}, 0 ) );
    SHOULD_BE( 0, ith_element( {0,1,2,3,4,5,6,7,8}, 0 ) );
    SHOULD_BE( 2, ith_element( {0,1,2,3,4,5,6,7,8}, 2 ) );
    SHOULD_BE( 6, ith_element( {5,4,7,6,1,2,0,8,3}, 6 ) );
    SHOULD_BE( 8, ith_element( {5,4,7,6,1,2,0,8,3}, 8 ) );
    SHOULD_BE( 5, ith_element( {5,5,5,5,5,5}, 1 ) );
}

Here’s the output:
QuickSelect

In fact, reviewing old posts on this blog, I found this link that dates back to 2013, when std::nth_element was only required by the standard to have worst-case O(N^2) complexity, with O(N) on average – precisely what you’d get from quickselect. Now though, thanks to introselect, O(N) is possible.

Leave a comment

Filed under C++, C++ Code, Programming

Tech Book: Effective Modern C++, Scott Meyers

EffectiveModernC++When Scott Meyers announced his retirement from C++ duties, I thought I’d get a copy of his latest book. There’s plenty in it to interest even seasoned C++ developers – as always, Scott’s insight and in-depth examples are worth studying. I’ve tried out most of the C++11 features, but still learnt a lot working through this book.

Uniform Initialisation and Auto
Meyers points out that compared to parentheses or just plain “=”, braced initialisation can be used in the most contexts, avoids his famous “C++’s most vexing parse”, and will issue compiler errors if narrowing occurs. However, for types that can take a std::initialiser_list in their constructor, the compiler is required to favour std::initialiser_list over any other interpretation. That’s a deterrent to use of braced initialisation with types that have a std::initializer_list constructor – and also precludes using auto with braced initialisation.

auto x = { 4 }; // type of x is inferred to be std::initializer_list&lt;int&gt;!

How to use the new “= delete” idiom
Meyers recommends declaring deleted methods as public to get better error messages from compilers that check for accessibility before deleted status. He also points out that you can declare non-member functions as deleted (I’d only seen examples of copy-constructor/copy-assignment operator as deleted before).

Use of noexcept on move operations
This one is a classic example of a combination of language features having an unexpected effect. std::vector::push_back offers the strong exception guarantee. It can achieve this using any copy constructor and being sure not to change the original contents of the vector until any new elements or copies have been constructed. Hence, move constructors are only preferred if it is exception-safe to do so – which means they must be marked as noexcept (and if that isn’t appropriate, you just won’t get move semantics pushing instances of your type into a std::vector).

Recursion with constexpr
Having toyed with template meta-programming in the past, this use of constexpr appeals to me:

constexpr int pow( int b, int exp ) noexcept
{
    return (exp == 0 ? 1 : b * pow( b, exp-1 ));
}
constexpr auto eight = pow( 2, 3 );

void testConstExpr()
{
    std::cout &lt;&lt; &quot;2^3 = &quot; &lt;&lt; eight &lt;&lt; &quot;\n&quot;;
}

It’s much more succinct than the equivalent TMP version, and still performs the calculation at compile time.

Summary
In the past, I’ve recommended Effective C++ for developers who have little experience of the language and wish to improve their skills. I think this book is a bit too advanced for that, particularly given the chapters on template type deduction and decltype being in the first part of the book! So read this book if you’ve got a few years’ experience of C++ already, but look at Effective C++ (3rd Edition) to improve on the basics.

Four stars

Leave a comment

Filed under C++, C++ Code, Programming, Tech Book

C++14 Language Extensions

Whilst reading Scott Meyers’ Effective Modern C++, I was looking for some clarification on ‘generalised lambda capture’ and came across this C++ 14 feature list. It was interesting to compare to the list of expected features that Bjarne Stroustrup presented at the ACCU 2013 conference – he described all of the following, which made it into C++14:

  • Generalised return type deduction for normal functions, not just lambdas
  • Generic (polymorphic) lambdas
  • Generalised constexpr functions (listed as Extended constexpt on the feature list)
  • Binary Literals
  • Digit Separators
  • Deprecated Attribute

However, this one appears not to have made the cut:

  • Runtime-sized arrays

This would be a great new feature and I blogged about it at the time – but it appears the work has stalled.

Leave a comment

Filed under C++, Programming

BCS Meetup – The Trust Machine, Simon Taylor

BCS LogoThe BCS hosted a presentation by Simon Taylor of Barclays Bank.

Meetup - The Trust Machine

With the full potential of the uses of blockchain databases still yet to be discovered, there is a race, led by financial services, following the growth of Bitcoin, to find new, transformational business models that will exploit this technology.

Simon will explain that, while a Blockchain is just a kind of shared database, it is quite different because it creates a system of transparent, unalterable and permanent records of agreements. The impact of this is to allow all parties to organise themselves without fear of cheating. Simon will explain how cryptographic keys are used to create this trust, how it stops any single party from having more control than any other, and how, by allowing parties, for instance a buyer and a seller, to directly connect, it is seen as an opportunity and a threat by established trusted intermediaries, like his own organisation.

Simon covered a lot of interesting use cases in his presentation and shone light on the differences between bitcoin/blockchain as a technology. For example, this scenario was in his talk and on his blog:

Problem: When an investor comes to raise a Seed, things get messy, people fall out. Solution: Store this on a Blockchain at NASDAQ which has perfect time stamps, and digital signatures and no database administrator can edit the record without signatures of the founders. Could you do this with a database? Sure, but you’d lose that audit trail.

There are plenty of links to further reading on the blog post, 10 things you should know about Blockchains.  Also, What is the Blockchain and why should you care on Recode is worth a read.

Leave a comment

Filed under Meetup, Technology