5 ms·

I don't think that's true. Say you have an imperative algorithm that modifies an array in a loop. Then the Haskell encoding of that algorithm will use writeArra

I don't think that's true. Say you have an imperative algorithm that modifies an array in a loop. Then the Haskell encoding of that algorithm will use writeArray. But since it's monadic, it won't look like general recursion, it'll need to use a combinator like forM. You could say it's general recursion plus bind and return, but it gets worse. If the loop body needs to use both writeArray and randomness, you need more combinators. I'm not sure anyone can reliably write that stuff on a napkin, the way I can write a loop. That's not like the situation with gotos, because code with gotos is harder to write on a napkin.

tome 9y ago
What's wrong with this? import qualified Data.Vector.Mutable as V import Control.Monad (when) import qualified System.Random as R main = do v <- V.replicate 10 0 putStrLn "Initialised to zero" printThemAll v setIncreasing v putStrLn "Set with values increasing by 2" printThemAll v addRandomness v putStrLn "Added a random number to each" printThemAll v printThemAll v = loop 0 (V.length v) where loop i n = do when (i < n) $ do e <- V.read v i print e loop (i + 1) n setIncreasing v = loop 0 (V.length v) where loop i n = do when (i < n) $ do V.write v i (i * 2) loop (i + 1) n addRandomness v = loop 0 (V.length v) where loop i n = do when (i < n) $ do r <- R.randomIO e <- V.read v i V.write v i (e + r) loop (i + 1) n
- cousin_it 9y ago
  That's indeed nice, and made me change my mind somewhat. I wonder if you can write a napkin example that mixes ST with randomness, instead of using IO for everything?
  - tome 9y ago
    It's not too bad to manually thread a seed around. import qualified Data.Vector.Mutable as V import Control.Monad (when) import qualified System.Random as R import Control.Monad.ST st = runST $ do v <- V.replicate 10 0 setIncreasing v addRandomness v printThemAll v = loop 0 (V.length v) where loop i n = do when (i < n) $ do e <- V.read v i print e loop (i + 1) n setIncreasing v = loop 0 (V.length v) where loop i n = do when (i < n) $ do V.write v i (i * 2) loop (i + 1) n addRandomness v = loop initial_g 0 (V.length v) where seed = 1234 initial_g = R.mkStdGen 1234 -- Seed loop g i n = do when (i < n) $ do let (r, next_g) = R.random g e <- V.read v i V.write v i (e + r) loop next_g (i + 1) n
    - cousin_it 9y ago
      I see, thanks! The imperative version would still look more direct to me, but your versions are very nice.
