good, simple advice

I was looking at Audrey Tang's presentation Visual Basic rocks, and came across a piece of good, simple advice:


Dogmatic
✗

Humble
✔



Well put. I was grateful to get a little reminder, a little booster shot. I'm just hoping that I have taken it sufficiently to heart.

(I'm assuming you see the red X under 'Dogmatic' and the green check mark under 'Humble').

I was looking at Audrey Tang's presentation Visual Basic rocks, and came across a piece of good, simple advice:


Dogmatic
✗

Humble
✔



Well put. I was grateful to get a little reminder, a little booster shot. I'm just hoping that I have taken it sufficiently to heart.

(I'm assuming you see the red X under 'Dogmatic' and the green check mark under 'Humble').

good, simple advice

burn your gas factories down

I've been Haskelling for three years now and have been loving it. The only discomfort is that from time to time I become painfully aware of my habit of making things horrible and ugly. Consider this code for instance:

usine à gaz

List of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N

> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

This code has been called "clever". Anytime somebody calls your code "clever", you should begin to worry. I mean just look at that thing! You can positively hear the gears turning and the doodads clicking. This code is what the French call a "gas factory", something incomprehensibly and needlessly complex.

is there no simpler way?

Stop micromanaging! Just tell the computer what you want, not what you want it to do

> nexts2 g (l,h) = map (\x -> fst $ randomR (x,h) g) [l..h-1]

No gears or doodads. Geez... I don't what it is with me and making things more complicated than they need to be.

I've been Haskelling for three years now and have been loving it. The only discomfort is that from time to time I become painfully aware of my habit of making things horrible and ugly. Consider this code for instance:

usine à gaz

List of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N

> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

This code has been called "clever". Anytime somebody calls your code "clever", you should begin to worry. I mean just look at that thing! You can positively hear the gears turning and the doodads clicking. This code is what the French call a "gas factory", something incomprehensibly and needlessly complex.

is there no simpler way?

Stop micromanaging! Just tell the computer what you want, not what you want it to do

> nexts2 g (l,h) = map (\x -> fst $ randomR (x,h) g) [l..h-1]

No gears or doodads. Geez... I don't what it is with me and making things more complicated than they need to be.

burn your gas factories down

unsort bis

Boy, do I feel like a big dummy!

Here is a super short and functional version I saw from a Pythonista on reddit.

import Data.List ( sort )
import System.Random ( Random, RandomGen, randoms, getStdGen )

main :: IO ()
main =
 do gen   <- getStdGen
    interact $ unlines . unsort gen . lines

unsort :: (Ord x, RandomGen g) => g -> [x] -> [x]
unsort g es = [ y | (_,y) <- sort $ zip rs es ]
  where rs = randoms g :: [Integer]

edit!

Heffalump points out that (i) if you have duplicates in rs, you don't get scrambling for the relevant bits (ii) this requires Ord x, which it really ought not to (although that is ani improvement from the array thing where I had to lock the type down for some reason)

edit deux

Hmm... what does it mean to get a list of random arbitrary precision integers?

Boy, do I feel like a big dummy!

Here is a super short and functional version I saw from a Pythonista on reddit.

import Data.List ( sort )
import System.Random ( Random, RandomGen, randoms, getStdGen )

main :: IO ()
main =
 do gen   <- getStdGen
    interact $ unlines . unsort gen . lines

unsort :: (Ord x, RandomGen g) => g -> [x] -> [x]
unsort g es = [ y | (_,y) <- sort $ zip rs es ]
  where rs = randoms g :: [Integer]

edit!

Heffalump points out that (i) if you have duplicates in rs, you don't get scrambling for the relevant bits (ii) this requires Ord x, which it really ought not to (although that is ani improvement from the array thing where I had to lock the type down for some reason)

edit deux

Hmm... what does it mean to get a list of random arbitrary precision integers?

unsort bis

unsort

Here's a small script I wrote partly for wikibook stuff and partly to learn how to use arrays and random numbers in Haskell.

I'm not a particularly enlightened Haskeller, so you might want to be careful about learning from me. Go ask somebody more experienced.

Note: one thing I'm a bit annoyed about is that I can't figure out how to make the unsort function generic, how to make it work for any type of array, element, index. Suggestions and by all means simplifications welcome.

unsort

> import Data.Ix ( Ix )
> import Data.List ( unfoldr )
> import Data.Array.MArray ( MArray, getElems, newListArray, readArray, writeArray )
> import System.Random ( mkStdGen, getStdGen, Random, RandomGen, random, randomR )
> import Data.Array.IO

> main :: IO ()
> main =
>  do gen   <- getStdGen
>     ins   <- lines `fmap` getContents
>     outs  <- unsort gen ins
>     putStr . unlines $ outs

Our objective is to scramble a list. To do this we convert the list into a mutable array and scramble it in place. This consists of traversing the array from left to right, swapping each element N with a random element from N to the end of the array.

> unsort :: RandomGen g => g -> [String] -> IO [String]
> unsort g es =
>  do arr  <- newListArray (l,h) es :: IO (IOArray Int String)
>     unsortH arr l idxs >>= getElems
>  where
>   idxs   = nexts g (l,h)
>   (l, h) = (1, length es)

The swapping itself is pretty straightforward. We swap the element at the
given index at the next random index. Recursion to the next element until
we run out of indices.

> unsortH :: (MArray a e m, Num i, Ix i) => a i e -> i -> [i] -> m (a i e)
> unsortH arr c [] = return arr
> unsortH arr c (r:rs) =
>  do rElem <- readArray arr r
>     cElem <- readArray arr c
>     writeArray arr c rElem
>     writeArray arr r cElem
>     unsortH arr (c+1) rs

And here is how we generate that list of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N... Hmm... I'm pretty sure this can be greatly cut down

> nexts :: (RandomGen g, Num n, Ord n, Random n, Ix n) => g -> (n,n) -> [n]
> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

Here's a small script I wrote partly for wikibook stuff and partly to learn how to use arrays and random numbers in Haskell.

I'm not a particularly enlightened Haskeller, so you might want to be careful about learning from me. Go ask somebody more experienced.

Note: one thing I'm a bit annoyed about is that I can't figure out how to make the unsort function generic, how to make it work for any type of array, element, index. Suggestions and by all means simplifications welcome.

unsort

> import Data.Ix ( Ix )
> import Data.List ( unfoldr )
> import Data.Array.MArray ( MArray, getElems, newListArray, readArray, writeArray )
> import System.Random ( mkStdGen, getStdGen, Random, RandomGen, random, randomR )
> import Data.Array.IO

> main :: IO ()
> main =
>  do gen   <- getStdGen
>     ins   <- lines `fmap` getContents
>     outs  <- unsort gen ins
>     putStr . unlines $ outs

Our objective is to scramble a list. To do this we convert the list into a mutable array and scramble it in place. This consists of traversing the array from left to right, swapping each element N with a random element from N to the end of the array.

> unsort :: RandomGen g => g -> [String] -> IO [String]
> unsort g es =
>  do arr  <- newListArray (l,h) es :: IO (IOArray Int String)
>     unsortH arr l idxs >>= getElems
>  where
>   idxs   = nexts g (l,h)
>   (l, h) = (1, length es)

The swapping itself is pretty straightforward. We swap the element at the
given index at the next random index. Recursion to the next element until
we run out of indices.

> unsortH :: (MArray a e m, Num i, Ix i) => a i e -> i -> [i] -> m (a i e)
> unsortH arr c [] = return arr
> unsortH arr c (r:rs) =
>  do rElem <- readArray arr r
>     cElem <- readArray arr c
>     writeArray arr c rElem
>     writeArray arr r cElem
>     unsortH arr (c+1) rs

And here is how we generate that list of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N... Hmm... I'm pretty sure this can be greatly cut down

> nexts :: (RandomGen g, Num n, Ord n, Random n, Ix n) => g -> (n,n) -> [n]
> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

unsort

risk and recursion

Lately, I've been playing a bit of correspondence Risk with some childhood friends. The good thing about correspondence Risk, when you're scattered across twelve timezones is that it is inherently self-limiting. You are forced to wait your turn every day. Well, that was my hope anyway, but it turns out that things are not quite that simple. The problem is that though you may well your turn, nothing is stopping you in the meantime from thinking about World Domination instead of doing something useful.

But maybe something useful just came out of these daydreams. I was thinking that Risk might be a good tool for teaching programming techniques. For example, it seems calculating dice roll outcomes would a rather nice example for teaching recursion and dynamic programming. This is something we typically do with factorial and fibonacci, but for some students, that might get a little boring. Perhaps dice rolls aren't all that exciting either, but maybe you could sell the Risk angle an awaken your audience's inner ten year old. Maybe you could sell this as part of a bigger package... in this class, we'll be putting together our own Risk implementation, with fancy graphics and everything.

The idea is that you want to ask your program "if the attacker has 37 armies and the defender has 10, what is the most probable outcome and its probability (assuming that each side uses as many dice as possible)?"

My belief is that there is no way to calculate this 'instantly' and without computing all possibilities. You would have to basically crunch through each one of the (a * d) eventual outcomes. (anybody with halfway decent math skills want to confirm that?)

One idea you might able to show with this is just plain simple recursion (although you probably want to start with a simpler example first). So I've got 37 and 10, and if I need the expected outcomes of 37/8 (attacker wins), 36/9 (both win one), and 35/10 (defender wins), I could just factor in the probabilities of getting those.

But I thought was interesting was that you could show that there is some redundant computation going on here. You start at 37/10, but then you go into

37/10
37/8	36/9	35/10

which in turn expands into

37/10
37/8			36/9			35/10
37/6	36/5	35/8	36/7	35/8	34/9	35/8	34/9	33/10

Here, we are recalculating the scenarios 36/7, 35/8 and 34/9. What happens if we turn the crank some more? If I'm not mistaken, the naive algorithm would have to do 3^n calculations (loosely speaking), when really we shouldn't be doing any more than n^2.

I suppose what you'd really want is to have some kind of record of all the outcomes you've already computed. I'm not sure how it would work out code-wise or how you'd shift all those weights around (and if you are interested, I do invite you to cook up a quick implementation, RiskBuzz). I will observe, however, that this table could make it simple to turn around and ask a slightly more involved question, like "ok, so what are the three likeliest outcomes and their probabilities?"

Lately, I've been playing a bit of correspondence Risk with some childhood friends. The good thing about correspondence Risk, when you're scattered across twelve timezones is that it is inherently self-limiting. You are forced to wait your turn every day. Well, that was my hope anyway, but it turns out that things are not quite that simple. The problem is that though you may well your turn, nothing is stopping you in the meantime from thinking about World Domination instead of doing something useful.

But maybe something useful just came out of these daydreams. I was thinking that Risk might be a good tool for teaching programming techniques. For example, it seems calculating dice roll outcomes would a rather nice example for teaching recursion and dynamic programming. This is something we typically do with factorial and fibonacci, but for some students, that might get a little boring. Perhaps dice rolls aren't all that exciting either, but maybe you could sell the Risk angle an awaken your audience's inner ten year old. Maybe you could sell this as part of a bigger package... in this class, we'll be putting together our own Risk implementation, with fancy graphics and everything.

The idea is that you want to ask your program "if the attacker has 37 armies and the defender has 10, what is the most probable outcome and its probability (assuming that each side uses as many dice as possible)?"

My belief is that there is no way to calculate this 'instantly' and without computing all possibilities. You would have to basically crunch through each one of the (a * d) eventual outcomes. (anybody with halfway decent math skills want to confirm that?)

One idea you might able to show with this is just plain simple recursion (although you probably want to start with a simpler example first). So I've got 37 and 10, and if I need the expected outcomes of 37/8 (attacker wins), 36/9 (both win one), and 35/10 (defender wins), I could just factor in the probabilities of getting those.

But I thought was interesting was that you could show that there is some redundant computation going on here. You start at 37/10, but then you go into

37/10
37/8	36/9	35/10

which in turn expands into

37/10
37/8			36/9			35/10
37/6	36/5	35/8	36/7	35/8	34/9	35/8	34/9	33/10

Here, we are recalculating the scenarios 36/7, 35/8 and 34/9. What happens if we turn the crank some more? If I'm not mistaken, the naive algorithm would have to do 3^n calculations (loosely speaking), when really we shouldn't be doing any more than n^2.

I suppose what you'd really want is to have some kind of record of all the outcomes you've already computed. I'm not sure how it would work out code-wise or how you'd shift all those weights around (and if you are interested, I do invite you to cook up a quick implementation, RiskBuzz). I will observe, however, that this table could make it simple to turn around and ask a slightly more involved question, like "ok, so what are the three likeliest outcomes and their probabilities?"

risk and recursion

iron coder

There ought to be something like Iron Chef for programming. Naturally, the Iron Coders would each represent a different paradigm: functional, imperative, object oriented, declarative. Actually, I have no idea how this would work and suspect it probably would not very entertaining at all. I just like the idea of summoning IRON CODER FUNCTIONAL! The guy rises with a platform and it's got a little lambda on it...

There ought to be something like Iron Chef for programming. Naturally, the Iron Coders would each represent a different paradigm: functional, imperative, object oriented, declarative. Actually, I have no idea how this would work and suspect it probably would not very entertaining at all. I just like the idea of summoning IRON CODER FUNCTIONAL! The guy rises with a platform and it's got a little lambda on it...

iron coder

haskell wikibook now featured

Spot the lambda?

Haskell :: Functional Programming with Types

Haskell :: Functional Programming with Types is now a featured wikibook, which means that it will be rotated on to the front page on a regular basis.

There are around 40 books on the site that have this distinction, so if you don't see the Haskell book on the front page, try again in another hour or so.

Write Yourself a Scheme in 48 Hours

Note that the wikibook version of Write Yourself a Scheme in 48 Hours has also been featured for quite some time. Yay, Johnathan! It's not on the front page yet, but should be making its way into the rotation at some point. Its blurb is
as follows:

In this advanced Haskell tutorial, we will implement a significant subset of Scheme together. We assume no prior knowledge; however, we will be going fast. So if you're feeling ambitious, why don't you Write Yourself a Scheme in 48 Hours?

Spot the lambda?

Haskell :: Functional Programming with Types

Haskell :: Functional Programming with Types is now a featured wikibook, which means that it will be rotated on to the front page on a regular basis.

There are around 40 books on the site that have this distinction, so if you don't see the Haskell book on the front page, try again in another hour or so.

Write Yourself a Scheme in 48 Hours

Note that the wikibook version of Write Yourself a Scheme in 48 Hours has also been featured for quite some time. Yay, Johnathan! It's not on the front page yet, but should be making its way into the rotation at some point. Its blurb is
as follows:

In this advanced Haskell tutorial, we will implement a significant subset of Scheme together. We assume no prior knowledge; however, we will be going fast. So if you're feeling ambitious, why don't you Write Yourself a Scheme in 48 Hours?

haskell wikibook now featured