Trees generation in Java and Haskell

Trees.hs

{-# LANGUAGE TupleSections #-}

module Trees where

data Tree = Leaf
          | Branch2 Tree Tree
          | Branch3 Tree Tree Tree
          deriving (Show, Eq)

size :: Tree -> Int
size Leaf = 1
size (Branch2 t1 t2) = 1 + size t1 + size t2
size (Branch3 t1 t2 t3) = 1 + (sum $ map size [t1, t2, t3])

allTrees :: Int -> [Tree]
allTrees n | n <= 0 = []
allTrees 1 = [Leaf]
allTrees n = branch2s ++ branch3s
  where branch2s = do
          size1 <- [1..n - 2]
          let size2 = n - 1 - size1
          tree1 <- allTrees size1
          tree2 <- allTrees size2
          return $ Branch2 tree1 tree2
        branch3s = do
          size1 <- [1..n - 3]
          size2 <- [1..n - 2 - size1]
          let size3 = n - 1 - size1 - size2
          tree1 <- allTrees size1
          tree2 <- allTrees size2
          tree3 <- allTrees size3
          return $ Branch3 tree1 tree2 tree3

addArg :: (a -> [b]) -> a -> [(a, b)]
addArg f x = map (x,) $ f x

allTrees' :: Int -> [Tree]
allTrees' n | n <= 0 = []
allTrees' 1 = [Leaf]
allTrees' n = branch2s ++ branch3s
  where branch2s = do
          (s1, t1) <- [1..n - 2] >>= addArg allTrees'
          t2 <- allTrees' (n - 1 - s1)
          return $ Branch2 t1 t2
        branch3s = do
          (s1, t1) <- [1..n - 3] >>= addArg allTrees'
          (s2, t2) <- [1..n - 2 - s1] >>= addArg allTrees'
          t3 <- allTrees' (n - 1 - s1 - s2)
          return $ Branch3 t1 t2 t3

Trees.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.function.Function;

public class Trees {

    private static abstract class Tree {
        abstract int size();
    }

    public static class Leaf extends Tree {
        @Override
        public int size() {
            return 1;
        }
    }

    public static class Branch2 extends Tree {
        private final Tree t1, t2;

        public Branch2(Tree t1, Tree t2) {
            this.t1 = t1;
            this.t2 = t2;
        }

        @Override
        int size() {
            return 1 + t1.size() + t2.size();
        }
    }

    public static class Branch3 extends Tree {
        private final Tree t1, t2, t3;

        public Branch3(Tree t1, Tree t2, Tree t3) {
            this.t1 = t1;
            this.t2 = t2;
            this.t3 = t3;
        }

        @Override
        int size() {
            return 1 + t1.size() + t2.size() + t3.size();
        }
    }

    public static class Pair<A, B> {
        public final A first;
        public final B second;

        public Pair(A first, B second) {
            this.first = first;
            this.second = second;
        }
    }

    public static <A, B> Pair<A, B> makePair(A first, B second) {
        return new Pair<>(first, second);
    }

    public static <T> List<Pair<Integer, T>> iterRange(int from, int to, Function<Integer, List<T>> function) {
        List<Pair<Integer, T>> result = new ArrayList<>();
        for (int i = from; i <= to; i++) {
            final int j = i;
            function.apply(i).stream().map(x -> makePair(j, x)).forEach(result::add);
        }
        return result;
    }

    public static List<Tree> generateAllTrees(int size) {
        if (size <= 0)
            return Collections.emptyList();
        else if (size == 1)
            return Arrays.<Tree>asList(new Leaf());

        final List<Tree> result = new ArrayList<>();
        for (final Pair<Integer, Tree> pair1 : iterRange(1, size - 3, Trees::generateAllTrees)) {
            for (final Pair<Integer, Tree> pair2 : iterRange(1, size - 2 - pair1.first, Trees::generateAllTrees)) {
                generateAllTrees(size - 1 - pair1.first - pair2.first).stream()
                        .forEach(x -> result.add(new Branch3(pair1.second, pair2.second, x)));
            }
        }
        for (final Pair<Integer, Tree> pair1 : iterRange(1, size - 2, Trees::generateAllTrees)) {
            generateAllTrees(size - 1 - pair1.first).stream()
                    .forEach(x -> result.add(new Branch2(pair1.second, x)));
        }

        return result;
    }

    public static void main(String[] args) {
        generateAllTrees(10).forEach(x -> System.out.println(x.size()));
    }

}