kqr 9y ago
If you need writeArray and randomness and you don't like loop combinators, there is absolutely no problem using general recursion. That's one of the beauties of the monadic interface – it composes very well! ---- I'm going to show you some Haskell code now. This is code that could probably use improvement, but the reason it may look sketchy in some places is that I – surprise! – reliably wrote it on a napkin. Excepting some typos, obvious brainfarts and missed imports, this is actually the first draft of the code. Here's the quicksort algorithm as it is written on Wikipedia: algorithm quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) It's Haskell implementation will be very similar: quicksort vec = runST $ do mvec <- thaw vec let loop lo hi = when (lo < hi) $ do p <- partition mvec lo hi loop lo (p-1) loop (p+1) hi loop 0 (Vector.length mvec - 1) freeze mvec I'll walk through it line by line, even though most of it is very similar to the Wikipedia imperative pseudocode. quicksort vec = runST $ do mvec <- thaw vec We run this stuff as an ST expression, which is the Haskell way of saying "hey this block of code does actual mutation, be careful". The first thing we do is thaw the vector, which means making it mutable. let loop lo hi = when (lo < hi) $ do We define a loop that is going to depend on two variables for iteration: lo and hi. It runs for as long as lo is less than hi, and will break when hi is equal to or less than lo. p <- partition mvec lo hi loop lo (p-1) First, we call the partition procedure which divides the vector into two halves and returns to us the index of the pivot element between the two. Then, since we are in a function called "loop" we can continue to the next iteration by calling "loop". The neat thing about this is how it looks like we almost defined our own keyword, which acts somewhat like a "continue" statement in imperative languages. There is a difference, though. The "continue" statement in an imperative language would abort the current iteration, go back to the top of the loop and run another Iteration. The "loop" statement in our code also goes back to the top of the loop, but it doesn't abort the current iteration. Which means we can loop (p+1) hi also run a second iteration. This is in principle independent from the previous execution, so you can sort of view this as a "multi-continue" that starts two new iterations of the loop in parallel. In reality, though, the execution is sequential because the compiler doesn't have enough information to determine that they are indeed independent. loop 0 (Vector.length mvec - 1) Note that until now, the loop was only defined – it was never executed. But now we execute it with the initial values for lo and hi. It may seem weird that definition and execution of a loop can be separate from each other, but I haven't been able to come up with any reason that could end up bad. freeze mvec After we're done, we freeze the vector to make it immutable again. It might sound like an expensive operation, but it's not. Hopefully, the compiler will understand that nobody else has simultaneous access to the array so it will perform the modifications in-place and optimise away the thawing and freezing. (continued in second comment)
kqr 9y ago
(continued from previous comment) But what's really interesting is the partitioning procedure. That's where things get complicated. According to Wikipedia, it can be implemented in an imperative language like so: algorithm partition(A, lo, hi) is pivot := A[hi] i := lo - 1 for j := lo to hi - 1 do if A[j] ≤ pivot then i := i + 1 if i ≠ j then swap A[i] with A[j] swap A[i+1] with A[hi] return i + 1 This is the Haskell translation I came up with: partition a lo hi = do pivot <- Vector.read a hi i' <- newSTRef (lo - 1) j' <- newSTRef lo fix $ \loop -> do j <- readSTRef j' when (j < hi) $ do aj <- Vector.read a j when (aj <= pivot) $ do i <- inc i' when (i /= j) $ Vector.swap a i j inc j' loop i <- inc i' Vector.swap a i hi pure i Again, I'll walk through it part by part. partition a lo hi = do pivot <- Vector.read a hi i' <- newSTRef (lo - 1) j' <- newSTRef lo Since we're already running this as part of an ST expression, we don't need to specify "runST". First thing, we read the last element of the vector as our pivot, and we define two new references to mutable values i' and j'. (I like to indicate references with ticks like that to distinguish them from the value they contain. Ticks sort of remind me of the C pointer asterisk so it works out.) fix $ \loop -> do j <- readSTRef j' when (j < hi) $ do Okay, so last time we created a named loop through the "let" keyword, which defines new variables and functions. We could do that here as well, but I think this other approach generates neater code in this case. The "fix" combinator might twist your mind the first few times you see it, but suffice it to say that it creates a recursive function from an anonymous function, by supplying the function with itself as its first argument. You'll see soon one of the reasons I preferred it in this case. Then we read the value of the j' reference and use it as our loop condition. The loop should run as long as j is less than hi. aj <- Vector.read a j when (aj <= pivot) $ do i <- inc i' when (i /= j) $ Vector.swap a i j We read the value under j in the array, and if it is less than the pivot we increment the value in the i' reference. If the incremented value is different from j, we swap the two in the array. inc j' loop Regardless of how aj compared to the pivot, we increment the value under the j' reference and go back to the top again to start a new iteration. i <- inc i' Vector.swap a i hi pure i When the loop has finished, we increment i', swap the pivot element back in to its right place, and then return i. There are three things of note here: 1) One of the major differences with the imperative code is that in imperative Haskell code, we sometimes need to "dereference" mutable variables in a separate statement. We (generally) cannot do that as part of an expression. There are some structured ways around this even in Haskell, but at that point it might no longer be worth using Haskell to write imperative code. Why do I say that? Because it's actually a good thing that we need to dereference mutable variables in a separate statement. Several "safe coding standards" over the decades have evolved toward "keep expressions free from side-effects and have one statement per side effect". 2) When we defined the loop with fix we didn't have to call it separately from its definition. That's one of the benefits I was talking about. 3) I forgot what number three was. ---- Randomness, you said? That's a common optimisation to the quicksort shown above. The pivot is picked at random in the inclusive range [lo,hi] instead of fixed at hi. It is child's play to include it by simply passing a random generator as a parameter down the call chain to partition, so I'm not going to show that. What I'm going to show instead is how trivial it is to abstract that parameter away into a state transformer wrapper. I intentionally ignored this aspect until now to get honest results about shimming randomness in there. Here are the changes: 1. partition a lo hi = do p <- state (randomR (lo, hi)) lift $ do Vector.swap a hi p -- pivot <- Vector.read a hi -- ... I converted the partition method to a state transformer, which makes it possible to compute a random number in the [lo,hi] range and implicitly update the generator state. Then I swap the highest element and the chosen pivot, and the rest of the algorithm is the same as before. The state transformer also means that the rest of the partition function is now lifted, but that's no biggie. 2. quicksort gen vec = runST . flip evalStateT gen $ do -- pivot <- Vector.read a hi -- ... The quicksort function needs to wrap the ST expression in a state transformer, but is otherwise exactly the same as before. Since we need some sort of generator to start with, the quicksort function now also takes a generator as an argument and puts it in the state. This is not super clean – the quicksort needs to receive a generator each time it is called? Well, yeah, sorta–kinda. This is probably one of those places where it's legitimate to do an "unsafePerformSomething" – the randomness does not cause any actual impurity in the code. ---- What I did not attempt, and what is a complicated subject anyway, was the issue of arbitrary pivot selection strategies. It's easy to integrate support for random pivots, but what if the user wants to specify a pivot selection strategy of their own? That's fine if it's pure, or at least only relies on randomness, but what if it's unrestricted in its effects? What if they want to supply a strategy that calls your grandmother and asks her for a good pivot, or one that launches nuclear missies and counts the casualties to determine a pivot? That's clearly some serious international side effects, and I think that we do want to prevent the user from inserting strategies with arbitrary effects. But where to draw the line? And how to distinguish these kinds of effects? Haskell only throws them all into the IO bin, which is a problem. But the problem is not that effects are controlled, it's that even in Haskell there's a certain lack of control over effects.

