Restricted monads in Haskell

[hsenag]

Comments

Very Nice, and perplexing

[anonymous]

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:

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].

If you have any more insight into why this works, I'd love if you wrote about it.

Re: Very Nice, and perplexing

[hsenag]

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 perplexing

[fredrickegerman]

[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:

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.