The algorithm powering iHarmony

Problem

I wrote the first version of iHarmony in 2008. It was the very first iOS app I gave birth to, combining my passion for music and programming. I remember buying an iPhone and my first Mac with the precise purpose of jumping on the apps train at a time when it wasn’t clear if the apps were there to stay or were just a temporary hype. But I did it, dropped my beloved Ubuntu to join a whole new galaxy. iHarmony was also one of the first 2000 apps on the App Store.

Up until the recent rewrite, iHarmony was powered by a manually crafted database containing scales, chords, and harmonization I inputted.

What-a-shame!

I guess it made sense, I wanted to learn iOS and not to focus on implementing some core logic independent from the platform. Clearly a much better and less error-prone way to go would be to implement an algorithm to generate all the entries based on some DSL/spec. It took me almost 12 years to decide to tackle the problem and I’ve recently realized that writing the algorithm I wanted was harder than I thought. Also thought was a good idea give SwiftUI a try since the UI of iHarmony is extremely simple but… nope.

Since someone on the Internet expressed interest 😉, I wrote this article to explain how I solved the problem of modeling music theory concepts in a way that allows the generation of any sort of scales, chords, and harmonization. I only show the code needed to get a grasp of the overall structure.

I know there are other solutions ready to be used on GitHub but, while I don’t particularly like any of them, the point of rewriting iHarmony from scratch was to challenge myself, not to reuse code someone else wrote. Surprisingly to me, getting to the solution described here took me 3 rewrites and 2 weeks.

Solution

The first fundamental building blocks to model are surely the musical notes, which are made up of a natural note and an accidental.

enum NaturalNote: String {
    case C, D, E, F, G, A, B
}

enum Accidental: String {
    case flatFlatFlat = "bbb"
    case flatFlat = "bb"
    case flat = "b"
    case natural = ""
    case sharp = "#"
    case sharpSharp = "##"
    case sharpSharpSharp = "###"
    
    func applyAccidental(_ accidental: Accidental) throws -> Accidental {...}
}

struct Note: Hashable, Equatable {
    
    let naturalNote: NaturalNote
    let accidental: Accidental
    
    ...
    
    static let Dff = Note(naturalNote: .D, accidental: .flatFlat)
    static let Df = Note(naturalNote: .D, accidental: .flat)
    static let D = Note(naturalNote: .D, accidental: .natural)
    static let Ds = Note(naturalNote: .D, accidental: .sharp)
    static let Dss = Note(naturalNote: .D, accidental: .sharpSharp)
    
    ...
    
    func noteByApplyingAccidental(_ accidental: Accidental) throws -> Note {...}
}

Combinations of notes make up scales and chords and they are… many. What’s fixed instead in music theory, and therefore can be hard-coded, are the keys (both major and minor) such as:

• C major: C, D, E, F, G, A, B
• A minor: A, B, C, D, E, F, G
• D major: D, E, F#, G, A, B, C#

We’ll get back to the keys later, but we can surely implement the note sequence for each musical key.

typealias NoteSequence = [Note]

extension NoteSequence {
    static let C = [Note.C, Note.D, Note.E, Note.F, Note.G, Note.A, Note.B]
    static let A_min = [Note.A, Note.B, Note.C, Note.D, Note.E, Note.F, Note.G]
    
    static let G = [Note.G, Note.A, Note.B, Note.C, Note.D, Note.E, Note.Fs]
    static let E_min = [Note.E, Note.Fs, Note.G, Note.A, Note.B, Note.C, Note.D]
    
    ...
}

Next stop: intervals. They are a bit more interesting as not every degree has the same types. Let’s split into 2 sets:

1. 2nd, 3rd, 6th and 7th degrees can be minor, major, diminished and augmented
2. 1st (and 8th), 4th and 5th degrees can be perfect, diminished and augmented.

We need to use different kinds of “diminished” and “augmented” for the 2 sets as later on we’ll have to calculate the accidentals needed to turn an interval into another.

Some examples:

• to get from 2nd augmented to 2nd diminished, we need a triple flat accidental (e.g. in C major scale, from D♯ to D♭♭ there are 3 semitones)
• to get from 5th augmented to 5th diminished, we need a double flat accidental (e.g. in C major scale, from G♯ to G♭there are 2 semitones)

We proceed to hard-code the allowed intervals in music, leaving out the invalid ones (e.g. Interval(degree: ._2, type: .augmented))