tome 9y ago

What's wrong with this? import qualified Data.Vector.Mutable as V import Control.Monad (when) import qualified System.Random as R main = do v <- V.replicate 10 0 putStrLn "Initialised to zero" printThemAll v setIncreasing v putStrLn "Set with values increasing by 2" printThemAll v addRandomness v putStrLn "Added a random number to each" printThemAll v printThemAll v = loop 0 (V.length v) where loop i n = do when (i < n) $ do e <- V.read v i print e loop (i + 1) n setIncreasing v = loop 0 (V.length v) where loop i n = do when (i < n) $ do V.write v i (i * 2) loop (i + 1) n addRandomness v = loop 0 (V.length v) where loop i n = do when (i < n) $ do r <- R.randomIO e <- V.read v i V.write v i (e + r) loop (i + 1) n

cousin_it 9y ago
That's indeed nice, and made me change my mind somewhat. I wonder if you can write a napkin example that mixes ST with randomness, instead of using IO for everything?
- tome 9y ago
  It's not too bad to manually thread a seed around. import qualified Data.Vector.Mutable as V import Control.Monad (when) import qualified System.Random as R import Control.Monad.ST st = runST $ do v <- V.replicate 10 0 setIncreasing v addRandomness v printThemAll v = loop 0 (V.length v) where loop i n = do when (i < n) $ do e <- V.read v i print e loop (i + 1) n setIncreasing v = loop 0 (V.length v) where loop i n = do when (i < n) $ do V.write v i (i * 2) loop (i + 1) n addRandomness v = loop initial_g 0 (V.length v) where seed = 1234 initial_g = R.mkStdGen 1234 -- Seed loop g i n = do when (i < n) $ do let (r, next_g) = R.random g e <- V.read v i V.write v i (e + r) loop next_g (i + 1) n
  - cousin_it 9y ago
    I see, thanks! The imperative version would still look more direct to me, but your versions are very nice.

