2

Many functional languages have a cons operator. It returns the result of an immutable list or array like type, with a new element attached to the end, in constant time.

As a pseudo code example, [1,2] : 3 would evaluate to [1,2,3].

Swift has append to add an element to an Array in amortised constant time (with some caveats). However, append requires a mutable Array. I can create a mutable Array from an immutable one and then append, but I am very surprised that there does not seem to be an existing function or operator that does this for me and provides the amortised constant time guarantee (where not shared).

Community
  • 1
  • 1
Benjohn
  • 13,228
  • 9
  • 65
  • 127

1 Answers1

4

This is not the cons operator, per se, but you can use the + operator for arrays to append or prepend an array onto a mutable or immutable array in "constructor style"; constructing a new array with the concatenated result.

From the Swift Language Guide - Collection Types:

Creating an Array by Adding Two Arrays Together

You can create a new array by adding together two existing arrays with compatible types with the addition operator (+). The new array’s type is inferred from the type of the two arrays you add together:

...

I.e.,

let foo = [1, 2]
let bar = foo + [3]    // [1, 2, 3], "cons(foo, 3)"
let baz = [-1, 0] + bar // [-1, 0, 1, 2, 3], "cons([-1, 0], bar)"

Note, however, that this does not run in amortised constant time, since we require allocating new memory and copying the result into this. However, since arrays are value types in Swift, I don't see how how any operation on immutable arrays---such that we create a new immutable array---will run in constant time, since we will always require copying for this (even if, sometimes, this might be performed lazily).

Hence, the performance of the above shouldn't differ from constructing a new array using .append/.appendContentsOf on an existing mutable one followed by copying; the former step running in amortised constant time (due to exponentially growing pre-allocation of array space), but the latter one running in linear time.

dfrib
  • 70,367
  • 12
  • 127
  • 192
  • [Hello again!](http://stackoverflow.com/a/36635150/2547229) and thank you for the answer. I think I'm going to have to accept that if I want a [linear time `scan`](http://stackoverflow.com/q/35160890/2547229), I won't be able to build it on top of `reduce` :-) – Benjohn May 03 '16 at 09:50
  • 1
    @Benjohn Indeed, it would seem as if---w.r.t. complexity---many of the functional aspects of Swift (reduce, map) are sometimes a bit to non-interjoinable to compete with pure old imperatively implemented algorithms (e.g. the `scan` function in the other thread). Wr.t. the current thread: I'm uncertain if we can truly have a non-mutating (i.e., create new) `cons` in amortised linear time for the value type that Swift array is, as we will always "suffer" copying (even lazily). – dfrib May 03 '16 at 10:05