The man of action

To the Greeks the Private Realm was the sphere of life ruled by the necessity of sustaining life, and the Public Realm the sphere of freedom where a man could disclose himself to others. Today, the significance of the terms private and public has been reversed; public life is the necessary impersonal life, the place where a man fulfills his social function, and it is in his private life that he is free to be his personal self.

In consequence the arts, literature in particular, have lost their traditional principal human subject, the man of action, the doer of public deeds.

—W. H. Auden

More LINQ translation.

We will get to the second part of the last post later, but right now I wanted to post another quick "convert to Haskell from LINQ" entry this time from a post by Eric Lippert.

> import Control.Monad

Notice how similar this definition is to the C# version:

> data Tree = Node Tree Tree | Empty

In both version Node is the name of the constructor taking two arguments. Both cases make an immutable "object".

> instance Show Tree where
>   show Empty = "x"
>   show (Node l r) = "(" ++ show l ++ show r ++ ")"

The C# version's BinaryTreeString has a helper function doing the recursion, but it isn't really necessary (in the C# or Haskell). What the C# gains is the ability to side-effect on a StringBuilder directly rather than returning partial results.

> allTrees :: Int -> [Tree]
> allTrees 0 = [Empty]
> allTrees n = [Node l r | i <- [0..n-1]
>                        , l <- allTrees i
>                        , r <- allTrees (n - 1 - i)
>                        ]

This translates very directly from the LINQ code, each from statement becomes a statement with a <-. That's it! Testing we have:

> trees = mapM_ (putStrLn . show) (allTrees 4)

giving the output:

*Main> trees
(x(x(x(xx))))
(x(x((xx)x)))
(x((xx)(xx)))
(x((x(xx))x))
(x(((xx)x)x))
((xx)(x(xx)))
((xx)((xx)x))
((x(xx))(xx))
(((xx)x)(xx))
((x(x(xx)))x)
((x((xx)x))x)
(((xx)(xx))x)
(((x(xx))x)x)
((((xx)x)x)x)

In the comments we have several answers to the challenge the last of which translates to this:

> data ATree = ANode [ATree]

> instance Show ATree where
>   show (ANode [])   = "{}"
>   show (ANode xs) = "{" ++ (foldl1 (++) (map show xs)) ++ "}"

> allATrees :: Int -> [ATree]
> allATrees n = [ANode x | x <- h (n - 1)]
>   where h 0 = [[]]
>         h n = [(ANode l) : r | i <- [1..n]
>                              , l <- h (i - 1)
>                              , r <- h (n - i)
>                              ]

> aTrees = mapM_ (putStrLn . show) (allATrees 4)

Evaluating aTrees gives:

*Main> aTrees
{{}{}{}}
{{}{{}}}
{{{}}{}}
{{{}{}}}
{{{{}}}}

Note that this output is all strings of nested braces that are in a single outer pair of braces and are eight characters long. If we called allATrees's helper function h directly we would be removing the "single outer pair of braces" constraint. So h of n is of the same order as allTrees.

Solving Combinatory Problems with Haskell

Today my Visual Studio start page had a link to an interesting blog post by Octavio Hernandez and I couldn't pass up the opportunity to solve the problem with Haskell. Please note that this is not in anyway a commentary on language X is better than Language Y, rather looking at the same problem in many different languages is very helpful in understanding the problem itself better. I'll try and make this a literate Haskell post so you should be able to copy and paste the text into a text file with the ".lhs" extension and have everything run. So we begin by importing an operator that we will use later:

> import Data.List ((\\))

We will need a list of the digits.

> num = [1..9]


The first generation is all of the one digit numbers that satisfy n mod 1 == 0. That's an easy one, all of them satisfy that condition!

> m1 = num

We can see this in the C# version as from i1 in oneToNine without any where clause. The next step is to look at two digit numbers without repeating digits where n mod 2 == 0. So we write this:

> m2 = [n | a <- num
>         , b <- num \\ [a]
>         , n <- [a*10 + b]
>         , n `mod` 2 == 0
>         ]

This is a Haskell list comprehension and it can be read as "list ([) of n's (n) such that (|)...". Where the "..." is a series of conditions. The conditions are either pulling a value from a list (the ones with the left arrow <-), or are predicate statements. It will only use values that cause all the predicate statements to be true. We specifically have a being a digit. The second value b is using the list difference operator // which takes a list on the left and a list of values to remove on the right.

We will pause for a second and notice how similar this is to the mathematical statement:



If we run the code so far in ghci we can see that evaluating m2 gives us:

*Main> m2
[12,14,16,18,24,26,28,32,34,36,38,42,46,48,52,54,56,58,62,64,68,72,74,76,78,82,8
4,86,92,94,96,98]

Notice no digits repeat and all the numbers are even. Evaluating length m2 we see:

*Main> length m2
32

Since there are 9 digits (greater than 0) half of which are even (round down because 1 is odd) there should be four repeating digit even two digit number (22,44,66,88). Since we are not considering zero, there are nine possibilities for the first digit and four for the second (same as our repeats). This gives four times nine (36) minus our repeats (4) which equals 32. We now should be convinced that m2 is correct.

At this point we might be tempted to do the same thing for m3 but replacing our a to draw from m2. Instead we will capture the idea of that step in a more generic way. First we need a helper:

> toDigits a   = reverse $ h a
>    where h 0 = []
>          h a = a `mod` 10 : (h $ a `div` 10)

Back to ghci:

*Main> :t toDigits
toDigits :: (Integral a) => a -> [a]

This Haskell type shows that toDigits takes an Integral and gives a list of Integrals. It could be helpful to construct a sort of inverse to toDigits called fromDigits which could be defined as:

> fromDigits = foldl1 (\a b -> 10*a + b)

The details are not important, but it is helpful to notice that these two functions are nearly inverses of each other:

*Main> :t fromDigits . toDigits
fromDigits . toDigits :: Integer -> Integer
*Main> :t toDigits . fromDigits
toDigits . fromDigits :: [Integer] -> [Integer]

Here the . operator is composing the two functions.

*Main> fromDigits [1,2,3]
123
*Main> toDigits 123
[1,2,3]
*Main> (fromDigits . toDigits) 123
123

When we use fromDigits on a list with numbers larger than nine toDigits fails to be an inverse:

*Main> fromDigits [12,3]
123
*Main> toDigits 123
[1,2,3]
*Main> fromDigits [1,23]
33

This "failure" would still be useful in the case where only the first item in the list is greater than nine. In general it is nearly always instructive to try and construct an inverse function as it tells you quite a lot about your original function. You might observe similarities between fromDigits and n in m2. It turns out that there is another way to generalize n which we will come back to later.

Looking back at our definition of m2 we want to make that work for any step so we look for the parts that need to change. We know that we want to have a pull from the numbers from the previous step. And we know that we will be "modding" by a higher number each time. This implies two inputs to our step function which we will call ns and m respectively. We also have a problems that our helper function will fix for us. First the numbers from the previous step need to be split into digits for them to be subtracted from the pool of digits for b. So that becomes b <- num \\ (toDigits a). Now we can write our function down:

> step ns m = [n | a <- ns
>                , b <- num \\ (toDigits a)
>                , n <- [10*a + b]
>                , n `mod` m == 0
>                ]

We can test this out and see if it produces the next step:

*Main> let m3 = step m2 3
*Main> m3
[123,126,129,147,162,165,168,183,186,189,243,246,249,261,264,267,285,321,324,327
,342,345,348,369,381,384,387,423,426,429,462,465,468,483,486,489,528,543,546,549
,561,564,567,582,621,624,627,642,645,648,681,684,687,723,726,729,741,762,765,768
,783,786,789,825,843,846,849,861,864,867,921,924,927,942,945,948,963,981,984,987
]
*Main> length m3
80

I'll leave it as an exercise to the reader to determine if that is correct for m3.

We can now write out all the steps to get to m9 but we will now call them s1...s9 for steps one through nine:

> s1 = num
> s2 = step s1 2
> s3 = step s2 3
> s4 = step s3 4
> s5 = step s4 5
> s6 = step s5 6
> s7 = step s6 7
> s8 = step s7 8
> s9 = step s8 9

We can verify s9 is in fact the same result as the C# code gives:

*Main> s9
[381654729]

But we are not done yet! Writing out all the steps is repetitive. We will do a little bit of Haskell trickery to see how we can easily write this more simpily:

> s 1 = num
> s 2 = step (s 1) 2
> s 3 = step (s 2) 3
> s 4 = step (s 3) 4
> s 5 = step (s 4) 5
> s 6 = step (s 5) 6
> s 7 = step (s 6) 7
> s 8 = step (s 7) 8
> s 9 = step (s 8) 9

Here we used Haskell's pattern matching style of function definition to turn our s1 through s9 functions into a single function s that takes one parameter. All we had to do was add a few spaces and parentheses Now it should be clear how to collapse this down to two statements:

> s' 1 = num
> s' m = step (s (m-1)) m

We have s' 1 as the base case and s' m as the m^th case.

*Main> s' 9
[381654729]


Next time we will go further and look at some other ways to generalize this kind of problem.