ImmutableArray in Objective-C; Uses AviNode, found here: https://gist.github.com/BobStrogg/8449933

ImmutableArray.h

//
//  ImmutableArray.h
//  AVLTree
//
//  Created by Chris Cavanagh on 1/17/14.
//

#import <Foundation/Foundation.h>

@interface ImmutableArray : NSObject

+ (void) initialize;

+ (ImmutableArray *) empty;

+ (ImmutableArray *) array;

- (id) init;

- (NSUInteger) count;

- (ImmutableArray *) addObject:(id)object;

- (ImmutableArray *) insertObject:(id)object
						  atIndex:(NSUInteger)index;

- (NSUInteger) indexOfObject:(id)object;

- (id) objectAtIndex:(NSUInteger)index;

- (NSEnumerator *)getEnumerator:(BOOL)reverse;

@end

ImmutableArray.m

//
//  ImmutableArray.m
//  AVLTree
//
//  Created by Chris Cavanagh on 1/17/14.
//

#import "ImmutableArray.h"
#import "AvlNode.h"

@interface ImmutableArrayEnumerator : NSEnumerator

- (id) initWithNode:(AvlNode *)root
			reverse:(BOOL)reverse
		   comparer:(EqualityComparer)equalityComparer;

@end

@implementation ImmutableArray
{
	AvlNode *_root;
	EqualityComparer _valueComparer;
}

static ImmutableArray *_empty;

+ (void) initialize
{
	if ( [self class] == [ImmutableArray class] )
	{
		_empty = [ImmutableArray new];
	}
}

+ (ImmutableArray *) empty
{
	return _empty;
}

+ (ImmutableArray *) array
{
	return [ImmutableArray new];
}

- (id) init
{
	if ( ( self = [super init] ) )
	{
		_root = [AvlNode empty];
		_valueComparer = ^( id v1, id v2 ) { return ( v1 < v2 ) ? -1 : ( v1 > v2 ) ? 1 : 0; };
	}

	return self;
}

- (id) initWithRoot:(AvlNode *)root
		   comparer:(EqualityComparer)equalityComparer
{
	if ( ( self = [super init] ) )
	{
		_root = root;
		_valueComparer = equalityComparer;
	}

	return self;
}

- (NSUInteger) count
{
	return [_root count];
}

- (ImmutableArray *) addObject:(id)object
{
	return [self insertObject:object atIndex:[self count]];
}

- (ImmutableArray *) insertObject:(id)object
						  atIndex:(NSUInteger)index
{
	return [[ImmutableArray alloc] initWithRoot:[_root insertIntoNew:index value:object] comparer:_valueComparer];
}

- (NSUInteger) indexOfObject:(id)object
{
	AvlNode *node = [_root searchNode:object comparer:_valueComparer];

	return ( node != nil ) ? node.count : -1;
}

- (id) objectAtIndex:(NSUInteger)index
{
	return [_root getNodeAt:index].value;
}

- (NSEnumerator *)getEnumerator:(BOOL)reverse
{
	return [[ImmutableArrayEnumerator alloc] initWithNode:_root reverse:reverse comparer:_valueComparer];
}

@end

@implementation ImmutableArrayEnumerator
{
	AvlNode *_root;
	BOOL _reverse;
	NSEnumerator *_avlNodeEnumerator;
	EqualityComparer _valueComparer;
}

- (id) initWithNode:(AvlNode *)root
			reverse:(BOOL)reverse
		   comparer:(EqualityComparer)equalityComparer
{
	if ( ( self = [super init] ) )
	{
		_root = root;
		_reverse = reverse;
		_avlNodeEnumerator = [root getEnumerator:reverse];
		_valueComparer = equalityComparer;
	}

	return self;
}

- (id) nextObject
{
	AvlNode *next = [_avlNodeEnumerator nextObject];

	return ( next != nil ) ? next.value : nil;
}

- (NSArray *)allObjects
{
	NSMutableArray *result = [NSMutableArray new];
	ImmutableArrayEnumerator *enumerator = [[ImmutableArrayEnumerator alloc] initWithNode:_root reverse:_reverse comparer:_valueComparer];

	id item = nil;

	while ( nil != ( item = [enumerator nextObject] ) )
	{
		[result addObject:item];
	}

	return result;
}

@end