Lab 1 (50 points)

Download the skeleton file FPWarmup.elm and use it as a starting point for the following problems. Look for all occurrences of TODO in comments, which point out where you should implement your solutions. Once you are done, follow the submission instructions below.

Problem 1: FP Warmup

The goal of this problem is to develop experience with basic functional programming tasks in Elm.

1.1.1 (10 points)

Write a function

digitsOfInt : Int -> List Int

such that digitsOfInt n returns [] if n is less than zero, and returns the list of digits of n in the order in which they appear. Once you have implemented the function, you should get the following behavior at the Elm REPL:

> import FPWarmup exposing (..)

> digitsOfInt 3124
[3,1,2,4] : List Int

> digitsOfInt 352663
[3,5,2,6,6,3] : List Int

> digitsOfInt 0
[0] : List Int

1.1.2 (15 points)

Consider the process of taking a number, adding its digits, then adding the digits of the number derived from it, etc., until the remaining number has only one digit. The number of additions required to obtain a single digit from a number n is called the additive persistence of n, and the digit obtained is called the digital root of n. For example, the sequence obtained from the starting number 9876 is 9876, 30, 3, so 9876 has an additive persistence of 2 and a digital root of 3.

Write two Elm functions

additivePersistence : Int -> Int
digitalRoot : Int -> Int 

that take positive integer arguments n and, respectively, return the additive persistence and the digital root of n. Once you have implemented the functions, you should get the following behavior at the Elm REPL:

> additivePersistence 9876
2 : Int

> digitalRoot 9876
3 : Int

Think about how you can factor the implementations of these two functions into common, reusable parts.

1.1.3 (15 points)

NOTE: Minor changes in sample output below, as discussed on Piazza.

Write a function

subsequences : List a -> List (List a)

that computes all subsequences of a list. This function is analogous to the powerset of a set. Your implementation may return subsequences in any order. For example, the following are two answers, among others, that are correct:

> subsequences (List.range 1 3)
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] : List (List Int)

> subsequences (List.range 1 3)
[[1,2,3],[2,3],[1,3],[3],[1,2],[2],[1],[]] : List (List Int)

1.1.4 (10 points)

The List library function includes a take such that take k xs returns the first k elements of xs. If k is negative or if there are not enough elements in xs, take quietly succeeds anyway.

In this problem, you will write a version of take that differentiates between the success and error cases using the Result type. Implement the function

take : Int -> List a -> Result String (List a)

so that it returns the error strings "not enough elements" and “negative index” in the corresponding error cases. For example:

> take 0 (List.range 1 9)
Ok [] : Result.Result String (List Int)

> take 5 (List.range 1 9)
Ok [1,2,3,4,5] : Result.Result String (List Int)

> take 10 (List.range 1 9)
Err "not enough elements" : Result.Result String (List Int)

> take (-10) (List.range 1 9)
Err "negative index" : Result.Result String (List Int)

Grading and Submission Instructions

Submit the following one file:

  • The file FPWarmup.elm updated with your changes. You are free to modify these files as you wish, as long as you do not change any type signatures that are provided.

Your solution will be graded using a combination of automated grading scripts and manual review. It is a good idea for you to design some test cases of your own to exercise more sample behaviors than just the ones provided in the writeup. We also reserve the right to take into account the organization and style of your code when assigning grades.

If you are not able to finish all parts of the assignment, make sure that all of your submitted files compile successfully. If not, you risk getting zero points for the assignment. In particular, for each file Foo.elm, make sure that it can be loaded into the Elm REPL

% elm-repl
> import Foo

and that it can be compiled to a standalone HTML file:

% elm-make Foo.elm --output=Foo.html
Successfully generated Foo.html