enum Degree: Int, CaseIterable {
    case _1, _2, _3, _4, _5, _6, _7, _8
}

enum IntervalType: Int, RawRepresentable {
    case perfect
    case minor
    case major
    case diminished
    case augmented
    case minorMajorDiminished
    case minorMajorAugmented
}

struct Interval: Hashable, Equatable {
    let degree: Degree
    let type: IntervalType
    
    static let _1dim = Interval(degree: ._1, type: .diminished)
    static let _1    = Interval(degree: ._1, type: .perfect)
    static let _1aug = Interval(degree: ._1, type: .augmented)
    
    static let _2dim = Interval(degree: ._2, type: .minorMajorDiminished)
    static let _2min = Interval(degree: ._2, type: .minor)
    static let _2maj = Interval(degree: ._2, type: .major)
    static let _2aug = Interval(degree: ._2, type: .minorMajorAugmented)
    
    ...
    
    static let _4dim = Interval(degree: ._4, type: .diminished)
    static let _4    = Interval(degree: ._4, type: .perfect)
    static let _4aug = Interval(degree: ._4, type: .augmented)
    
    ...
    
    static let _7dim = Interval(degree: ._7, type: .minorMajorDiminished)
    static let _7min = Interval(degree: ._7, type: .minor)
    static let _7maj = Interval(degree: ._7, type: .major)
    static let _7aug = Interval(degree: ._7, type: .minorMajorAugmented)
}

Now it’s time to model the keys (we touched on them above already). What’s important is to define the intervals for all of them (major and minor ones).

enum Key {
    // natural
    case C, A_min
    
    // sharp
    case G, E_min
    case D, B_min
    case A, Fs_min
    case E, Cs_min
    case B, Gs_min
    case Fs, Ds_min
    case Cs, As_min
    
    // flat
    case F, D_min
    case Bf, G_min
    case Ef, C_min
    case Af, F_min
    case Df, Bf_min
    case Gf, Ef_min
    case Cf, Af_min
    
    ...
    
    enum KeyType {
        case naturalMajor
        case naturalMinor
        case flatMajor
        case flatMinor
        case sharpMajor
        case sharpMinor
    }
    
    var type: KeyType {
        switch self {
        case .C: return .naturalMajor
        case .A_min: return .naturalMinor
        case .G, .D, .A, .E, .B, .Fs, .Cs: return .sharpMajor
        case .E_min, .B_min, .Fs_min, .Cs_min, .Gs_min, .Ds_min, .As_min: return .sharpMinor
        case .F, .Bf, .Ef, .Af, .Df, .Gf, .Cf: return .flatMajor
        case .D_min, .G_min, .C_min, .F_min, .Bf_min, .Ef_min, .Af_min: return .flatMinor
        }
    }
    
    var intervals: [Interval] {
        switch type {
        case .naturalMajor, .flatMajor, .sharpMajor:
            return [
                ._1, ._2maj, ._3maj, ._4, ._5, ._6maj, ._7maj
            ]
        case .naturalMinor, .flatMinor, .sharpMinor:
            return [
                ._1, ._2maj, ._3min, ._4, ._5, ._6min, ._7min
            ]
        }
    }
    
