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.