Разделение дерева Haskell: может ли кто-нибудь объяснить эту строку?

split s (Root x lst rst)
 | s < x = let (nlt, nrt) = split s lst in
     (nlt, Root x nrt rst)

Может кто-нибудь объяснить эту строку? Я действительно не получаю часть let.

Я пробовал думать об этом, я понятия не имею, правильно ли я понял: мы связываем (nlt, nrt) с результатом split s lst; и split s lst будет (nlt, Root x nrt rst)

Это что?

Здесь полный код:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x lst rst)
 | s < x = let (nlt, nrt) = split s lst in
     (nlt, Root x nrt rst)
 | s > x = let (nlt, nrt) = split s rst in
         (Root x lst nlt, nrt)

Ответ 1

мы связываем (nlt, nrt) с результатом split s lst

Yup - split s lst - пара, и мы даем имена nlt и nrt двум элементам пары.

и split s lst будет (nlt, Root x nrt rst)

Нет, split s (Root x lst rst) (результат всей функции) будет (nlt, Root x nrt rst).

Но что делает вся функция?

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x lst rst)
 | s < x = let (nlt, nrt) = split s lst in
     (nlt, Root x nrt rst)
 | s > x = let (nlt, nrt) = split s rst in
         (Root x lst nlt, nrt)

Попробуйте это для некоторых выборочных данных:

> split 300 (Root 512 (Root 256 (Root 128 Empty Empty) (Root 384 Empty Empty)) Empty)
(Root 256 (Root 128 Empty Empty) Empty,Root 512 (Root 384 Empty Empty) Empty)

Итак, мы взяли дерево с 512 в качестве его корня и все элементы, меньшие его в левом поддереве, и разделили его так, чтобы первое дерево состояло из записей ниже 300, причем те, которые были более 300 во втором, Это выглядит так:

Как работает эта строка?

Сначала перепишите код с расширенными именами:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x left_subtree right_subtree)
 | s < x = let (new_left_tree, new_right_tree) = split s left_subtree in
     (new_left_tree, Root x new_right_tree right_subtree)
 | s > x = let (new_left_tree, new_right_tree) = split s right_subtree in
         (Root x left_subtree new_left_tree, new_right_tree)

Защитник |s < x означает, что мы имеем дело с тем, что этот x должен идти справа.

Сначала разделим левое поддерево split s left_subtree, указав нам new_left_tree и new_right_tree. new_left_tree - это материал, который должен идти слева, но new_right_tree объединяется с x и оригинальным right_subtree, чтобы составить биты, которые идут справа от s.

Что мы можем узнать об этой функции?

right_subtree остается одним, потому что s принадлежит слева от x, поэтому функция предполагает, что дерево уже отсортировано в том смысле, что в Root x l r все в l ниже x и все в r выше x.

left_subtree получает разделение, потому что часть его может быть меньше s и других бит больше, чем s.

Часть split s left_subtree, которая теперь принадлежит справа (потому что она больше, чем s), называется new_right_tree, а поскольку все left_subtree меньше x и right_subtree, все из new_right_tree должно по-прежнему находиться слева от x и right_subtree. Поэтому мы делаем Root x new_right_tree right_subtree правильным ответом в паре (и new_left_tree слева от пары).

Здесь диаграмма до и после:

Почему бы не написать более описательные имена?

Хороший вопрос. Позвольте сделать это:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root this below_this above_this)

 | s < this = let (below_this_below_s, below_this_above_s) = split s below_this in
     (below_this_below_s,  Root  this  below_this_above_s  above_this)

 | s > this = let (above_this_below_s, above_this_above_s) = split s above_this in
         (Root  this  below_this above_this_below_s,  above_this_above_s)

Хорошо, я думаю, что это отвечает на мой вопрос: иногда описательные имена тоже могут сбивать с толку!