Railway Pattern
Question 1
Create the following ADTs in Python:
- A singly linked list
- A
Maybe-like type, with “constructors”JustandNothing - An
Either-like type, with “constructors”LeftandRight - A
Validation-like type, with “constructors”SuccessandFailure. Because Python does not have higher-kinds, you may assume thatFailures always hold a list of strings.
Then define methods on all these types so that they are all functors, applicatives and monads (Validation does not need to be a monad). fmap can be called map, <*> can be called ap, return can just be pure, and >>= can be called flatMap.
Due to Python’s inexpressive type system, you are free to omit type annotations.
Try not to look at Haskell’s definitions when doing this exercise to truly understand how these data structures work!
Example runs for each data structure follow:
Lists
# lists>>> my_list = Node(1, Node(2, Empty()))
# map>>> my_list.map(lambda x: x + 1)Node(2, Node(3, Empty()))
# pure>>> List.pure(1)Node(1, Empty())
# ap>>> Node(lambda x: x + 1, Empty()).ap(my_list)Node(2, Node(3, Empty()))
# flatMap>>> my_list.flatMap(lambda x: Node(x, Node(x + 1, Empty())))Node(1, Node(2, Node(2, Node(3, Empty()))))Maybe
>>> my_just = Just(1)>>> my_nothing = Nothing()
# map>>> my_just.map(lambda x: x + 1)Just(2)>>> my_nothing.map(lambda x: x + 1)Nothing()
# pure>>> Maybe.pure(1)Just(1)
# ap>>> Just(lambda x: x + 1).ap(my_just)Just(2)>>> Just(lambda x: x + 1).ap(my_nothing)Nothing()>>> Nothing().ap(my_just)Nothing()>>> Nothing().ap(my_nothing)Nothing()
# flatMap>>> my_just.flatMap(lambda x: Just(x + 1))Just(2)>>> my_nothing.flatMap(lambda x: Just (x + 1))Nothing()Either
>>> my_left = Left('boohoo')>>> my_right = Right(1)
# map>>> my_left.map(lambda x: x + 1)Left('boohoo')>>> my_right.map(lambda x: x + 1)Right(2)
# pure>>> Either.pure(1)Right(1)
# ap>>> Left('sad').ap(my_right)Left('sad')>>> Left('sad').ap(my_left)Left('sad')>>> Right(lambda x: x + 1).ap(my_right)Right(2)>>> Right(lambda x: x + 1).ap(my_left)Left('boohoo')
# flatMap>>> my_right.flatMap(lambda x: Right(x + 1))Right(2)>>> my_left.flatMap(lambda x: Right(x + 1))Left('boohoo')Validation
>>> my_success = Success(1)>>> my_failure = Failure(['boohoo'])
# map>>> my_failure.map(lambda x: x + 1)Failure(['boohoo'])>>> my_success.map(lambda x: x + 1)Right(2)
# pure>>> Validation.pure(1)Right(1)
# ap>>> Failure(['sad']).ap(my_success)Failure(['sad'])>>> Failure(['sad']).ap(my_failure)Failure(['sad', 'boohoo'])>>> Success(lambda x: x + 1).ap(my_success)Success(2)>>> Success(lambda x: x + 1).ap(my_failure)Failure(['boohoo'])Question 2
Question 2.1: Unsafe Sum
Recall Question 6 in Chapter 1 (Exercises) where we defined a function sumDigits in Haskell. Now write a function sum_digits(n) that does the same, i.e. sums the digits of a nonnegative integer
>>> sum_digits(1234)10>>> sum_digits(99999)45Your Haskell definition should also run similarly:
ghci> sumDigits 123410ghci> sumDigits 9999945Question 2.2: Safe Sum
Try entering negative integers as arguments to your functions. My guess is that something bad happens.
Let us make sum_digits safe. Re-define sum_digits so that we can drop the assumption that Maybe context to keep our function pure. Use the Maybe data structure that you have defined from earlier for the Python version, and use Haskell’s built-in Maybe to do so. Example runs follow:
>>> sum_digits(1234)Just(10)>>> sum_digits(99999)Just(45)>>> sum_digits(-1)Nothingghci> sumDigits 1234Just 10ghci> sumDigits 99999Just 45ghci> sumDigits (-1)NothingQuestion 2.3: Final Sum
Now define a function final_sum(n) that repeatedly calls sum_digit until a single-digit number arises. Just like your safe implementation of sum_digit, final_sum should also be safe. Example runs follow:
>>> final_sum(1234)Just(1)>>> final_sum(99999)Just(9)>>> final_sum(-1)Nothing()ghci> finalSum 1234Just 1ghci> finalSum 99999Just 9ghci> finalSum (-1)NothingQuestion 3
Question 3.1: Splitting Strings
Define a function split that splits a string delimited by a character. This is very similar to s.split(c) in Python. However, the returned result should be a singly-linked list—in Python, this would be the singly-linked-list implementation you defined in Question 1, and in Haskell, this would be just [String].
Example runs follow:
>>> split('.', 'hello. world!. hah')Node('hello', Node(' world!', Node(' hah', Empty())))>>> split(' ', 'a b')Node('this', Node('', Node('', Node('is', Empty()))))ghci> split '.' "hello. world!. hah"["hello"," world!"," hah"]ghci> split ' ' "a b"["a","","","b"]Question 3.2: CSV Parsing
The Python csv library allows us to read CSV files to give us a list of rows, each row being a list of cells, and each cell is a string. Our goal is to do something similar using the list data structure.
A CSV-string is a string where each row is separated by \n, and in each row, each cell is separated by ,. Our goal is to write a function csv that receives a CSV-string and puts all the cells in a two-dimensional list. Example runs follow.
>>> csv('a,b,c\nd,e\nf,g,h')Node(Node('a', Node('b', Node('c', Empty()))),Node(Node('d', Node('e', Empty())),Node(Node('f', Node('g', Node('h', Empty()))),Empty())))ghci> csv "a,b,c\nd,e\nf,g,h"[["a","b","c"],["d","e"],["f","g","h"]]Question 4
The formula gamblingprobability and statistics, combinatorics etc. The way to compute
Question 4.1: Factorial
Clearly, being able to compute factorials would make computing factorial that computes the factorial of a nonnegative integer. Do so in Python and Haskell. Example runs follow.
>>> factorial(4)24>>> factorial(5)120ghci> factorial 424ghci> factorial 5120Question 4.2: Safe Factorial
Just like we have done in Question 2, our goal is to make our functions safer! Re-define factorial so that we can drop the assumption that the integer is nonnegative. In addition, your function should receive the name of a variable so that more descriptive error messages can be emitted. Use the Either type. Again, do so in Python and Haskell. Example runs follow:
>>> factorial(4, 'n')Right(24)>>> factorial(5, 'k')Right(120)>>> factorial(-1, 'n')Left('n cannot be negative!')>>> factorial(-1, 'k')Left('k cannot be negative!')ghci> factorial 4 "n"Right 24ghci> factorial 5 "k"Right 120ghci> factorial (-1) "n"Left "n cannot be negative!"ghci> factorial (-1) "k"Left "k cannot be negative!"Question 4.3: Safe n choose k
Now let us use factorial to define factorial functions to define a function choose that receives integers
>>> choose(5, 2)Right(10)>>> choose(-1, -3)Left('n cannot be negative!')>>> choose(1, -3)Left('k cannot be negative!')>>> choose(3, 6)Left('n - k cannot be negative!')ghci> choose 5 2Right 10ghci> choose (-1) (-3)Left "n cannot be negative!"ghci> choose 1 (-3)Left "k cannot be negative!"ghci> choose 3 6Left "n - k cannot be negative!"Question 4.4: n choose k With Validation
Notice that several things could go wrong with Either, change the implementation of factorial so that it uses the Validation applicative instead. This is so that all the error messages are collected. Your choose function definition should not change, aside from its type. Example runs follow.
>>> choose(5, 2)Success(10)>>> choose(-1, -3)Failure(['n cannot be negative!', 'k cannot be negative!'])>>> choose(1, -3)Failure(['k cannot be negative!'])>>> choose(3, 6)Failure(['n - k cannot be negative!'])ghci> choose 5 2Success 10ghci> choose (-1) (-3)Failure ["n cannot be negative!","k cannot be negative!"]ghci> choose 1 (-3)Failure ["k cannot be negative!"]ghci> choose 3 6Failure ["n - k cannot be negative!"]