How to lift delete to State List monad?
dauc...@gmail.com
I'm having a spot of bother implementing a bit of nondeterminism that
affects the state. What I wish to do is something equivalent to
lifting delete to a State [a] monad, in pseudo-code:
takeout = \s -> (x, delete x s)
where x is one of the values in s.
What I'm aiming at is code in this style:
> do a <- takeout
> guard (a > 0)
> b <- takeout
> c <- takeout
where takeout progressively narrows the stored in the current state.
What I'm not after is
[(a,b,c)| a <- list, a > 0, b <- list, c <- list]
as I wish to progressively narrow options at each select, and this
compression does not do that.
Recommendations? Any help is gratefully accepted!
Sincerely,
Doug Auclair
Dirk Thierbach
> What I wish to do is something equivalent to
> lifting delete to a State [a] monad, in pseudo-code:
> takeout = \s -> (x, delete x s)
> where takeout progressively narrows the stored in the current state.
I'm not sure I have fully understood what you want (it would help to
see a concrete example what you want to use it for).
Anyway, to combine a list monad with a state monad, you need a state
monad transformer. Assume for example you want to keep as state a list
of "candidates", then choose nondeterministically a candidate (taking
it out of the list), and also verify if some calculated value is a candidate
(also taking it out of the list during that process).
> import Control.Monad.State
> import Data.List
>
> -- split list into all combinations of one element and rest
> splits :: [a] -> [(a,[a])]
> splits l = splitAccum [] l where
> splitAccum ys [] = []
> splitAccum ys (x:xs) = (x,xs++ys) : splitAccum (x:ys) xs
>
> choose :: StateT [a] [] a
> choose = StateT $ \s -> splits s
>
> verify :: Eq a => a -> StateT [a] [] ()
> verify v = StateT $ \s ->
> if v `elem` s then [((), delete v s)] else []
To make up a stupid example, if you want to find out all ways to sum
two numbers to a third number, where all numbers must be from a given set
of candidates and cannot repeat, you could write
> sums = do
> x <- choose
> y <- choose
> let z = x + y
> verify z
> return (x,y,z)
and get
*Main> evalStateT sums [1..4]
[(1,2,3),(1,3,4),(2,1,3),(3,1,4)]
(Yes, this can be done more efficiently, it's just for illustration).
Is that close to what you were after?
- Dirk
Florian Kreidler
> Dear all,
>
> I'm having a spot of bother implementing a bit of nondeterminism that
> affects the state. What I wish to do is something equivalent to
> lifting delete to a State [a] monad, in pseudo-code:
>
> takeout = \s -> (x, delete x s)
takeout = do (x,s) <- get
put s
return x
In the API docs for Control.Monad.State.Lazy this function is called
item.
(Are you sure that you don't want to use mapM?)
dauc...@gmail.com
On Nov 29, 4:41 am, Dirk Thierbach <dthierb...@usenet.arcornews.de>
wrote:
> daucl...@gmail.com wrote:
> I'm not sure I have fully understood what you want (it would help to
> see a concrete example what you want to use it for).
[snip splits and choose]
Yes, that's what I was looking for. Thank you for providing the
solution.
>
> > verify :: Eq a => a -> StateT [a] [] ()
> > verify v = StateT $ \s ->
> > if v `elem` s then [((), delete v s)] else []
> >
[...]
> (Yes, this can be done more efficiently, it's just for illustration).
Actually, I use the following definition for verify (in the spirit of
guard for MonadPlus):
> verify :: Bool -> StateT [a] [] ()
> verify p = StateT $ \s -> if p then [((), s)] else []
... as I was only looking to eliminate x where x <- choose from future
selections, so thank you again for your solution. By the way, the
solution you provided is "efficient enough": it sped up SEND
+MORE=MONEY using just the list monad (in the style of McCarthy's amb
operator) by a factor of ~10.
I'm wondering: being new to monadic programming in Haskell, I wasn't
driven toward your solution. http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html
was very helpful for introducing monad transformers to me, but it
hasn't got me to the point where monad use and monad transformation
are simple and natural for me. What do you recommend I read/do so I
would able to work my way to the solution you provided?
Sincerely,
Douglas Auclair
Dirk Thierbach
>> > verify :: Eq a => a -> StateT [a] [] ()
>> > verify v = StateT $ \s ->
>> > if v `elem` s then [((), delete v s)] else []
> Actually, I use the following definition for verify (in the spirit of
> guard for MonadPlus):
>> verify :: Bool -> StateT [a] [] ()
>> verify p = StateT $ \s -> if p then [((), s)] else []
Hm. How do you access the state with the predicate? Or do you just
need the same functionality as "guard"? If so, you can just use "guard"
itself:
> sums = do
> x <- choose
> guard $ even x
> y <- choose
> let z = x + y
> verify z
> return (x,y,z)
*Main> evalStateT sums [1..4]
[(2,1,3)]
> I'm wondering: being new to monadic programming in Haskell, I wasn't
> driven toward your solution.
It's been some time since I wrote that code (for a similar problem
as the "send more money" one). AFAIR, my train of thought was something
like this:
- I need both state and nondeterminism, so I have to combine the state
monad and the list monad. This means I need a monad transformer and
a monad (you need to have seen this before, but if you have once, it's
easy to remember).
- The state itself also has to be a list (of candidates).
- So the final monad has type "StateT [a] [] b".
- I need some function to nondeterministically pick a candidate. This
function should also update the state.
- Played around a short time with available functions, didn't get anywhere.
- Decided I need to go to the "bare metal".
- Expanded "StateT [a] [] a" into "[a] -> [(a,[a])]", then it was
obvious what "choose" should do.
- Decided the required functionality "split a list into one element and
rest, in all possible ways" was general enough to deserve its own function.
- Wrote it down, in the first attempt without accumulator.
- Wrote it down again, this time using an accumulator.
> http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html
> was very helpful for introducing monad transformers to me, but it
> hasn't got me to the point where monad use and monad transformation
> are simple and natural for me. What do you recommend I read/do so I
> would able to work my way to the solution you provided?
I don't know any good tutorial. I guess the high points are something
like:
- There are three important types of monads: State, List for
nondeterminism, Cont for non-local jumps.
- Most practically interesting monads are a variant and/or combination
of those.
- To combine monads, you have to use monad transformers instead of plain
monads for all involved monads but one.
(There's a simple explanation for this if you're a bit familiar with
category theory: Every monad is equivalent to a pair of adjoint
functors. The "monad functor" (i.e., the monad type constructor) is
the composition of those. But if you want to combine monads, you need
both functors separately. So if you don't have the adjoint pair
itself, the only way to do this is to leave a "hole" in the type
constructor "between" those functors, so the composition still
works. This is what monad transformers do).
- To write "interesting" operations for a particular monad, you often
have to work directly with the representation.
I guess enough practice also helps :-)
- Dirk