combinatorics!

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

foo :: Integer
foo = 3

factorial :: Integer -> Integer
factorial n = product [1..n]

choose :: Integer -> Integer -> Integer
choose n k =
    factorial n `div` factorial k `div` factorial (n-k)

squaresInGrid :: Integer -> Integer
squaresInGrid n = sum [i^2 | i <- [1..8]]

squaresInGrid' :: Integer -> Integer
squaresInGrid' n = sum (map (^2) [1..n])

-- 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
fibo2 :: Integer -> (Integer, Integer)
fibo2 0 = (0,1)
fibo2 n = let (x,y) = fibo2 (n - 1) in (y, x+y)

-- 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 recursive way that uses Haskell's laziness. Can you figure out how
-- it works?

-- 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 :: [Integer]
fiboList = 0 : 1 : zipWith (+) fiboList (tail fiboList)

-- (!!) just indexes into the list (indexes start from 0). For example
-- [11,22,33] !! 1 = 22.
fibo3 :: Int -> Integer
fibo3 i = fiboList !! i

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 <- perms 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.

------------------------------------------------------------------------
-- 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]))

-- There's a 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".

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

-- 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 = do
    d1 <- [1..6]
    d2 <- [1..6]
    d3 <- [1..6]
    d4 <- [1..6]
    d5 <- [1..6]
    return [d1,d2,d3,d4,d5]


-- (.) 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