### Pages

### Categories

- AC
- algorithm
- announcement
- applicative
- art
- axiom of choice
- balanced
- Beeminder
- bijection
- BlogLiterately
- category
- challenge
- collaborative editing
- combinatorial species
- combinatorics
- competitive
- constructive
- contest
- darcs
- data
- design
- diagrams
- dissertation
- drawing
- DSL
- EDSL
- enumeration
- feedback
- functional
- functional programming
- functor
- geometry
- GHC
- ghci
- graphics
- hackathon
- Hac φ
- haskell
- ICFP
- isomorphism
- Kattis
- library
- log
- monad
- monads
- monoid
- multiset
- music
- paper
- parsing
- partitions
- patch theory
- pedagogy
- Philadelphia
- pictures
- productivity
- programming
- QuickCheck
- random
- release
- sampling
- sets
- species
- talk
- teaching
- theory
- translation
- tree
- tutorial
- type
- type-level
- Typeclassopedia
- types
- virtual
- workshop

### Archives

- February 2021 (1)
- July 2020 (2)
- June 2020 (3)
- May 2020 (4)
- April 2020 (2)
- March 2020 (2)
- February 2020 (4)
- December 2019 (1)
- November 2019 (1)
- October 2019 (1)
- July 2019 (1)
- May 2019 (2)
- April 2019 (2)
- March 2019 (1)
- February 2019 (3)
- November 2018 (1)
- October 2018 (3)
- June 2018 (1)
- May 2018 (4)
- April 2018 (1)
- March 2018 (2)
- February 2018 (3)
- January 2018 (1)
- November 2017 (1)
- September 2017 (1)
- June 2017 (1)
- May 2017 (1)
- April 2017 (1)
- March 2017 (1)
- February 2017 (4)
- January 2017 (3)
- November 2016 (2)
- October 2016 (2)
- September 2016 (3)
- August 2016 (4)
- July 2016 (1)
- June 2016 (1)
- May 2016 (3)
- April 2016 (2)
- March 2016 (3)
- February 2016 (1)
- November 2015 (2)
- October 2015 (1)
- August 2015 (2)
- July 2015 (1)
- June 2015 (3)
- May 2015 (2)
- April 2015 (1)
- March 2015 (1)
- August 2014 (3)
- June 2014 (2)
- May 2014 (2)
- January 2014 (2)
- October 2013 (1)
- August 2013 (1)
- July 2013 (1)
- May 2013 (1)
- April 2013 (3)
- March 2013 (2)
- January 2013 (2)
- December 2012 (2)
- November 2012 (4)
- October 2012 (3)
- August 2012 (4)
- July 2012 (5)
- June 2012 (1)
- March 2012 (1)
- January 2012 (1)
- November 2011 (4)
- October 2011 (3)
- September 2011 (2)
- August 2011 (2)
- July 2011 (2)
- June 2011 (1)
- May 2011 (6)
- April 2011 (2)
- March 2011 (1)
- February 2011 (3)
- January 2011 (1)
- December 2010 (2)
- November 2010 (3)
- October 2010 (1)
- September 2010 (1)
- August 2010 (3)
- July 2010 (2)
- June 2010 (3)
- May 2010 (3)
- April 2010 (3)
- March 2010 (2)
- February 2010 (1)
- January 2010 (1)
- December 2009 (2)
- October 2009 (3)
- September 2009 (2)
- August 2009 (4)
- July 2009 (7)
- June 2009 (1)
- May 2009 (2)
- April 2009 (1)
- March 2009 (2)
- February 2009 (3)
- January 2009 (3)
- December 2008 (2)
- September 2008 (2)
- August 2008 (1)
- July 2008 (3)
- June 2008 (1)
- April 2008 (4)
- March 2008 (4)
- February 2008 (4)
- January 2008 (2)
- December 2007 (4)
- October 2007 (2)
- September 2007 (2)
- August 2007 (3)
- June 2007 (2)

### Top Posts

### Blogroll

### Fun

### Personal

### Meta

# Category Archives: math

## What would Dijkstra do? Proving the associativity of min

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

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

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 diagrams, finding, floating, haskell, point, polynomial, QuickCheck, root, solve, test
13 Comments

## Worstsort

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 badsort, computable, Fun, iterated, sort, worstsort
10 Comments

## Finding roots of polynomials in Haskell?

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

## Counting inversions with monoidal sparks

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

## Monoidal sparks

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

## Parametricity for Bifunctor

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 Bifunctor, bimap, free, haskell, parametricity, Typeclassopedia
3 Comments

## Sum of heights in a binary tree

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

## Signed sets and ballots and naturality

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 ballots, bijection, involution, natural, sets, signed, species, virtual
2 Comments

## Signed sets and ballots, part 2

Recall, from my previous post, that our goal is to find a combinatorial proof showing the correspondence between signed sets and signed ballots, where a signed set is just a set of elements, considered positive or negative according to the … Continue reading