Exercise 8.1: Solve problems with map, reduce and filter

Here is a series of simple tasks which you could easily solve with a for-loop in most cases. However the challenge here is to solve the problems without using a for-loop and instead use one of the mapreduce and filter functions.

Exercise 8.1a: Add numbers

Implement sumup(xs) which adds up all the numbers in an iterable collection xs. It should be usable like the builtin sum function.

function sumup(xs)
using Test
@testset "sumup tests" begin
	@test sumup([1, 1, 1]) == 3
  @test sumup(1:4) == 10
  @test sumup(4) == 4
blackcore (Julia)
sumup (generic function with 1 method)

Exercise 8.1b: Factorial

Implement fac(n) which calculates the factorial of the number n. The factorial of 6 is 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720, while the factorial of 3 is 3! = 3 * 2 * 1 = 6.

function fac(n)
using Test
@testset "fac tests" begin
	@test fac(3) == 6
  @test fac(6) == 720
  @test fac(0) == 1
blackcore (Julia)
DefaultTestSet("fac tests", Any[], 3, false)

Exercise 8.1c: Find length of longest word

Define longest(strings) to find the length of the string in the collection of strings called strings.

function longest(strings)
using Test
@testset "finding longest word tests" begin
	@test longest(["one"]) == 3
  @test longest(["one", "two", "three"]) == 5
  @test longest(["twelve", "two", "three"]) == 6  
blackcore (Julia)
DefaultTestSet("finding longest word tests", Any[], 3, false)

Exercise 8.2: Implement the zip function

The zip function appears in many functional languages and also exists in the Julia standard library. It is used to combine two or more separate lists of objects into a single list of composite objects, such as a tuple.

Julia's zip can work with any number of iterable collections but we want to make a simplified version called combine which takes two collections and combine them to one.

function combine(xs, ys)
using Test
@testset "combine tests" begin
	@test combine(1:3, 'a':'c') == collect(zip(1:3, 'a':'c'))
  @test combine([4, 8, 10], ["foo", "bar", "qux"]) == collect(zip([4, 8, 10], ["foo", "bar", "qux"]))
  @test_throws DimensionMismatch("dimensions must match") combine([4, 8, 10], ["foo", "bar"])
blackcore (Julia)
DefaultTestSet("combine tests", Any[], 3, false)

Exercise 8.3: Implement a "zip with" function

In some functional languages there is a function called zipwith which is a more generic version of zip. It lets you specify the function which should combine two elements.

function zipwith(f, xs, ys)
using Test
@testset "zipwith tests" begin
	@test zipwith(tuple, [4, 8, 10], ["foo", "bar", "qux"]) == [
    (4, "foo"), 
    (8, "bar"), 
    (10, "qux")]
  @test zipwith(=>, [4, 8, 10], ["foo", "bar", "qux"]) == [
    4 => "foo", 
    8 => "bar",  
    10 => "qux"]
  @test zipwith(+, 1:4, ones(Int, 4)) == [2, 3, 4, 5]
blackcore (Julia)
DefaultTestSet("zipwith tests", Any[], 3, false)

Exercise 8.4: Reverse Polish Notation Calculator

Reverse polish notation is a way of expressing calculations which does not require parentesis to express the order of computations. Calculations are based on having a stack of inputs values and operations.

It is easiest to explain with some examples. 3 + 4 in reverse polish notation (RPN) would be written as 3 4 +. Basically you list the numbers you want to do something with and then you specify the operation you want to do on them. This is beneficial in complex expressions.

(3 + 4) * 2
10*2 - 2 * (3 + 2)

These expressions would in RPN turn into:

3  4 + 2 *
10 2 * 2 3 2 + * -

Let us look at the first expression. We read from left to right.

  1. Start by putting 3 and 4 on the stack.

  2. When we encounter + we pop the two top elements from the stack which are 3 and 4 and add them. This gives 7, which is put on the top of the stack.

  3. Put 2 on the stack. The stack now looks like [7, 2]

  4. Encounter * operator. Pop top values from the stack and multiply them.

We end up with 14 as the result.

The following functions will be useful in this exercise:

  • vcat vertical concatenation of arrays. Remember regular 1D arrays in Julia are column vectors, hence stitching them together is vertical concatenation.

  • reduce Useful whenever you are processing a list of elements and want to turn them into one value.

  • ... splat operator. Turn an array, tuple etc into multiple function arguments.

input = [10, 4, 3, +, 2, *, -] # solve_rpn(input) should give -4 as answer
function solve_rpn(xs)
using Test
@testset "solve RPN tests" begin
	@test solve_rpn(input)  == [-4]
blackcore (Julia)
DefaultTestSet("solve RPN tests", Any[], 1, false)

Exercise 8.4b: Parse string input (tricky)

Imagine you are reading an expression directly from the command line or from a file. You will not get the input as a neat Julia array of numbers and operations. Instead you will get a string which you need to parse.

Add a method to solve_rpn which processes string input. In this case we need to be introduced to some new Julia functions:

  • Meta.parse this is different from parse which is just for parsing types. Meta.parse can parse any Julia expression, and turn it into Julia code. Or more specifically it will turn it into expressions made up of symbols and literals.

  • eval will take Julia code and evaluate it. So a symbol such as :+ will turn into the function object +. The number literal 4 will just turn into the number 4. Strings and numbers just evaluate to themselves.

function  solve_rpn(s::AbstractString)
@testset "solve RPN parsing tests" begin
	@test solve_rpn("3  4 +")  == [7]
  @test solve_rpn("3 4 + 2 *")  == [14]
  @test solve_rpn("10 4 3 + 2 * -")  == [-4]
blackcore (Julia)
DefaultTestSet("solve RPN parsing tests", Any[], 3, false)
Runtimes (1)