Implement fold (or reduce) for Tree

[jsbean]

There are now several methods that traverse over a Tree while holding over some accumulator.

It could be worthwhile to implement:

func reduce <U> (_ initial: U, _ nextPartial: (U, T) -> U) -> U

[mossheim]

Confused about how to do this correctly.. what is the type of T above? Tree? Then it seems hard to do without hitting infinite recursion:

    public func reduce <A> (_ initial: A, _ nextPartial: (A, Tree) -> A) -> A {
        switch self {
        case .leaf(let value):
            return nextPartial(initial, self)
        case .branch(let value, let trees):
            ???
        }
    }

This also seems overly complicated as it forces you to write nextPartial with a switch every time.

is it Either<Leaf, Branch>? Couldn't get this to compile.

Furthermore, should it be inorder, preorder, postorder...?

[mossheim]

Aha!

    public func reduce <A> (_ initial: A, _ nextPartial: (A, Tree) -> A) -> A {
        switch self {
        case .leaf(_):
            return nextPartial(initial, self)
        case .branch(_, let trees):
            return nextPartial(trees.reduce(initial) { $1.reduce($0, nextPartial) }, self)
        }
    }

[mossheim]

That's a postorder version. The others are not too hard to write. I guess it doesn't really matter anyway.

[mossheim]

Still, I feel like it should be a goal to specialize extension Tree where Branch == Leaf

[mossheim]

extension Tree where Branch == Leaf {
    public func reduceValues <A> (_ initial: A, _ nextPartial: (A, Leaf) -> A) -> A {
        switch self {
        case .leaf(let value):
            return nextPartial(initial, value)
        case .branch(let value, let trees):
            return nextPartial(trees.reduce(initial) { $1.reduce($0, nextPartial) }, value)
        }
    }
}

[mossheim]

    func testReduceBranchEqLeaf() {
        let a = Tree.branch(5, [
            .leaf(1),
            .branch(2, [
                .leaf(2),
                .leaf(3)
            ]),
            .leaf(4)
        ])

        let expected = 17

        XCTAssertEqual(a.reduceValues(0, +), expected)
    }

without changing the function name, swiftc couldn't infer types. This is pretty damn cool. How I've missed FP...