Enumerative Combinatorics with Haskell, Splash 2017

c.hs

import Control.Monad
import Data.List

-- Haskell comments look like this, lines that start with two hyphens.

{- You can also write range comments like this. -}

-- We did not write the type annotations (lines with ::) during class, and in
-- fact if you delete them Haskell will supply (more general) type signatures.
-- You can see what type Haskell thinks the things we've defined are by running
-- :t in GHCi, like typing this after the prompt
--
-- Prelude> :l c
-- *Main> :t factorial

factorial :: Integer -> Integer
-- factorial x = product [1..x]
factorial 0 = 1
factorial n = n * factorial (n-1)

choose :: Integer -> Integer -> Integer
-- choose n k = if n < 0 then error "n should be positive" else factorial n `div` factorial k `div` factorial (n-k)
choose n k
    | n < 0 = error "n should be nonnegative"
    | k < 0 = error "k should be nonnegative"
    | k > n = error "k should be <= n"
    | otherwise = factorial n `div` factorial k `div` factorial (n-k)

foo :: Integer
foo = 12345

-- Naive definition of Fibonacci numbers: really slow
fibo :: Integer -> Integer
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n - 1) + fibo (n - 2)

-- One-pass linear recurrence definition of Fibonacci numbers: decent
--      i = 0, 1, 2, 3, 4, 5, 6, 7 , 8,  ...
-- fibo i = 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
-- (0, 1) -> (1, 1) -> (
-- fibo2 k = (kth fibo number, (k+1)th fibo number)
fibo2 0 = (0, 1)
fibo2 n = let (x, y) = fibo2 (n-1) in (y, x + y)
-- if n = 8
-- then x = 13
-- and y = 21

-- There are even faster, tricker ways to calculate fibo, e.g. you can
-- calculate fibo (2*n) quickly in terms of fibo n and fibo (n + 1). But here's
-- a tricky and recursive but (IMO) elegant way that uses Haskell's laziness:

-- zipWith takes a function and two lists, applies the function to elements at
-- the same positions in the lists, and returns a list of the results. For
-- example, zipWith (+) [1,2,3] [10,20,30] = [11,22,33].

-- tail returns all but the first element of the list. For example,
-- tail [11,22,33,44] = [22,33,44].
fiboList = 0 : 1 : zipWith (+) fiboList (tail fiboList)

-- (!!) just indexes into the list (indexes start from 0). For example
-- [12,34,56] !! 0 = 12
-- [12,34,56] !! 1 = 34
-- [12,34,56] !! 2 = 56
-- [12,34,56] !! 3 = <error>
fibo3 :: Int -> Integer
fibo3 i = fiboList !! i

-- We can implement our own higher-order functions:
mymap :: (a -> b) -> [a] -> [b]
mymap f [] = []
mymap f (x:xs) = f x : mymap f xs

sum' :: [Integer] -> Integer
sum' [] = 0
sum' (x:xs) = x + sum' xs

spliceOne :: [a] -> [(a,[a])]
spliceOne [] = []
spliceOne (x:xs) = (x, xs) : [(y, x:ys) | (y, ys) <- spliceOne xs]

perms :: [a] -> [[a]]
perms [] = [[]]
perms xs = [y : p | (y, ys) <- spliceOne xs, p <- permutations ys]

-- Note: Haskell has a function called "permutations" in Data.List, which also
-- lists all permutations of a list (albeit in a different order).
-- To use functions from the module, you can type
--
-- import Data.List
--
-- at the top of Haskell code (as I have done here) or in GHCi.


-- There are a few different way to write computations that are sort of like
-- list comprehensions, that also let you harness the powerful Haskell
-- abstraction known as a "monad". This abstraction lets us write, for example,
-- "replicateM" to repeat an "action", which for our purposes, choses multiple
-- elements from a list with replacement.

-- We also take this opportunity to show the smaller integer data type Int.
-- It's fine since we're only representing dice faces from 1 to 6 with it.

rollFiveDice :: [[Int]]
-- rollFiveDice = [[d1, d2, d3, d4, d5] | d1 <- [1..6], d2 <- [1..6], d3 <- [1..6], d4 <- [1..6], d5 <- [1..6]]
--
rollFiveDice = replicateM 5 [1..6]

------------------------------------------------------------------------
-- BONUS CODE
------------------------------------------------------------------------

-- How many permutations a1,a2,...,a10 are there such that
-- a1 > a2 < a3 > a4 < a5 and so on?
-- These permutations are called *alternating*.

-- Can you understand how this recursive definition works?
-- Note (:) is right-associative, so
-- (x:y:z:[1,2,3]) = (x:(y:(z:[1,2,3]))) = [x,y,z,1,2,3].

isAlternating :: [Integer] -> Bool
isAlternating [] = True
isAlternating [x] = True
isAlternating [x,y] = x > y
isAlternating (x:y:z:xs) = x > y && y < z && isAlternating (z:xs)

-- filter is the second most common higher-order function. Try
-- evaluating filter (>5) [0..10] or filter even [1..10]. Can
-- you figure out what it does?

-- The number of alternating permutations of [1..n] is called
-- the nth Euler number.

-- There are 50521 alternating permutations of [1..10]. Of
-- course, this is an extremely brute-force way of calculating
-- it. Can you figure out a better way?

eulerNumber :: Integer -> Integer
eulerNumber n = genericLength (filter isAlternating (perms [1..n]))

-- How many ways are there to roll five distinct dice and get a total of at
-- least 22?

-- (.) is the function composition operator. ((>= s) . sum) means the function
-- that first sums its argument, and then tests if the sum is >= s.
--
-- ($) is the function application operator. It sounds silly because function
-- application is already the most basic thing you do in Haskell just by
-- writing "a b" to apply function a to argument b. However, ($) has extremely
-- low precedence, so we often use it to avoid writing parentheses. The below
-- line is equivalent to these:
--
-- fiveDiceAtLeast s = (length) $ (filter ((>= s) . sum) rollFiveDice)
-- fiveDiceAtLeast s = (length) (filter ((>= s) . sum) rollFiveDice)
-- fiveDiceAtLeast s = length (filter ((>= s) . sum) rollFiveDice)
fiveDiceAtLeast :: Int -> Int
fiveDiceAtLeast s = length $ filter ((>= s) . sum) rollFiveDice

-- Remember how Haskell is strongly typed? If you try to do a computation that
-- definitely results in an integer, like length, and then use the result in a
-- division, you'll get an error. fromIntegral converts the integer to a
-- different number type (Haskell infers what type you want) so that the
-- division is acceptable. (On the other hand, a number like 6 can be an
-- integer or a floating-point number depending on context.)
fiveDiceAtLeastProb :: Int -> Double
fiveDiceAtLeastProb s = fromIntegral (fiveDiceAtLeast s) / 6^5

-- For an even more generic version, replicateM repeats a "monadic action" some
-- number of times and collects all the results into a list. The "monadic
-- action" in this case is just "choose a value from [1..6]".
rollDice :: Int -> [[Int]]
rollDice reps = replicateM reps [1..6]

diceAtLeast :: Int -> Int -> Int
diceAtLeast n s = length . filter ((>= s) . sum) $ rollDice n

diceAtLeastProb :: Int -> Int -> Double
diceAtLeastProb n s = fromIntegral (diceAtLeast n s) / 6^n