Nothing too crazy today, just a cute (basic/intermediate) haskell trick as a response to Mark Dominus’s excellent Universe of Discourse post on Easy exhaustive search with the list monad intended for people new or unfamiliar with haskell demonstrating the common “list monad as a constraint solver” approach that is standard fare for learning Haskell. I myself have literally done an entire series of blog posts on this usage.
Mark’s use case however incorporates a bit of an extra pattern not typically discussed. The list monad is good for taking “independent samples” of things (looking at different samples from a list):
ghci> do x <- "abc" y <- "abc" z <- "abc" return [x,y,z] ["aaa","aab","aac","aba","abb" ... ]
However, what if you wanted to instead “draw” from a pool, and represent different drawings? Traditionally, the answer was something like:
ghci> do x <- "abc" y <- filter (/= x) "abc" z <- filter (/= y) . filter (/= x) $ "abc" return [x,y,z] "abc","acb","bac","bca","cab","cba"]
This is a little bit awkward…and it definitely gets a lot worse () when you have more items. Also, it relies on an
Eq constraint — what if our thing doesn’t have an
Eq instance? And this also falls apart when our list contains duplicate items. If we had used
"aabc" instead of
"abc", the result would be the same — despite having more
'a's to pick from!