Ярлыки дерева

Question

Со следующим типом данных

data Tree a = Node a [Tree a]

Я хотел бы создать следующую функцию:

labels:: Tree a -> [a]
labels (Node label children) = label: (map labels children)

, но это принимает значение

   * Occurs check: cannot construct the infinite type: a ~ [a]
      Expected type: [a]
        Actual type: [[a]]

Имеет детейx: xs тоже не помог, так как xs все равно будет списком деревьев, а не одним деревом.

Answer 1

Ваша функция labels имеет тип Tree a -> [a]. Таким образом, это означает, что если вы создаете map labels, он имеет тип map labels :: [Tree a] -> [[a]]. Таким образом, вам необходимо объединить эти элементы, чтобы мы создали список [a] вместо [[a]].

. Вместо него можно использовать concatMap :: Foldable f => (a -> [b]) -> f a -> [b]:

labels :: Tree a -> [a]
labels (Node label children) = label : <b>concatMap</b> labels children

Наличие children в качестве x:xs не помогло бы, так как xs все равно был бы списком деревьев, а не одним деревом.

Действительно,Более того, используя (x:xs), вы (ненужно) ограничиваете себя деревьями с непустым списком детей. Распространенным заблуждением является то, что x и xs являются «специальными» именами переменных в (x:xs). Вы просто сопоставляете шаблон с конструктором данных "cons" (:).

Answer 2

Вам нужно join, чтобы преобразовать [[a]] в [a], что происходит из законов монады.

Например:

module Tree where

import Data.Functor.Foldable.TH
import Data.Functor.Foldable
import Control.Monad (join)

data Tree a = Tree a [Tree a] deriving stock Show

makeBaseFunctor ''Tree

labels :: Tree a -> [a]
labels = cata $ \case
  TreeF a y -> a : join y