kqr 9y ago

If you need writeArray and randomness and you don't like loop combinators, there is absolutely no problem using general recursion. That's one of the beauties of the monadic interface – it composes very well! ---- I'm going to show you some Haskell code now. This is code that could probably use improvement, but the reason it may look sketchy in some places is that I – surprise! – reliably wrote it on a napkin. Excepting some typos, obvious brainfarts and missed imports, this is actually the first draft of the code. Here's the quicksort algorithm as it is written on Wikipedia: algorithm quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) It's Haskell implementation will be very similar: quicksort vec = runST $ do mvec <- thaw vec let loop lo hi = when (lo < hi) $ do p <- partition mvec lo hi loop lo (p-1) loop (p+1) hi loop 0 (Vector.length mvec - 1) freeze mvec I'll walk through it line by line, even though most of it is very similar to the Wikipedia imperative pseudocode. quicksort vec = runST $ do mvec <- thaw vec We run this stuff as an ST expression, which is the Haskell way of saying "hey this block of code does actual mutation, be careful". The first thing we do is thaw the vector, which means making it mutable. let loop lo hi = when (lo < hi) $ do We define a loop that is going to depend on two variables for iteration: lo and hi. It runs for as long as lo is less than hi, and will break when hi is equal to or less than lo. p <- partition mvec lo hi loop lo (p-1) First, we call the partition procedure which divides the vector into two halves and returns to us the index of the pivot element between the two. Then, since we are in a function called "loop" we can continue to the next iteration by calling "loop". The neat thing about this is how it looks like we almost defined our own keyword, which acts somewhat like a "continue" statement in imperative languages. There is a difference, though. The "continue" statement in an imperative language would abort the current iteration, go back to the top of the loop and run another Iteration. The "loop" statement in our code also goes back to the top of the loop, but it doesn't abort the current iteration. Which means we can loop (p+1) hi also run a second iteration. This is in principle independent from the previous execution, so you can sort of view this as a "multi-continue" that starts two new iterations of the loop in parallel. In reality, though, the execution is sequential because the compiler doesn't have enough information to determine that they are indeed independent. loop 0 (Vector.length mvec - 1) Note that until now, the loop was only defined – it was never executed. But now we execute it with the initial values for lo and hi. It may seem weird that definition and execution of a loop can be separate from each other, but I haven't been able to come up with any reason that could end up bad. freeze mvec After we're done, we freeze the vector to make it immutable again. It might sound like an expensive operation, but it's not. Hopefully, the compiler will understand that nobody else has simultaneous access to the array so it will perform the modifications in-place and optimise away the thawing and freezing. (continued in second comment)

kqr 9y ago