    var notes: NoteSequence {
        switch self {
        case .C: return .C
        case .A_min: return .A_min
    	...
    }
}

At this point we have all the fundamental building blocks and we can proceed with the implementation of the algorithm.

The idea is to have a function that given

• a key
• a root interval
• a list of intervals

it works out the list of notes. In terms of inputs, it seems the above is all we need to correctly work out scales, chords, and – by extension – also harmonizations. Mind that the root interval doesn’t have to be part of the list of intervals, that is simply the interval to start from based on the given key.

Giving a note as a starting point is not good enough since some scales simply don’t exist for some notes (e.g. G♯ major scale doesn’t exist in the major key, and G♭minor scale doesn’t exist in any minor key).

Before progressing to the implementation, please consider the following unit tests that should make sense to you:

func test_noteSequence_C_1() {
    let key: Key = .C
    let noteSequence = try! engine.noteSequence(customKey: key.associatedCustomKey,
                                                intervals: [._1, ._2maj, ._3maj, ._4, ._5, ._6maj, ._7maj])
    let expectedValue: NoteSequence = [.C, .D, .E, .F, .G, .A, .B]
    XCTAssertEqual(noteSequence, expectedValue)
}
    
func test_noteSequence_withRoot_C_3maj_majorScaleIntervals() {
    let key = Key.C
    let noteSequence = try! engine.noteSequence(customKey: key.associatedCustomKey,
                                                rootInterval: ._3maj,
                                                intervals: [._1, ._2maj, ._3maj, ._4, ._5, ._6maj, ._7maj])
    let expectedValue: NoteSequence = [.E, .Fs, .Gs, .A, .B, .Cs, .Ds]
    XCTAssertEqual(noteSequence, expectedValue)
}
    
func test_noteSequence_withRoot_Gsmin_3maj_alteredScaleIntervals() {
    let key = Key.Gs_min
    let noteSequence = try! engine.noteSequence(customKey: key.associatedCustomKey,
                                                rootInterval: ._3maj,
                                                intervals: [._1aug, ._2maj, ._3dim, ._4dim, ._5aug, ._6dim, ._7dim])
    let expectedValue: NoteSequence = [.Bs, .Cs, .Df, .Ef, .Fss, .Gf, .Af]
    XCTAssertEqual(noteSequence, expectedValue)
}

and here is the implementation. Let’s consider a simple case, so it’s easier to follow:

• key = C major
• root interval = 3maj
• interval = major scale interval (1, 2maj, 3min, 4, 5, 6maj, 7min)

if you music theory allowed you to understand the above unit tests, you would expect the output to be: E, F♯, G, A, B, C♯, D (which is a Dorian scale).

Steps:

1. we start by shifting the notes of the C key to position the 3rd degree (based on the 3maj) as the first element of the array, getting the note sequence E, F, G, A, B, C, D;
2. here’s the first interesting bit: we then get the list of intervals by calculating the number of semitones from the root to any other note in the sequence and working out the corresponding Interval:
   1_perfect, 2_minor, 3_minor, 4_perfect, 5_perfect, 6_minor, 7_minor;
3. we now have all we need to create a CustomKey which is pretty much a Key (with notes and intervals) but instead of being an enum with pre-defined values, is a struct;
4. here’s the second tricky part: return the notes by mapping the input intervals. Applying to each note in the custom key the accidental needed to match the desired interval. In our case, the only 2 intervals to ‘adjust’ are the 2nd and the 6th intervals, both minor in the custom key but major in the list of intervals. So we have to apply a sharp accidental to ‘correct’ them.

👀 I’ve used force unwraps in these examples for simplicity, the code might already look complex by itself.

class CoreEngine {

