Combinatoric problem in Haskell
The algorithm is purely combinatorial: it doesn't depend on the actual values of the elements. That can be made explicit by using more general types. Compare these signatures:

ansatzEtas :: Integer -&gt; Forest String
ansatzEtas :: Integer -&gt; [a] -&gt; Forest (a, a)
-- takes the alphabet as a parameter (length must be &gt;= the first argument n)



The output is guaranteed to be a forest of pairs.
Now that a is a type parameter, we are guaranteed that the pairs contain only elements from the original list.




We can easily get back a forest of strings using the fact that trees are functors:

pairToList :: Forest (a, a) -&gt; Forest [a]
pairToList = (fmap . fmap) (\(x, y) -&gt; [x, y])




More precise types make mistakes much less likely, and can even help us know what to write. For example, imagine we're still trying to write innerEtas, and we want to know what to put in place of the underscore:

innerEtas :: String -&gt; [(String, String)]
innerEtas (x:xs) = map (\a -&gt; (_, filter (/=a) xs)) xs


We can try to compile this code as it is, with the underscore, and GHC will report that this hole is of expected type String.

• Found hole: _ :: String


It also helpfully tells us that xs :: [Char] is in scope. On a tired day, one might then mistakenly interpret that as advice to put xs in:

innerEtas (x:xs) = map (\a -&gt; (xs, filter (/=a) xs)) xs
                               -- Bug!


Looking back, before we even start writing innerEtas, we know that it's supposed to give us pairs, and we can say it in the type.

innerEtas :: [a] -&gt; [((a, a), [a])]
innerEtas (x:xs) = map (\a -&gt; (_, filter (/=a) xs)) xs


Here we would be told the following expected type:

• Found hole: _ :: (a, a)


Which is hopefully much more helpful to determine what goes where.



This generalization may introduce a bit of a challenge, because innerEtas uses (/=), which requires an Eq constraint. Two options:


Just add the Eq a constraint everywhere, this is an easy solution, we still get most of the benefits of the generalization anyway.
Rewrite innerEtas to not use (/=), instead write a custom recursive function or use other combinators than filter. This can help avoid mistakes when making heavy use of Eq, but arguably this is not the case here.


Still, in this case there's a cute one-liner to extract an element from a list and keep the rest, nondeterministically, without using Eq:

pick :: [a] -&gt; [(a, [a])]
pick xs = [(y, ys ++ ys') | (ys, y : ys') &lt;- liftA2 zip inits tails xs]
-- inits, tails from Data.List

-- Example
pick [1,2,3] = [(1,[2,3]),(2,[1,3]),(3,[1,2])]




Some refactoring is possible between innerEtas and buildEtas. There is redundancy because both are checking whether the list is empty. In fact, x is quite a bit more special than the other elements, and we can take it apart in buildEtas already. Then innerEtas could take x separately from the tail as an argument, but it becomes a one-liner that we might as well inline:

buildEtas :: [a] -&gt; Forest (a, a)
buildEtas [] = []
buildEtas (x : []) = undefined   -- I think this is unnecessary, but kept it to remain close to the original code
buildEtas (x : xs) = let ys = map (\(y, zs) -&gt; ((x, y), zs) (pick xs)
                     in map (\(node, list) -&gt; Node node $ buildEtas list) ys