Railway Pattern

Question 1

To implement these classes and methods, just “convert” the Haskell definitions to Python code. Note that Validation is not a monad.

from typing import Any
from dataclasses import dataclass

class List:
    @staticmethod
    def pure(x): return Node(x, Empty())

    # Convenience method for Question 3
    @staticmethod
    def from_list(ls):
        match ls:
            case []: return Empty()
            case x, *xs: return Node(x, List.from_list(xs))

@dataclass
class Node(List):
    head: object
    tail: List

    def map(self, f):
        return Node(f(self.head), self.tail.map(f))

    def ap(self, x):
        tails = self.tail.ap(x)
        heads = Node._ap(self.head, x)
        return heads.concat(tails)

    # helper method
    @staticmethod
    def _ap(f, xs):
        match xs:
            case Empty(): return Empty()
            case Node(l, r): return Node(f(l), Node._ap(f, r))

    def concat(self, xs):
        return Node(self.head, self.tail.concat(xs))

    def flatMap(self, f):
        return f(self.head).concat(self.tail.flatMap(f))

@dataclass
class Empty(List):
    def map(self, f): return self
    def concat(self, xs): return xs
    def ap(self, x): return self
    def flatMap(self, f): return self

class Maybe:
    @staticmethod
    def pure(x): return Just(x)

@dataclass
class Just(Maybe):
    val: object

    def map(self, f): return Just(f(self.val))

    def ap(self, x):
        match x:
            case Just(y): return Just(self.val(y))
            case Nothing(): return x

    def flatMap(self, f): return f(self.val)

@dataclass
class Nothing:
    def map(self, f): return self
    def ap(self, x): return self
    def flatMap(self, f): return self

class Either:
    @staticmethod
    def pure(x): return Right(x)

@dataclass
class Left(Either):
    inl: object
    def map(self, f): return self
    def ap(self, f): return self
    def flatMap(self, f): return self

@dataclass
class Right(Either):
    inr: object

    def map(self, f): return Right(f(self.inr))

    def ap(self, f):
        match f:
            case Left(e): return f
            case Right(x): return Right(self.inr(x))

    def flatMap(self, f): return f(self.inr)

class Validation:
    @staticmethod
    def pure(x): return Success(x)

@dataclass
class Success:
    val: object

    def map(self, f): return Success(f(self.val))

    def ap(self, f):
        match f:
            case Failure(e): return f
            case Success(x): return Success(self.val(x))


@dataclass
class Failure:
    err: list[str]

    def map(self, f): return self

    def ap(self, f):
        match f:
            case Failure(err): return Failure(self.err + err)
            case Success(x): return self

Question 2

Question 2.1: Unsafe Sum

The Python implementation of sum_digits can be a Haskell rewrite of your sumDigits solution for Question 6 in Chapter 1.4 (Course Introduction#Exercises):

def sum_digits(n):
    return n if n < 10 else \
           n % 10 + sum_digits(n // 10)

Question 2.2: Safe Sum

The idea is to have sum_digits return a Maybe object. In particular, the function should return Nothing if n is negative, and Just x when n is positive and produces result x.

def sum_digits(n):
    return Nothing() if n < 0 else \
           Just(n)   if n < 10 else \
           sum_digits(n // 10).map(lambda x: x + n % 10)

sumDigits :: Int -> Maybe Int
sumDigits n
  | n < 0 = Nothing
  | n < 10 = Just n
  | otherwise = (n `mod` 10 +) <$> sumDigits (n `div` 10)

Question 2.3: Final Sum

The result of sum_digits is a Maybe[int], and sum_digits itself has type int -> Maybe[int]. To compose sum_digits with itself we can use flatMap or >>=.

def final_sum(n):
    n = sum_digits(n)
    return n.flatMap(lambda n2: n2 if n2 < 10 else final_sum(n2))

finalSum :: Int -> Maybe Int
finalSum n = do
  n' <- sumDigits n
  if n' < 10
  then Just n'
  else finalSum n'

Question 3

Question 3.1: Splitting Strings

split in Python can be implemented with the str.split method. The split function for Haskell is shown in Chapter 4.4 (Railway Pattern#Validation).

# Uses the convenience method from_list in the List class
def split(char, s):
    return List.from_list(s.split(char))

Question 3.2: CSV Parsing

Split the string over \n, then split each string in that list over , using map:

def csv(s):
    return split('\n', s)
                .map(lambda x: split(',', x))

csv :: String -> [[String]]
csv s = split ',' <$> (split '\n' s)

Question 4

Question 4.1: Factorial

Should be boring at this point.

def factorial(n):
    return 1 if n <= 1 else \
           n * factorial(n - 1)

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

Question 4.2: Safe Factorial

The idea is to return a Left if n is negative, Right with the desired result otherwise. Typically, Right is the happy path.

def factorial(n, name):
    if n < 0:
        return Left(name + ' cannot be negative!')
    if n <= 1:
        return Right(1)
    return factorial(n - 1, name).map(lambda x: x * n)

factorial :: Int -> String -> Either String Int
factorial n name
  | n < 0 = Left $ name ++ " cannot be negative!"
  | n <= 1 = Right 1
  | otherwise = (n*) <$> factorial (n - 1) name

Question 4.3: Safe n choose k

Idea: Compute , and in “parallel”, combine with ap:

def choose(n, k):
    nf = factorial(n, 'n')
    kf = factorial(k, 'k')
    nmkf = factorial(n - k, 'n - k')
    div = lambda x: lambda y: lambda z: x // y // z
    return nf.map(div).ap(kf).ap(nmkf)

choose :: Int -> Int -> Either String Int
choose n k
    = let nf   = factorial n "n"
          kf   = factorial k "k"
          nmkf = factorial (n - k) "n - k"
          f x y z = x `div` y `div` z
      in f <$> nf <*> kf <*> nmkf

With the ApplicativeDo language extension enabled, you can just use do notation:

{-# LANGUAGE ApplicativeDo #-}
choose :: Int -> Int -> Either String Int
choose n k = do
  nf <- factorial n "n"
  kf <- factorial k "k"
  nmkf <- factorial (n - k) "n - k"
  return $ nf `div` kf `div` nmkf

Question 4.4

Redefine factorial to use Validation instead of Either:

def factorial(n, name):
    if n < 0:
        return Failure([f'{name} cannot be negative!'])
    if n <= 1:
        return Success(1)
    else:
        return factorial(n - 1, name).map(lambda x: n * x)

factorial :: Int -> String -> Validation [String] Int
factorial n name
  | n < 0 = Failure [name ++ " cannot be negative!"]
  | n <= 1 = Success 1
  | otherwise = (n*) <$> factorial (n - 1) name

Finally, update the type signature of choose (we do not need to do so in Python).

choose :: Int -> Int -> Validation [String] Int
choose n k = do
  nf <- factorial n "n"
  kf <- factorial k "k"
  nmkf <- factorial (n - k) "n - k"
  return $ nf `div` kf `div` nmkf