Avatar of mbraak

mbraak's solution

to List Ops in the TypeScript Track

Published at Dec 29 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Implement basic list operations.

In functional languages list operations like length, map, and reduce are very common. Implement a series of basic list operations, without using existing functions.

Setup

Go through the setup instructions for TypeScript to install the necessary dependencies:

http://exercism.io/languages/typescript

Requirements

Install assignment dependencies:

$ yarn install

Making the test suite pass

Execute the tests with:

$ yarn test

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

list-ops.test.ts

import List from './list-ops'

describe('append entries to a list and return the new list', () => {
    it('empty lists', () => {
        const list1 = new List()
        const list2 = new List()
        expect(list1.append(list2)).toEqual(new List())
    })

    xit('empty list to list', () => {
        const list1 = new List([1, 2, 3, 4])
        const list2 = new List<number>()
        expect(list1.append(list2)).toEqual(list1)
    })

    xit('non-empty lists', () => {
        const list1 = new List([1, 2])
        const list2 = new List([2, 3, 4, 5])
        expect(list1.append(list2).values).toEqual([1, 2, 2, 3, 4, 5])
    })
})

describe('concat lists and lists of lists into new list', () => {
    xit('empty list', () => {
        const list1 = new List()
        const list2 = new List()
        expect(list1.concat(list2).values).toEqual([])
    })

    xit('list of lists', () => {
        const list1 = new List([1, 2])
        const list2 = new List([3])
        const list3 = new List([])
        const list4 = new List([4, 5, 6])
        expect(list1.concat(list2).concat(list3).concat(list4).values).toEqual([1, 2, 3, 4, 5, 6])
    })
})

describe('filter list returning only values that satisfy the filter function', () => {
    xit('empty list', () => {
        const list1 = new List([])
        expect(list1.filter((el: number) => el % 2 === 1).values).toEqual([])
    })

    xit('non empty list', () => {
        const list1 = new List([1, 2, 3, 5])
        expect(list1.filter((el: number) => el % 2 === 1).values).toEqual([1, 3, 5])
    })
})

describe('returns the length of a list', () => {
    xit('empty list', () => {
        const list1 = new List()
        expect(list1.length()).toEqual(0)
    })

    xit('non-empty list', () => {
        const list1 = new List([1, 2, 3, 4])
        expect(list1.length()).toEqual(4)
    })
})

describe('returns a list of elements whose values equal the list value transformed by the mapping function', () => {
    xit('empty list', () => {
        const list1 = new List()
        expect(list1.map((el: number) => ++el).values).toEqual([])
    })

    xit('non-empty list', () => {
        const list1 = new List([1, 3, 5, 7])
        expect(list1.map((el: number) => ++el).values).toEqual([2, 4, 6, 8])
    })
})

describe('folds (reduces) the given list from the left with a function', () => {
    xit('empty list', () => {
        const list1 = new List()
        expect(list1.foldl((acc: number, el: number) => el / acc, 2)).toEqual(2)
    })

    xit('division of integers', () => {
        const list1 = new List([1, 2, 3, 4])
        expect(list1.foldl((acc: number, el: number) => el / acc, 24)).toEqual(64)
    })
})

describe('folds (reduces) the given list from the right with a function', () => {
    xit('empty list', () => {
        const list1 = new List()
        expect(list1.foldr((acc: number, el: number) => el / acc, 2)).toEqual(2)
    })

    xit('division of integers', () => {
        const list1 = new List([1, 2, 3, 4])
        expect(list1.foldr((acc: number, el: number) => el / acc, 24)).toEqual(9)
    })
})

describe('reverse the elements of a list', () => {
    xit('empty list', () => {
        const list1 = new List()
        expect(list1.reverse().values).toEqual([])
    })

    xit('non-empty list', () => {
        const list1 = new List([1, 3, 5, 7])
        expect(list1.reverse().values).toEqual([7, 5, 3, 1])
    })
})
function fold<T, U>(fn: (acc: U, v: T) => U, l: T[], initial: U): U {
    let acc = initial;

    for (const v of l) {
        acc = fn(acc, v);
    }

    return acc;
}

function foldRight<T, U>(fn: (acc: U, v: T) => U, l: T[], initial: U): U {
    let acc = initial;

    for (let i = l.length - 1; i >= 0; i--) {
        const v = l[i];
        acc = fn(acc, v);
    }

    return acc;
}

function appendReducer<T>(l: T[], v: T): T[] {
    return l.concat(v);
}

function copyList<T>(l: T[]): T[] {
    return fold<T, T[]>(appendReducer, l, []);
}

function concatLists<T>(l1: T[], l2: T[]): T[] {
    return fold<T, T[]>(appendReducer, l2, copyList<T>(l1));
}

export default class List<T> {
    values: T[];

    constructor(values?: T[]) {
        this.values = values || [];
    }

    append(list: List<T>): List<T> {
        const { values } = this;

        this.values = concatLists(values, list.values).sort();

        return this;
    }

    concat(list: List<T>): List<T> {
        const { values } = this;

        return new List(concatLists(values, list.values).sort());
    }

    filter(fn: (v: T) => boolean): List<T> {
        const { values } = this;

        this.values = fold(
            (l: T[], v: T) => (fn(v) ? l.concat(v) : l),
            values,
            []
        );

        return this;
    }

    length(): number {
        const { values } = this;

        return fold((n: number) => n + 1, values, 0);
    }

    map(fn: (v: T) => T): List<T> {
        const { values } = this;

        this.values = fold((l: T[], v: T) => l.concat(fn(v)), values, []);

        return this;
    }

    foldl(fn: (acc: T, v: T) => T, acc: T): T {
        const { values } = this;

        return fold(fn, values, acc);
    }

    foldr(fn: (acc: T, v: T) => T, acc: T): T {
        const { values } = this;

        return foldRight<T, T>(fn, values, acc);
    }

    reverse(): List<T> {
        const { values } = this;

        return new List<T>(foldRight<T, T[]>(appendReducer, values, []));
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?