Category Archives: math

Average and median via optimization

Posted on June 8, 2021 by Brent

This is certainly not a new observation, and I’m sure it is folklore and/or contained in various textbooks, but it was amusing to derive it independently. Suppose we have a finite set of real numbers , and we want to … Continue reading →

Posted in math | Tagged , , , , | 1 Comment

What would Dijkstra do? Proving the associativity of min

Posted on February 23, 2020 by Brent

This semester I’m teaching a Discrete Mathematics course. Recently, I assigned them a homework problem from the textbook that asked them to prove that the binary operator on the real numbers is associative, that is, for all real numbers , … Continue reading →

Posted in math | Tagged , , , , , , | 16 Comments

What’s the right way to QuickCheck floating-point routines?

Posted on February 24, 2019 by Brent

I got a lot of great comments on my previous post about finding roots of polynomials in Haskell. One particularly promising idea I got from commenter Jake was to give up on the idea of having no external dependencies (which, … Continue reading →

Posted in haskell, math | Tagged , , , , , , , , , | 13 Comments

Worstsort

Posted on February 16, 2019 by Brent

Thanks for the responses to my previous post about finding roots of polynomials; I now have some new avenues to explore. But today I want to write about something completely different. I recently stumbled across this fun paper by Miguel … Continue reading →

Posted in haskell, humor, math | Tagged , , , , , | 10 Comments

Finding roots of polynomials in Haskell?

Posted on February 13, 2019 by Brent

tl;dr: There are several Haskell packages one can use to find an individual root of a function on a certain interval. But I’ve had less luck finding a suitable package for finding all the roots of a given polynomial. This … Continue reading →

Posted in haskell, math | Tagged , , , , , | 14 Comments

Counting inversions with monoidal sparks

Posted on October 6, 2018 by Brent

Time for me to reveal the example I had in mind that led to the generalization in my previous post. Thanks for all the interesting comments: it seems like there are some interesting connections to be explored (e.g. to the … Continue reading →

Posted in math | Tagged , , , , , , , , | 8 Comments

Monoidal sparks

Posted on October 1, 2018 by Brent

While at ICFP in St. Louis this past week, I discovered an interesting construction on monoids that no one I talked to (including Kenny Foner and Edward Kmett) seemed to have heard of or thought about before. In this post I’ll … Continue reading →

Posted in math | Tagged , , , , | 27 Comments

Parametricity for Bifunctor

Posted on March 30, 2018 by Brent

I’ve begun work to add Bifunctor, Bifoldable, and Bitraversable to the Typeclassopedia. While thinking and writing about Bifunctor I ended up proving some “folklore” results for my own satisfaction, and decided someone might possibly find it useful if I formally … Continue reading →

Posted in haskell, math | Tagged , , , , , | 3 Comments

Sum of heights in a binary tree

Posted on November 3, 2017 by Brent

Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down … Continue reading →

Posted in math, teaching | Tagged , , , , , , , | 2 Comments

Signed sets and ballots and naturality

Posted on February 27, 2017 by Brent

This is blog post #3 in a series on signed sets and ballots (the previous posts are here and here). Naturality, isomorphism, and equipotence When are two species isomorphic? Since species are, by definition, functors , the obvious answer is … Continue reading →

Posted in combinatorics, math, species | Tagged , , , , , , , | 2 Comments