(continued from previous comment) But what's really interesting is the partitioning procedure. That's where things get complicated. According to Wikipedia, it can be implemented in an imperative language like so: algorithm partition(A, lo, hi) is pivot := A[hi] i := lo - 1 for j := lo to hi - 1 do if A[j] ≤ pivot then i := i + 1 if i ≠ j then swap A[i] with A[j] swap A[i+1] with A[hi] return i + 1 This is the Haskell translation I came up with: partition a lo hi = do pivot <- Vector.read a hi i' <- newSTRef (lo - 1) j' <- newSTRef lo fix $ \loop -> do j <- readSTRef j' when (j < hi) $ do aj <- Vector.read a j when (aj <= pivot) $ do i <- inc i' when (i /= j) $ Vector.swap a i j inc j' loop i <- inc i' Vector.swap a i hi pure i Again, I'll walk through it part by part. partition a lo hi = do pivot <- Vector.read a hi i' <- newSTRef (lo - 1) j' <- newSTRef lo Since we're already running this as part of an ST expression, we don't need to specify "runST". First thing, we read the last element of the vector as our pivot, and we define two new references to mutable values i' and j'. (I like to indicate references with ticks like that to distinguish them from the value they contain. Ticks sort of remind me of the C pointer asterisk so it works out.) fix $ \loop -> do j <- readSTRef j' when (j < hi) $ do Okay, so last time we created a named loop through the "let" keyword, which defines new variables and functions. We could do that here as well, but I think this other approach generates neater code in this case. The "fix" combinator might twist your mind the first few times you see it, but suffice it to say that it creates a recursive function from an anonymous function, by supplying the function with itself as its first argument. You'll see soon one of the reasons I preferred it in this case. Then we read the value of the j' reference and use it as our loop condition. The loop should run as long as j is less than hi. aj <- Vector.read a j when (aj <= pivot) $ do i <- inc i' when (i /= j) $ Vector.swap a i j We read the value under j in the array, and if it is less than the pivot we increment the value in the i' reference. If the incremented value is different from j, we swap the two in the array. inc j' loop Regardless of how aj compared to the pivot, we increment the value under the j' reference and go back to the top again to start a new iteration. i <- inc i' Vector.swap a i hi pure i When the loop has finished, we increment i', swap the pivot element back in to its right place, and then return i. There are three things of note here: 1) One of the major differences with the imperative code is that in imperative Haskell code, we sometimes need to "dereference" mutable variables in a separate statement. We (generally) cannot do that as part of an expression. There are some structured ways around this even in Haskell, but at that point it might no longer be worth using Haskell to write imperative code. Why do I say that? Because it's actually a good thing that we need to dereference mutable variables in a separate statement. Several "safe coding standards" over the decades have evolved toward "keep expressions free from side-effects and have one statement per side effect". 2) When we defined the loop with fix we didn't have to call it separately from its definition. That's one of the benefits I was talking about. 3) I forgot what number three was. ---- Randomness, you said? That's a common optimisation to the quicksort shown above. The pivot is picked at random in the inclusive range [lo,hi] instead of fixed at hi. It is child's play to include it by simply passing a random generator as a parameter down the call chain to partition, so I'm not going to show that. What I'm going to show instead is how trivial it is to abstract that parameter away into a state transformer wrapper. I intentionally ignored this aspect until now to get honest results about shimming randomness in there. Here are the changes: 1. partition a lo hi = do p <- state (randomR (lo, hi)) lift $ do Vector.swap a hi p -- pivot <- Vector.read a hi -- ... I converted the partition method to a state transformer, which makes it possible to compute a random number in the [lo,hi] range and implicitly update the generator state. Then I swap the highest element and the chosen pivot, and the rest of the algorithm is the same as before. The state transformer also means that the rest of the partition function is now lifted, but that's no biggie. 2. quicksort gen vec = runST . flip evalStateT gen $ do -- pivot <- Vector.read a hi -- ... The quicksort function needs to wrap the ST expression in a state transformer, but is otherwise exactly the same as before. Since we need some sort of generator to start with, the quicksort function now also takes a generator as an argument and puts it in the state. This is not super clean – the quicksort needs to receive a generator each time it is called? Well, yeah, sorta–kinda. This is probably one of those places where it's legitimate to do an "unsafePerformSomething" – the randomness does not cause any actual impurity in the code. ---- What I did not attempt, and what is a complicated subject anyway, was the issue of arbitrary pivot selection strategies. It's easy to integrate support for random pivots, but what if the user wants to specify a pivot selection strategy of their own? That's fine if it's pure, or at least only relies on randomness, but what if it's unrestricted in its effects? What if they want to supply a strategy that calls your grandmother and asks her for a good pivot, or one that launches nuclear missies and counts the casualties to determine a pivot? That's clearly some serious international side effects, and I think that we do want to prevent the user from inserting strategies with arbitrary effects. But where to draw the line? And how to distinguish these kinds of effects? Haskell only throws them all into the IO bin, which is a problem. But the problem is not that effects are controlled, it's that even in Haskell there's a certain lack of control over effects.