Здравствуйте, kurtx, Вы писали:

Делаю как на wiki:

Сначала пишу функцию деления списка на две части. Для начала опишу для удобства несколько типов.

data BinTree a = Leaf a | Branch (BinTree a) (BinTree a) deriving Show

type Freq = (Char, Integer)

Сама функция делит список на две части, суммы частот которых наиболее близки.

1. Для этого получаем сначала список всех возможных пар списков. Это можно сделать по разному (splitAt по всей длине или пройтись свёрткой, собирая списки). Мы сделаем просто — склеим головы и хвосты: zip (inits xs) (tails xs)

2. Отсортируем полученный список пар и выберем голову. sortBy в Haskell имеет тип (a -> a -> Ordering) -> [a] -> [a]. Т.к. у нас `a` — это ([(Char, Integer)], [(Char, Integer)]), то нам придётся сравнивать 4 списка (суммируем попарно, а потом берём разность), поэтому для упрощения напишем функцию сортировки, которая сравнивает значения получая их целые (Integer) представления:

sortAsInt :: (a -> Integer) -> [a] -> [a]
sortAsInt asInt xs = map fst $ sortBy (\(_, i) (_, j) -> i `compare` j) $ map (\xs -> (xs, asInt xs)) xs

Я предпочитаю лямбды не выписывать, поэтому в конечном коде их перенесу в where.

3. Собственно сама функция получения разницы сумм:

sumDiff xs ys = abs $ sndSum xs - sndSum ys
    where
            sndSum = sum . map snd

snd здесь нужно потому что у нас элемент xs (или ys) — это пара (Пара_списков, Разница_их_сумм)
Блин, быстрее пишется, чем объясняется.

Итого:

sortAsInt :: (a -> Integer) -> [a] -> [a]
sortAsInt asInt = map fst . sortBy sndCompare . map withInt
    where
        sndCompare (_, i) (_, j) = i `compare` j
        withInt xs = (xs, asInt xs)

divide :: [Freq] -> ([Freq], [Freq])
divide xs = head $ sortAsInt (uncurry sumDiff) $ zip (inits xs) (tails xs)
    where
        sndSum = sum . map snd
        sumDiff xs ys = abs $ sndSum xs - sndSum ys

Дальше генерация дерева. Это проще, т.к. генерация — это всего лишь рекурсивный обход — разделили на две части, для каждой части опять генерируем дерево и т.д. Если дошли до одиночного символа, генерируем из него листочек.

genTree :: [Freq] -> BinTree Freq
genTree [x] = Leaf x
genTree xs  = let (ls, rs) = divide xs in Branch (genTree ls) (genTree rs)