    func noteSequence(customKey: CustomKey,
                      rootInterval: Interval = ._1,
                      intervals: [Interval]) throws -> NoteSequence {
        // 1.
        let noteSequence = customKey.shiftedNotes(by: rootInterval.degree)
        let firstNoteInShiftedSequence = noteSequence.first!
        
        // 2.
        let adjustedIntervals = try noteSequence.enumerated().map {
            try interval(from: firstNoteInShiftedSequence,
                         to: $1,
                         targetDegree: Degree(rawValue: $0)!)
        }
        
        // 3.
        let customKey = CustomKey(notes: noteSequence,
                                  intervals: adjustedIntervals)
        
        // 4.
        return try intervals.map {
            let referenceInterval = customKey.firstIntervalWithDegree($0.degree)!
            let note = customKey.notes[$0.degree.rawValue]
            let accidental = try referenceInterval.type.accidental(to: $0.type)
            return try note.noteByApplyingAccidental(accidental)
        }
    }
}

It’s worth showing the implementation of the methods used above:

private func numberOfSemitones(from sourceNote: Note,
                               to targetNote: Note) -> Int {
    let notesGroupedBySameTone: [[Note]] = [
        [.C, .Bs, .Dff],
        [.Cs, .Df, .Bss],
        [.D, .Eff, .Css],
        [.Ds, .Ef, .Fff],
        [.E, .Dss, .Ff],
        [.F, .Es, .Gff],
        [.Fs, .Ess, .Gf],
        [.G, .Fss, .Aff],
        [.Gs, .Af],
        [.A, .Gss, .Bff],
        [.As, .Bf, .Cff],
        [.B, .Cf, .Ass]
    ]
        
    let startIndex = notesGroupedBySameTone.firstIndex { $0.contains(sourceNote)}!
    let endIndex = notesGroupedBySameTone.firstIndex { $0.contains(targetNote)}!
        
    return endIndex >= startIndex ? endIndex - startIndex : (notesGroupedBySameTone.count - startIndex) + endIndex
}
    
private func interval(from sourceNote: Note,
                      to targetNote: Note,
                      targetDegree: Degree) throws -> Interval {
    let semitones = numberOfSemitones(from: sourceNote, to: targetNote)
        
    let targetType: IntervalType = try {
        switch targetDegree {
        case ._1, ._8:
            return .perfect
        ...
        case ._4:
            switch semitones {
            case 4:
                return .diminished
            case 5:
                return .perfect
            case 6:
                return .augmented
            default:
                throw CustomError.invalidConfiguration
        ...
        case ._7:
            switch semitones {
            case 9:
                return .minorMajorDiminished
            case 10:
                return .minor
            case 11:
                return .major
            case 0:
                return .minorMajorAugmented
            default:
                throw CustomError.invalidConfiguration
            }
        }
    }()
    return Interval(degree: targetDegree, type: targetType)
}

the Note‘s noteByApplyingAccidental method:

func noteByApplyingAccidental(_ accidental: Accidental) throws -> Note {
    let newAccidental = try self.accidental.apply(accidental)
    return Note(naturalNote: naturalNote, accidental: newAccidental)
}

and the Accidental‘s apply method:

func apply(_ accidental: Accidental) throws -> Accidental {
    switch (self, accidental) {
    ...
    case (.flat, .flatFlatFlat):
        throw CustomError.invalidApplicationOfAccidental
    case (.flat, .flatFlat):
        return .flatFlatFlat
    case (.flat, .flat):
        return .flatFlat
    case (.flat, .natural):
        return .flat
    case (.flat, .sharp):
        return .natural
    case (.flat, .sharpSharp):
        return .sharp
    case (.flat, .sharpSharpSharp):
        return .sharpSharp
            
    case (.natural, .flatFlatFlat):
        return .flatFlatFlat
    case (.natural, .flatFlat):
        return .flatFlat
    case (.natural, .flat):
        return .flat
    case (.natural, .natural):
        return .natural
    case (.natural, .sharp):
        return .sharp
    case (.natural, .sharpSharp):
        return .sharpSharp
    case (.natural, .sharpSharpSharp):
        return .sharpSharpSharp   
    ...
}

With the above engine ready (and 💯﹪ unit tested!), we can now proceed to use it to work out what we ultimately need (scales, chords, and harmonizations).

extension CoreEngine {
    func scale(note: Note, scaleIdentifier: Identifier) throws -> NoteSequence {...}
    func chord(note: Note, chordIdentifier: Identifier) throws -> NoteSequence {...}
    func harmonization(key: Key, harmonizationIdentifier: Identifier) throws -> NoteSequence {...}
    func chordSignatures(note: Note, scaleHarmonizationIdentifier: Identifier) throws -> [ChordSignature] {...}
    func harmonizations(note: Note, scaleHarmonizationIdentifier: Identifier) throws -> [NoteSequence] {...}
}

Conclusions

There’s more to it but with this post I only wanted to outline the overall idea.

The default database is available on GitHub at albertodebortoli/iHarmonyDB. The format used is JSON and the community can now easily suggest additions.

Here is how the definition of a scale looks:

"scale_dorian": {
    "group": "group_scales_majorModes",
    "isMode": true,
    "degreeRelativeToMain": 2,
    "inclination": "minor",
    "intervals": [
        "1",
        "2maj",
        "3min",
        "4",
        "5",
        "6maj",
        "7min"
    ]
}

and a chord:

"chord_diminished": {
    "group": "group_chords_diminished",
    "abbreviation": "dim",
    "intervals": [
        "1",
        "3min",
        "5dim"
    ]
}

and a harmonization:

"scaleHarmonization_harmonicMajorScale4Tones": {
    "group": "group_harmonization_harmonic_major",
    "inclination": "major",
    "harmonizations": [
        "harmonization_1_major7plus",
        "harmonization_2maj_minor7dim5",
        "harmonization_3maj_minor7",
        "harmonization_4_minor7plus",
        "harmonization_5_major7",
        "harmonization_6min_major7plus5sharp",
        "harmonization_7maj_diminished7"
    ]
}

Have to say, I’m pretty satisfied with how extensible this turned out to be.

Thanks for reading 🎶