Very Nice, and perplexing
anonymous
March 23 2008, 18:49:38 UTC
I remember wanting this very badly when I was first learning Haskell, since I wanted to create a quantum computation monad.
I'm still quite perpexed by your implementation. I haven't the slightest idea why code like this:
test = unEmbed $ do x <- Embed $ Set.fromList [1..5] y <- Embed $ Set.fromList [1..5] f <- return (+ (x + y)) return (f 1)
works. Intuitively, that would require an intermediate Set (Int -> Int).
... time passes ...
After staring at this for a while, I am still not sure how it works. But from some experiments I can say that it is probably no better than an abstract:
import Debug.Trace test = unEmbed $ do x <- Embed $ Set.fromList [-5..5] y <- return (x^2) trace (show y) $ return y Which traces 25,16,9,4,1,0,1,4,9,16,25, then returns [0,1,4,9,16,25
( ... )
Re: Very Nice, and perplexinghsenagMarch 24 2008, 17:11:36 UTC
Intuitively, that would require an intermediate Set (Int -> Int).
All it requires is an intermediate AsMonad Set (Int -> Int), and that is easy to make, by construction. The important part of my trick is to ensure that we don't have to convert it into Set (Int -> Int) in unEmbed - instead we just apply the underlying functions.
But from some experiments I can say that it is probably no better than an abstract [list-based implementation]
Yes, you're right, and thank you for pointing that out with a clear example. Efficiency issues were at the back of my mind but I hadn't got round to thinking them through. I actually had in mind when I designed this some other applications where efficiency isn't a concern, but I thought that Set was the most familiar example to present it with. However, the efficiency issue is actually somewhat subtle, and your question has prompted some ideas that I will explore further to see if I can't do better. I'll make another post once I reach a conclusion.
Re: Very Nice, and perplexingfredrickegermanMarch 26 2008, 12:37:55 UTC
[Here via Haskell-café]
The clever thing that this makes clear is that the restrictions on the carrying type (such as Ord for Set) only apply when you're actually using that type. The rest of the time the monad laws permit us to "compose away" all the bind operations. Let me simplify your first example:
y <- Embed $ Set.fromList [1..5] f <- return (+ (y + y)) return (f 1)
We can make f just vanish by following the monad laws, and that's exactly what the implementation above does:
The key insight (which I'd missed plenty of times in the past myself) is that we don't need Setty behavior unless the thing on the left hand side of >>= is actually a set.
I too have wanted something like this before, so it's good to see that it's possible - though how you do it is currently completely beyond me! :-) Looks like I'd better read up on GADTs and work my way through this post. As for parametrising AsMonad: could you generate the code with Template Haskell? It doesn't look like you actually need to know about the contents of your typeclass to generate the restricted monad for it.
Looks like you have found a generalised version of an approach I have just come up with for making Set a Monad.
I think it is worth pointing out that there are two tricks used here:
The first is to defer the evaluation of the bind (and return in your case) until you actually need a value, by which time you can restrict on member type because you are not tied by the Monad class definition.
The second trick is to use the monad associativity law to ensure that binds are always evaluated from the right. This allows the type checker to check the constraint in the final values of a bind chain and not worry about the intermediate ones. You do this during evaluation, I did it when building the tree.
The main problem with this approach, as has been pointed out here, is performance. In the Set example this is better than using lists, but you really want to be able to evaluate from the left.
Yeah - I did promise above that I'd post more about efficiency once I'd played around with a bit, but I never really got anywhere because I ran into the issue you mention about evaluating from the left.
I then concluded that what I really wanted was an arrow, but ran into problems handling "first" because working with it requires being able to deduce that the restriction is satisfied for a if it is satisfied for (a, b), which is not in general true, and even for Ord it's tricky to convince the typechecker that it is true.
Certainly nice, but it can be done in a different way, which seems more elegant for me: data OrdRest m a where OrdReturn :: a -> OrdRest m a OrdBind :: Ord a => m a -> (a -> OrdRest m b) -> OrdRest m b instance Monad (OrdRest m) where return = OrdReturn OrdReturn x >>= f = f x OrdBind mx g >>= f = OrdBind mx $ \x -> g x >>= f embed mx = OrdBind mx OrdReturn unembed (OrdReturn x) = ordReturn x unembed (OrdBind mx g) = ordBind mx $ unembed . gAnyway, it's kinda pattern, and being such it shows that Haskell isn't powerful enough.
I don't see any particular difference (in terms of elegance or otherwise) between doing the collapsing early or late, but obviously that's a matter of personal taste.
To be quite honest, i would have, for instance, a SetInternal type with the actual representation of the set, and then just have AsMonad SetInternal a be called Set a. Implement the functions on AsMonad SetInternal a and keep the embedding invisible to the programmer.
Well, crud. I just realized that you can't implement things like Foldable or Traversable over AsMonad, and you don't have control over the return type like you do with Functor and Monad. Ah, well.
Comments 15
I'm still quite perpexed by your implementation. I haven't the slightest idea why code like this:
test = unEmbed $ do
x <- Embed $ Set.fromList [1..5]
y <- Embed $ Set.fromList [1..5]
f <- return (+ (x + y))
return (f 1)
works. Intuitively, that would require an intermediate Set (Int -> Int).
... time passes ...
After staring at this for a while, I am still not sure how it works. But from some experiments I can say that it is probably no better than an abstract:
newtype SetM a = SetM [a]
deriving Monad
embed = SetM . Set.toList . Set.fromList
unEmbed (SetM xs) = Set.toList (Set.fromList xs)
On account of the following test:
import Debug.Trace
test = unEmbed $ do
x <- Embed $ Set.fromList [-5..5]
y <- return (x^2)
trace (show y) $ return y
Which traces 25,16,9,4,1,0,1,4,9,16,25, then returns [0,1,4,9,16,25 ( ... )
Reply
All it requires is an intermediate AsMonad Set (Int -> Int), and that is easy to make, by construction. The important part of my trick is to ensure that we don't have to convert it into Set (Int -> Int) in unEmbed - instead we just apply the underlying functions.
But from some experiments I can say that it is probably no better than an abstract [list-based implementation]
Yes, you're right, and thank you for pointing that out with a clear example. Efficiency issues were at the back of my mind but I hadn't got round to thinking them through. I actually had in mind when I designed this some other applications where efficiency isn't a concern, but I thought that Set was the most familiar example to present it with. However, the efficiency issue is actually somewhat subtle, and your question has prompted some ideas that I will explore further to see if I can't do better. I'll make another post once I reach a conclusion.
Reply
The clever thing that this makes clear is that the restrictions on the carrying type (such as Ord for Set) only apply when you're actually using that type. The rest of the time the monad laws permit us to "compose away" all the bind operations. Let me simplify your first example:
y <- Embed $ Set.fromList [1..5]
f <- return (+ (y + y))
return (f 1)
We can make f just vanish by following the monad laws, and that's exactly what the implementation above does:
Embed(Set.fromList [1..5]) >>= \y ->
return (+(y+y)) >>= \f -> return (f 1)
Now we can fold away the Bind of f:
Embed(Set.fromList [1..5]) >>= \y ->
return ((+(y+y)) 1)
The key insight (which I'd missed plenty of times in the past myself) is that we don't need Setty behavior unless the thing on the left hand side of
>>= is actually a set.
Reply
Reply
Reply
I think it is worth pointing out that there are two tricks used here:
The first is to defer the evaluation of the bind (and return in your case) until you actually need a value, by which time you can restrict on member type because you are not tied by the Monad class definition.
The second trick is to use the monad associativity law to ensure that binds are always evaluated from the right. This allows the type checker to check the constraint in the final values of a bind chain and not worry about the intermediate ones. You do this during evaluation, I did it when building the tree.
The main problem with this approach, as has been pointed out here, is performance. In the Set example this is better than using lists, but you really want to be able to evaluate from the left.
Reply
I then concluded that what I really wanted was an arrow, but ran into problems handling "first" because working with it requires being able to deduce that the restriction is satisfied for a if it is satisfied for (a, b), which is not in general true, and even for Ord it's tricky to convince the typechecker that it is true.
Reply
Reply
data OrdRest m a where
OrdReturn :: a -> OrdRest m a
OrdBind :: Ord a => m a -> (a -> OrdRest m b) -> OrdRest m b
instance Monad (OrdRest m) where
return = OrdReturn
OrdReturn x >>= f = f x
OrdBind mx g >>= f = OrdBind mx $ \x -> g x >>= f
embed mx = OrdBind mx OrdReturn
unembed (OrdReturn x) = ordReturn x
unembed (OrdBind mx g) = ordBind mx $ unembed . gAnyway, it's kinda pattern, and being such it shows that Haskell isn't powerful enough.
Reply
embed :: (Ord a) => m a -> OrdRest m a
unembed :: (OrdMonad m, Ord b) => OrdRest m b -> m b
Reply
It turns out that it is possible to use associated data types (GHC 6.8+) to abstract over this pattern: http://www.haskell.org/pipermail/haskell-cafe/2008-March/041084.html. I merged this with the above idea to make a general restricted monad library: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/rmonad, but didn't get round to blogging about it.
Reply
Reply
In fact in the original application where I used this idea I did have control of the type so just added the extra 'AsMonad' constructors to that type.
Reply
Reply
Leave a comment