Created
January 29, 2016 19:51
-
-
Save jml/cdb20d02cf1195c03f72 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
parts s = do | |
a <- [1..s-1] | |
b <- [1..s-a] | |
c <- [1..s-a-b] | |
d <- [1..s-a-b-c] | |
return [a, b, c, d] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Bonus solution: StateT and []
There's a different approach to this problem, using the
StateT
monad transformer with[]
.This combination can be viewed as enriching each alternative value with a state, or as extending state actions to be "state multi-actions".
This lets lets us define a "multi-action" that reads the current sum, and then splits itself into alternatives, one for each possible selection and remaining sum:
With this defined, we can implement
partsOf
simply by repeatingpart
withreplicateM
, and feeding it the initial sum:For
allPartsOf
, we need something that conditionally repeats the action until the state (remaining sum) hits 0. We could implement this ourselves, but conveniently, monad-loops already haswhileM
, which repeats a monadic value until a monadic condition is met: