-
-
Save jml/cdb20d02cf1195c03f72 to your computer and use it in GitHub Desktop.
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] |
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:
import Control.Monad.Trans.Class
import Control.Monad.Trans.State
part :: (Enum n, Num n) => StateT n [] n
part = do s <- get
d <- lift [1..s]
put (s-d)
return d
With this defined, we can implement partsOf
simply by repeating part
with replicateM
, and feeding it the initial sum:
-- We can simply repeat the the part action.
partsOf :: (Enum n, Num n) => Int -> n -> [[n]]
n `partsOf` s = replicateM n part `evalStateT` s
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 has whileM
, which repeats a monadic value until a monadic condition is met:
import Control.Monad.Loops (whileM)
allPartsOf :: (Enum n, Num n, Ord n) => n -> [[n]]
allPartsOf s = whileM ((0 <) <$> get) part `evalStateT` s
Alright, here's my attempt at explaining the intuition behind the
unfoldM
-based solution above, with a detour intounfoldr
too, as a mini-tutorial.(This assumes some existing familiarity with the
[]
functor.)1. Almost a solution: sequence
Observe that whenever you have this pattern:
then you can simplify it to the following if the expressions are independent:
This is tantalizingly close to a solution for the puzzle: if we could define the right expressions for each element, and control the list's length, then we would have our solution.
The idea of controlling the length of a
sequence
is close to whatreplicateM
does:However,
replicateM
only replicates identical copies of the same element, as the name suggests.Can we fix the length like
replicateM
, but vary the elements?One approach we can try is to generate lists of the desired length, with elements close to the shape of the puzzle:
We can
sequence
these:But now, we run into the fundamental limitation of
sequence
mentioned before: once the elements are generated and passed tosequence
, each element represents an independent list of alternative values for that element. This means that the list of alternatives at each position is predetermined: any selection made for an element at one position cannot affect the list of alternative values for an element at another position.By contrast, our problem defines the list of possible alternatives for each element in terms of the selection made for the previous element: starting with an initial sum, each element's selection is subtracted from it to get the remaining sum that the following element may range up to.
So, to solve the problem, we need a way to generate a list element by element, starting from a seed value (the initial sum), with each step generating a value from the seed (an integer between 1 and the sum) and passing along a modified seed (the remaining sum).
This is exactly what
unfoldr
does for pure lists, andunfoldM
does for lists in the context of a monad.2. Intermission: unfoldr
A quick refresher: where
foldr
consumes a list by breaking down its structure to a summary value,unfoldr
produces a list by generating its structure from a seed value. Formally, the two functions are dual to each other.The type of
unfoldr
looks a bit strange, at first, compared tofoldr
:but this difference is mainly technical: Haskell does not have anonymous sum types, so the function uses
Just (a, b)
andNothing
as stand-ins to represent the choice between generating a cons or a nil at each step.Like
foldr
,unfoldr
is widely useful for anything that produces lists, and many common functions can be defined in terms of it:Even
map
, which is usually presented as afoldr
(map f = foldr ((:) . f) []
), can also be formulated as anunfoldr
, which consumes the input list as it produces the output list:3. Counting down with unfoldr
Before tackling the main problem and
unfoldM
, let's consider a simple but similar toy problem which can be solved withunfoldr
.The problem is to generate countdown lists:
Counting down to a target is easy enough:
(Note how this is almost identical to
replicate
, except for filling in the list elements with the count itself, rather than the fixed value.)Counting a fixed number of counts from an arbitrary number is a bit trickier: we can no longer reuse the same number for both the current count and the number of steps left. However, we can keep track of both at the same time:
4. Counting down with unfoldM
Earlier, I said that
unfoldM
is likeunfoldr
in the context of a monad, but what does this actually mean, intuitively?Compare the types:
Compared to
unfoldr
,unfoldM
addsm
to the generating function's result and the final result. This means that each generating step takes the current seed and returns the next step as a monadic value.We can experiment with this by making a variation of
countdown
that usesunfoldM
with IO actions to prompt the user for how much to count down by, at each step:Note how the only change was to insert the relevant IO actions around the
Just
andNothing
results.How about swapping
IO
for[]
? Instead of reading the amount from the user, we can list all possible amounts to count down by as alternative values:(The
max
is necessary to ensure we always count down by at least 1.)This gives us a list of possible countdowns by non-zero increments:
#5. The solution: Counting down differences
multiCountdown
looks very reminiscent of our puzzle solution.In fact, it is the puzzle solution, if you take the differences between the countdown numbers.
With a tweak to the edge condition, and letting the value of each element be the difference rather than the current seed (or remaining sum), we can transform
multiCountdown
intoallPartsOf
: