Haskell - списки от корня до листьев

Question

Код предполагает возврат списка всех путей от корня до листа в дереве в порядке слева направо. Узлы с одним дочерним узлом (один Tip и один Bin) не считаются конечными узлами.

Я пытался кодировать как

paths :: Tree a -> [[a]]
paths Tip = [[]]
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)

Но кажется, что возвращаемый путь включает узлы содин ребенок. Это приведет к таким путям, как [[4,3],[4]] на Bin (Bin Tip 3 Tip) 4 Tip.

Answer 1

Это связано с тем, что ваш paths Tip = [[]] возвращает список с одним элементом: пустой список.

Таким образом, это означает, что для Bin Tip 4 (Bin Tip 3 Tip), например,paths left, таким образом, вернет [[]], и вы добавите к этому списку 4, поэтому будет получен [4].

Если вы измените это значение на paths Tip = [], вы исправите проблемус тех пор он не даст элемента:

paths :: Tree a -> [[a]]
<b>paths Tip = []</b>
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)